본문 바로가기

알고리즘/Baekjoon

 (196)
그래프와 순회. [24444] [1. 문제 설명] 무방향 그래프가 주어졌을 때 시작 정점에서 bfs 시, 각 정점에 방문 순서를 출력하도록 한다. (인접 정점이 여러개인 경우 오름차순으로 정점을 방문하도록 한다.) 방문 할 수 없는 경우 0을 출력하도록 한다. [2. 풀이 접근] bfs 를 구현하기 위한 queue 는 container/list 패키지를 사용하여 구현한다. 또한, bfs 는 dfs 와 달리 인접 한 정점들이 먼저 방문할 수 있음을 보장하므로 실제 queue 에서 pop 된 시점이 아닌, queue 에 push 하는 시점에 바로 방문 처리해도 된다. [3. 코드]
그래프와 순회. [24479], [24480] [1. 문제 설명] 무방향 그래프가 주어졌을 때 시작 정점에서 dfs 시, 각 정점에 방문 순서를 출력하도록 한다. (인접 정점이 여러개인 경우 오름차순으로 정점을 방문하도록 한다.) 방문 할 수 없는 경우 0을 출력하도록 한다. [2. 풀이 접근] 실수했던 사항 메모리 사용량 => 문제에서 주어지는 정점의 개수는 최대 10만개 => 인접행렬로는 그래프 구현이 불가 (메모리 사용량 때문에) => 인접리스트로 구현 시, golang 에서 slice 를 사용하였는데, cap 를 10만으로 설정하여, 메모리 초과가 발생 => len: 0, cap: 0 으로 각 정점에 주어진 인접리스트를 초기화함 그래프 구현 => 주어지는 그래프는 무방향 그래프 => 처음에 edge 를 단방향으로만 여겨서 오답처리 되었음 =>..
백 트래킹. [14889] [1. 문제 설명] 2N 명의 사람을 적절히 나눠 N명씩 두개의 팀을 구성하였을 때, 두 팀 간의 능력치 차이가 최소값을 구한다. [2. 풀이 접근] 1. 두개의 팀을 구성하는 방법 보통 한개의 집합을 구성하는 경우는 재귀 호출 전, 적당한 자료구조(보통 리스트 같은 계열) 에 값을 저장(푸쉬)하고 다음 재귀로 넘기는 방식으로 구현하지만 여기서는 두개의 팀을 구성해야 하므로 이렇게 구현하는 경우 살짝 까다로울 것으로 생각함 그래서 한팀(A)은 0명에서 시작하고 다른 한팀(B)은 2N명에서 시작하도록 각각 배열을 준비하여, (두 배열 모두 길이는 2N) 각 재귀 호출 전 A 팀은 i번째 사람을 할당하도록 하고. (해당 index 값을 on) B 팀은 갖고 있던 i번째 사람을 제거하여 (해당 index 값을..
백 트래킹. [14888] [1. 문제 설명] 어떤 수열 사이에 산술연산자를 끼워 넣어 얻을 수 있는 계산 결과의 최대/최소를 구한다. (연산자 우선순위는 무시하고, 앞에서부터 차례대로 진행) [2. 풀이 접근] 사용 할 수 있는 연산자의 개수는 한정되어있으므로, 완전 탐색 방식으로 접근한다. 수열의 끝에 접근한 경우, 누적된 계산 결과를 확인하여 최대/최소를 갱신한다. 기타 자세한 구현은 코드 참조 [3. 코드]
백 트래킹. [2580] [1. 문제 설명] 스도쿠 규칙에 맞게 9x9 배열을 채워서 출력한다. [2. 풀이 접근] 잘못된 풀이 1차 풀이는 배열의 모든 원소에 접근 후, 해당 원소 값이 0인 경우, 1 ~ 10 까지 값 중에서 행/열, 그리고 작은 사각형 내 에서 허용된 값인 경우 해당 값을 이차원 배열에 할당 한다. 위 과정 전체를 하나의 문제로 놓고 재귀 호출한다. 이렇게 구현한 경우 시간초과로 인해 실패 처리되었다. 시간 초과에 대한 정확한 원인은 잘 모르겠지만, 아래와 같은 이유 때문으로 추정한다. 채워야 할 값의 위치가 아래와 같을 때 [y,x] = [ [0,0], [0,1], [3,3] ] for y < 9 for x < 9 // [y, x] 가 0인 경우 아래를 수행 /// 재귀 호출로 실행 된 경우, [0, 0]..
백 트래킹. [9663] [1. 문제 설명] [2. 풀이 접근] 체스에서 퀸은 자신을 기준으로 같은 행, 열 및 대각선에 있는 퀸은 공격하지 못한다고 한다. 첫번째로 작성한 풀이는 O(N^3) 이라 답은 맞는데 시간초과 발생 위키피디아 참조 [3. 코드] [4. 시간초과 발생한 코드]
우선 순위 큐. [1655] [3. 코드]
우선 순위 큐. [11286] [1. 문제 설명] 특정 연산 수행 시, 절대 값이 가장 작은 순서대로 값을 출력 [2. 풀이 접근] 우선 순위 큐를 사용한다. 정렬에 대한 조건을 정의한다. => 예제를 보면, 늦게 들어간 -1 이 먼저 출력되었음 => 절대값이 같은 경우, 작은 값이 먼저 출력되야 함.(최소 힙 특성) [3. 코드] [4. STL prioirty_queue] compare 작성 가이드 기준과 반대되는 comparator 를 생각해야 함 값이 클 수록 우선순위가 높은 경우 => std::less => 입력파라미터 기준 return Left 값이 작을 수록 우선순위가 높은 경우 => std::greater => 입력파라미터 기준 return Left > Right => 특정 기준으로 작성해야 하는 경우..
우선 순위 큐. [11279] [1. go heap 구현] go 에서 heap 을 사용하기 위해서는 container/heap 패키지를 사용해야 하며, 사용자가 정의한 heap 타입은 아래와 같이 몇가지 interface 들의 함수를 구현해야 한다. (h MinHeap) Len() int => heap 의 길이를 반환한다. => slice 길이를 반환하도록 한다. (h MinHeap) Less(parent, child int) bool => 보통의 heap 구현이 마지막 child 를 parent 와 비교해나가면서 루트로 올라가는 방식이며, => parent 와 child 간 값을 비교하여 parent 의 우선순위가 더 높은 경우 true 를 반환하도록 한다. => child 와 parent 간 swap 이 필요하지 않는 경우 tru..
이분 탐색. [2110] [1. 문제 설명] 일렬로 늘어선 N개의 집들에 C개의 공유기를 설치할 때 가장 인접한 두 공유기 사이의 거리의 최대 값 [2. 풀이 접근] A. 잘못된 접근 처음 이 문제를 보고 잘못 이해해서, 예제로 나온 답이 어떻게 나왔는지 이해하지 못했다. 왜냐하면, 1,2,9 이렇게 설치하면 두 공유기 사이의 최대 거리는 7이 나오기 때문이다. 두 공유기 사이 거리의 최대 값에 중점을 두었기 때문이다. 여기에 한가지 조건 "가장 인접한" 을 추가해야, 내 생각이 틀렸음을 이해할 수 있었다. 위와 같은 방식으로 설치하는 경우, 가장 인접한 두 공유기 사이의 거리는 1이 되기 때문이다. B. 올바른 접근 문제에서 주어진 C 공유기의 개수는 그렇게 중요한 요소는 아니다. 중요한 요소는 공유기 사이의 거리이다. C 가..

티스토리툴바