거창한 시작

www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 알고리즘 종류 - 투 포인터 사고 과정 - 두 개의 포인터를 배열의 양끝에 놓고 비교하면서 포인터를 움직이면 된다. 1. left와 right에 해당하는 값을 더해서 sum을 구한다. 2. sum의 절대값이 이전의 값보다 작으면, left와 right가 가리키는 값을 저장한다. 3. left와 right가 교차할 때까지 반복한다. 구현(C++) 1 2 3 4 5 6 7 8 9 ..

www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 알고리즘 종류 - 플로이드 와샬(floyd warshall) 사고 과정 - 플로이드 와샬 적용하기 구현(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 #include #include using na..

www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 알고리즘 종류 - 다익스트라 사고 과정 - 3가지 방법으로 이동하고 비용이 있다. * x +1, time + 1 * x - 1, time + 1 * x * 2, time - 이동하는 간선에 비용이 있고, 최소 비용으로 도착하는 방법을 찾기 위해서는 다익스트라 알고리즘을 사용한다. 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19..

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