본문 바로가기

알고리즘

 (403)
그래프와 순회. [2667], [1012] [1. 문제 설명] NxN 크기의 배열에서 아래,위로 인접한 집들을 하나의 단지로 묶을 수 있을 때, 전체 단지의 개수와 각 단지에 속한 집들의 개수를 오름차순으로 출력 (대각선으로 인접한 것은 취급하지 않는다.) [2. 풀이 접근] 인접한 집으로 이동 할 수 있다는 점에서 그래프 개념으로 접근할 수 있다. 어떤 위치에서 이동할 수 있는 방향은 상,하,좌,우 4가지가 되므로, 각 경우에 대해서 dfs 를 수행 해 볼수 있다. 그러나, 좌표를 움직여야 하므로, 좌표가 NxN 배열을 넘어 선 경우, 이미 방문한 좌표, 좌표에 해당하는 값이 0인 경우는 무시해야 한다. 또한 작성 한 dfs 함수는 최종적으로 하나의 단지의 포함 된 집의 개수를 반환하는데, 기저 사례를 통과한 경우 최소 하나의 집이 있음이 보장..
그래프와 순회. [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. 시간초과 발생한 코드]
01. 완전 탐색 [1. 개요] 완전탐색이란 가능한 경우의 수를 일일히 나열하면서 답을 찾는 방법 컴퓨터가 충분히 빠르기 때문에 가능한 방법 [2. 재귀호출] 완전히 같은 코드를 반복해서 실행 및 다양한 알고리즘을 구현하는데 매우 유용한 도구 재귀 호출 작성 시 유의 할 점 => 더 이상 쪼개지지 않는 최소한의 작업에 도달한 경우, 답을 곧장 반환하는 조건문을 반드시(?) 포함하도록 한다. => 일명 기저 사례(base case) 에 대한 처리가 필요하다. 중첩 for 문 등을 아주 유용하게 대체 할 수 있다. 완전 탐색 구현 시 아주 유용한 도구 [3. 문제와 부분 문제] 문제 => 항상 수행해야 할 작업과 그 작업을 적용할 자료의 조합 부분 문제 (원래 문제의 부분 문제) => 원래 문제에서 한 조각을 떼어냈을 뿐, ..
우선 순위 큐. [1655] [3. 코드]
우선 순위 큐. [11286] [1. 문제 설명] 특정 연산 수행 시, 절대 값이 가장 작은 순서대로 값을 출력 [2. 풀이 접근] 우선 순위 큐를 사용한다. 정렬에 대한 조건을 정의한다. => 예제를 보면, 늦게 들어간 -1 이 먼저 출력되었음 => 절대값이 같은 경우, 작은 값이 먼저 출력되야 함.(최소 힙 특성) [3. 코드] [4. STL prioirty_queue] compare 작성 가이드 기준과 반대되는 comparator 를 생각해야 함 값이 클 수록 우선순위가 높은 경우 => std::less => 입력파라미터 기준 return Left 값이 작을 수록 우선순위가 높은 경우 => std::greater => 입력파라미터 기준 return Left > Right => 특정 기준으로 작성해야 하는 경우..

티스토리툴바