거창한 시작

www.acmicpc.net/problem/20327 20327번: 배열 돌리기 6 크기가 2N×2N인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 8가지가 있고, 연산에는 단계 ℓ (0 ≤ ℓ < N)이 있다. 단계 ℓ은 배열을 부분 배열로 나눌때 사용하는 값이며, 부분 www.acmicpc.net 알고리즘 종류 - 구현 사고 과정 - l에 따라 부분 나누기 * for문 2개를 이용한다. 아래와 같이 구할 수 있다. for(int i=0; i

www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 알고리즘 종류 - 그리디(greedy) - 힙 구조(heap) 사고 과정 - 무게가 작은 가방부터 가장 비싼 보석을 넣는다. [그리디 문제는 확신이 없습니다. 틀린 부분이 있으면 댓글로 알려주시면 감사하겠습니다.] 1. 가방과 보석을 무게 순으로 오름차순 정렬한다. 2. 가방의 무게 이하인 보석을 모두 최대 힙에 저장합니다. 3. 최대 힙에서 가장 큰..

www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 알고리즘 종류 - 이분탐색 사고 과정 1. 합을 구하는 문제이므로 부분 합을 미리 구해 놓는다. 1-1. 배열 A, B의 합을 미리 구한다. 1-2. 배열 C, D의 합을 미리 구한다. 2. 목표 값을 정해서 이분 탐색을 진행한다. 2-1. 목표 값은 배열 AB(A와 B의 합이 저장된 배열)에서 하나씩 꺼내온다. 2-2. 목표 값을 가지고 배열 CD에서 이분 탐색을 진행한다. 2-3. 이분 탐..

www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 알고리즘 종류 - MST - Kruskal 사고 과정 - 전형적인 MST 문제 - 이미 연결된 간선을 구현하기 위해서 두 정점(v1, v2)에 union_find 알고리즘을 적용 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 ..

www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 알고리즘 종류 - MST - Kruskal 사고 과정 1. 기본적인 Kruskal 알고리즘 적용 2. 서로 다른 별 사이의 거리를 계산하기 위해서 pow와 sqrt 사용 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 ..

www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 알고리즘 종류 - 최단거리 - 다익스트라 사고 과정 - 출발 정점 1과 도착 정점 n은 정해져 있다. 그리고 이 사이에 v1과 v2라는 특정된 정점이 있다. 특정된 정점을 지나간다는 것은 특정 정점이 도착 정점이 된다는 것을 의미한다. 경우를 나열해 보면, 1->v1->v2->n 또는 1->v2->v1->n이다. 경우 1을 가지고 설명해보면, 1에서 v1로 가는 최단..

www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 알고리즘 종류 - 이분 탐색 사고 과정 1. 1~n*n 범위를 설정한다. 2. 이분 탐색으로 이 배열에서 mid를 구하고, mid보다 작거나 같은 값의 개수를 배열 A에서 구한다. 2-1. 구한 개수가 k보다 작으면, left = mid+1을 해준다. 2-2. 구한 개수가 k보다 크거나 같으면, right = mid -1을 해주고, answer = mid 해준다. 3. left

www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 알고리즘 종류 - 투 포인터 - 에라토스테네스의 체 사고 과정 1. 에라토스테네스의 체로 소수만 선별하기 2. 선별된 소수 배열에 투 포인터 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 #include #include #include using namespace std; in..

알고리즘 종류 - 구현 사고 과정 - 색이 같은 영역에서 회전을 시킨다. 1. 각 영역마다 (가로 길이 - 1) * 2 + (세로 길이 -1) * 2를 하면 1바퀴를 돌게 된다. 즉, 이 값으로 회전 횟수 r을 나눈 나머지가 유의미하게 회전할 횟수이다. 2. 유의미한 회전 횟수를 구한 후, 회전 횟수 만큼 각 변을 회전시킨다. 3. 하나의 영역이 완료되면, 내부 영역으로 옮기고 1번부터 다시 수행한다. 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 5..

알고리즘 종류 - 회전 사고 과정 1. 회전 횟수만큼 while을 반복한다. 2. 4개의 꼭지점을 찾고, 꼭지점이 사각형을 이룰 때까지 while을 반복한다. 3. 4개의 변에서 값을 시계방향으로 한 칸씩 이동시킨다. 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 #include #include using namespa..