서로소 집합(Union-find), 크루스칼 알고리즘(최소 신장 트리), 위상 정렬과 관련한 문제들이다. 각 알고리즘의 설명 및 구현은 따로 올릴 것이다. 팀 결성 팀 합치기, 같은 팀 여부 확인 연산을 하는 문제로 Union-Find 방법을 이용해 푸는 문제였다. 0번 연산이 union을 만드는 연산, 1번 연산이 같은 parent를 가지는지 확인하는 연산이었다. 각각에 대해 makeUnion, findParent 연산을 만들어서 해결했다. int parent[100001] = { 0 }; int find_parent(int a, int b) { //항상 a
최단 경로 알고리즘은 다익스트라, 플로이드 워셜, 벨만 포드 알고리즘이 있는데 이를 각각 구현하는 포스트는 다음에 올리겠다. 한 지점에서 특정 지점까지의 최단 경로를 구할 때에는 다익스트라를, 모든 지점에서 모든 지점까지의 최단 경로를 구할 때는 플로이드 워셜을, 다익스트라와 같은 경우지만 음의 가중치를 가진 간선이 존재할 경우 벨만 포드 알고리즘을 사용하면 된다. 미래 도시 방향이 없고 가중치가 없는 그래프로 1번 회사에서 K번 회사로, K번 회사에서 X번 회사로 가는 최단 경로를 구하는 문제였다. 나는 이 문제를 1번부터 K번, K번부터 X번까지의 최단 경로를 다익스트라를 이용해 구한 후 두 개의 값을 더해서 풀었는데 책에서는 전형적인 플로이드 워셜 유형의 문제라고 했다. 노드와 간선의 개수가 100..
DP 문제는 수식을 생각해 줘야하는데 어려운 문제에서는 그게 참 어렵다. 책의 실전 문제에서는 아직 엄청나게 어려운 문제는 없었다. 1로 만들기 주어진 정수 X를 1로 만드는 연산의 최소 횟수를 구하는 문제였다. 연산 종류 X%5 == 0 이면 5로 나누기 X%3 == 0 이면 3으로 나누기 X%2 ==0 이면 2로 나누기 X - 1 하기 DP 문제를 풀 때는 초깃값을 설정할 수 있는 것은 설정하고, 나머지는 가장 큰 값으로 채우거나 비워놓아야 한다. 이 문제에서는 1,2,3,5 index의 값을 1로 설정할 수 있다. 문제의 수식은 4번째 값을 구할 때 찾아낼 수 있다. dp[4] = min(dp[4-1]+1 , dp[4/2]+1) 연산을 할 수 있다면 dp[연산 결과]+1을 비교해 최솟값을 찾아내는 ..
이진 탐색 문제는 left, right를 정하고 mid값을 비교해가며 풀면 된다. 이진 탐색 문제를 풀 때 배열은 항상 정렬되어 있어야 한다. 부품 찾기 배열 N 에서 배열 M의 값들을 찾는 문제였다. 배열 N의 값들을 오름차순으로 정렬한 후 M의 값들을 차례대로 이진탐색한 결과를 출력했다. 또, 찾아야 하는 값을 findNum으로 두고 초기 left와 right 값은 각각 0과 N 배열의 최댓값의 index인 N-1로 정했다. 이진탐색을 할 때 총 4가지 경우가 있다. narr[mid] 값이 findNum 보다 클 경우 → 왼쪽 범위를 탐색해야 함 (right 값을 mid-1로 바꿔줌) narr[mid] 값이 findNum 보다 작을 경우 → 오른쪽 범위를 탐색해야 함 (left 값을 mid+1 로 바..
long long을 사용할 때 %lf를 사용하는 줄 알았는데 아니었다!! long long은 %lld, long은 %ld를 사용한다.
string은 c++에서 만들어진 것이라 cin, cout으로만 입출력을 받을 수 있다고 한다. 개인적으로 scanf와 printf가 편해서 편법을 찾아봤다. 입력받기 scanf로 char를 입력받고 string 변수에 저장해주는 방법이 있다. char x[10]; scanf("%s",x); string a = x; 출력하기 string 변수 뒤에 .c_str()를 붙여주면 된다. printf("%s",a.c_str());
실전 문제는 굉장히 쉬웠다. 위에서 아래로 단순히 내림차순 정렬하는 문제였다. c++의 sort 함수는 오름차순 정렬이 기본으로 설정되어 있다. 내림차순 정렬을 하고 싶을 때에는 compair 함수를 생성해서 sort의 세 번째 인자로 넣어주면 된다. int compair(int a, int b) { return a > b; } int main() { int N; int i; int num[501]; scanf("%d", &N); for (i = 0; i < N; i++) { scanf("%d", &num[i]); } sort(num, num + N, compair); for (i = 0; i < N; i++) { printf("%d ", num[i]); } } /* 3 15 27 12 */ 성적이 낮은..
DFS BFS 문제는 dx, dy로 위치 이동을 해가며 stack이나 queue에 넣고빼기를 하면 되는 문제라 다른 문제들보다는 괜찮은 것 같다. 음료수 얼려 먹기 전체 맵에서 아이스크림 개수를 구하는 문제였다. 맵은 0과 1로 이루어져 있고 0이 길(뚫려 있는 부분), 1이 벽(칸막이)이었다. dx와 dy로 방향을 정하고 dfs 재귀함수에서 4방향 중 한 번도 방문하지 않았고 길이면 다시 dfs로 탐색한다. 이때 아이스크림 개수를 찾는 문제이기 때문에 맵 전체를 탐색해야 한다. for문으로 전체 맵에서 방문하지 않았고 길인 곳에서 dfs 함수를 호출하면 최종적으로 아이스크림 총 개수를 구할 수 있다. int g[1001][1001]; int N, M; int dx[4] = { 1,-1,0,0 }; in..
