본문 바로가기

C C++166

알고리즘 병합 정렬 완벽 이해하기 병합 정렬이란? 병합 정렬은 나누고 붙이는 과정을 기반으로 한 정렬 알고리즘이다. 하나의 배열을 둘로 나누고, 이를 정렬하여 다시 붙이게 된다. 병합 정렬은 재귀 함수 호출로 정렬할 수 있는 데, 배열을 1/2씩 최대한 쪼갠 후 쪼개진 배열을 정렬하고, 최대한 쪼개진 배열을 둘씩 붙이고, 다시 정렬하고, 다시 붙이고...를 반복한다. 사실 설명보다 아래 그림을 이해하는 편이 더 쉽다. 이 정렬 방식은 최악, 최선 어느 경우에도 O(Nlong(N))의 시간 복잡도를 가진다. 공간 복잡도는 O(n)이다. 코드 부분 부분 해설 코드는 아래와 같은 형식으로 풀 수 있다. 1. 반으로 최대한 쪼갤 수 있을 때까지 쪼갠다. (재귀 함수 호출, 더 쪼갤 수 없을 때는 리턴) 2. 정렬의 가장 왼쪽을 가리키는 값(p1.. 2022. 10. 29.
[C/C++] 백준 10026번 적록색약 문제 풀이 이 문제는 전형적인 BFS와 DFS 문제이며 DFS로 문제를 풀도록 하겠다. 예시의 부분은 아래와 같다. R R R B B G G B B B B B B R R B B R R R R R R R R 예를 들면 첫 번째 [1,1], [1,2], [1,3] 영역을 칠하게 된다. 어떠한 식으로 칠해야할까? 1) for문으로 모든 영역을 훑도록 한다. (visit 체크된 좌표는 이미 칠했으므로 넘어간다.) 2) [1,1]이 입력되면 해당 좌표를 방문하였으므로 visit 체크한다. 3) 상하좌우 탐색한다. 4) 범위 밖으로 나가면 넘어간다. 5) 색이 다르는 등의 조건이 맞지 않는 경우 넘어간다. 6) 연결된 부위에서 조건이 맞는 내용은 또 칠한다. (DFS 함수에 탐색된 좌표를 다시 넣는다.) 위와 같다.. 2022. 10. 26.
[C/C++] DFS 61. 특정 수 만들기(DFS : MS 인터뷰) 문제 풀이 N개의 원소로 구성된 자연수 집합이 주어지면, 집합의 원소와 ‘+’, ‘-’ 연산을 사용하여 특정 수인 M을 만드는 경우가 몇 가지 있는지 출력하는 프로그램을 작성하세요. 각 원소는 연산에 한 번만 사용합니다. 예를 들어 {2, 4, 6, 8}이 입력되고, M=12이면 2+4+6=12 4+8=12 6+8-2=12 2-4+6+8=12 로 총 4가지의 경우가 있습니다. 만들어지는 경우가 존재하지 않으면 -1를 출력한다. 입력설명 첫 번째 줄에 자연수 N(1M; for (int i=1; i>arr[i]; } } void DFS(int cnt, int sum) { if (cnt==N+1) { if (sum==M) { flag=true; cnt_value++; return; } return; } DFS.. 2022. 10. 22.
[C/C++] DFS 60. 합이 같은 부분집합(DFS : 아마존 인터뷰) 문제 N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요. 예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다. 입력설명 첫 번째 줄에 자연수 N(1n이 되어 if-return을 만나서 return된다. 1+2+3을 모두 더한 것이다. 그렇다면 return되었으니 x+1에서 하나 이전인 x값을 가지는 함수로 돌아가게 된다. 그리고 그 다음 DFS(x+1, tmp);를 만나게 된다. 이 함수는 횟수는 늘어나는 데, x .. 2022. 10. 20.

티스토리툴바