내가 그때 이걸 알았더라면

1. 서론 다익스트라 알고리즘이란, 그래프 상에서 한 정점에서 다른 (모든) 정점으로의 최단경로를 구하기 위해 사용되는 알고리즘이다. 인접 리스트와 우선순위 큐를 이용해 손쉽게 구현할 수 있다는 장점이 있어 많은 사람들이 사용한다. 2. 설명 먼저, 다음과 같은 그래프가 있다고 가정하자. 다익스트라 알고리즘은 먼저 시작점 자신의 거리를 0으로 두고 다른 갈 수 있는 모든 점들의 최단거리값 (dist[])를 업데이트한다. 업데이트시 만약 [현재 노드의 cost + 현재 가리키는 노드로 가는 edge의 cost] 값이 가리키는 노드의 dist값보다 작다면, dist를 업데이트한다. 그 다음, 방문하지 않은 다른 모든 점들중 가장 dist값이 작은 노드를 시작점으로 잡고, 다시 dist를 업데이트한다. 이를 ..

1. 문제 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 양의 정수 n(1 ≤ n ≤ 100,000)과 n개의 원소로 이루어진 수열 An이 주어진다. 이때, An에서 가장 큰 구간합을 구하여라. 2. 해결 방법 1. Brute Force 먼저 가장 간단한 방법은, Brute Force 방식으로 크기 n의 int 배열을 만들어 i번째 자리에서 1~i-1번째 자리부터에서의 합을 구해 O(n^2)(1~i에서 O(n), 이를 1번째부터 i-1까지 반복하므로 O..

1. 문제 https://www.acmicpc.net/problem/1822 1822번: 차집합 첫째 줄에는 집합 A의 원소의 개수 n(A)와 집합 B의 원소의 개수 n(B)가 빈 칸을 사이에 두고 주어진다. (1 ≤ n(A), n(B) ≤ 500,000)이 주어진다. 둘째 줄에는 집합 A의 원소가, 셋째 줄에는 집합 B의 원소 www.acmicpc.net 집합 A에는 속하지만, B에는 속하지 않는 원소들의 개수와 원소들을 모두 출력하는 문제이다. 집합에서 A - B (차집합)의 개념이 등장한다. 2. 풀이 방법 배열이나 리스트 등을 사용하면 해당 자료형 안에 특정 원소가 있는지 확인하려면 O(1)의 시간이 걸리기에, 접근하는데 시간이 O(1)이 걸리는 맵 자료형을 이용하여 문제를 해결했다. 먼저 A와 ..

1. 문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 길이가 n일 수열이 주어질 때, 이 수열에서 가장 긴 증가하는 부분 수열의 길이(연속일 필요는 없지만 증가해야 함)를 구하면 되는 문제이다. 2. 풀이 방법 LIS 문제의 해결법은 이 블로그에 잘 나와 있다. https://seungkwan.tistory.com/8 가장 긴 증가하는 부분 수열 (Longest..

1. 문제 https://www.acmicpc.net/problem/19566 19566번: 수열의 구간 평균 길이가 $N$인 수열 $A_1, A_2, \cdots, A_N$이 주어진다. 구간에 있는 모든 수들의 평균이 정확히 $K$인 구간의 개수를 구해 보자. www.acmicpc.net 길이가 n인 수열이 주어질 때, 이 수열에서 평균이 k인 구간의 개수를 구하면 되는 문제이다. 2. 해결 방법 1. 먼저 평균의 의미를 다시 생각해보자. 평균 = 원소들의 합 / 원소들의 개수이다. 양변에 원소들의 개수를 곱하면, 다음과 같이 쓸 수 있다. 구간합 = 평균 * 구간길이 이다. 즉, 구간합을 원소들의 개수로 나눠 이를 평균과 비교할 것이 아니라, 구간합이 구간길이 * 평균과 같은지만 비교해주면 된다는 것..

- 목차 1. 설명 2. 문제 리스트 3. 각 문제 풀이 및 개선할 점, 코드 1. 설명 22-10-30 21:00:00~ 23:00:00 2시간동안 진행한 모의대회 2 관련 풀이 정리 https://www.acmicpc.net/group/practice/view/15679/17 로그인 www.acmicpc.net 2. 문제 리스트 A - 제곱수의 합 (solved) https://www.acmicpc.net/problem/1699 B - 골드바흐의 추측 (solved) https://www.acmicpc.net/problem/6588 C - 기상청 인턴 신현수 (solved) https://www.acmicpc.net/problem/2435 D - 수열의 구간 평균 https://www.acmicpc...

1. 문제 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제에서는 밭의 가로, 세로 크기와 심어진 배추의 개수, 각 배추의 위치가 주어진다. 이때 배추들을 건강하게 키우기 위한 최소 배추흰지렁이 개수를 구하면 되는 문제이다. 2. 해결 아이디어 dfs, bfs 등을 이용하여 쉽게 해결할 수 있는 문제이다. 다만 이번 문제를 해결하면서 작은 문제를 마주쳐 그것에 대해 기록하려고 글을 쓴다... 3. 개선할 점 코드에서 전역으로 밭(field), visit..

1. 문제 https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicp..

1. 문제 문제 어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 ..

1. 문제 길이가 같은 두 개의 이진수 코드 A와 B가 있다고 하자. 이 두 코드 사이의 해밍 거리는 A와 B의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 수이다. 예를 들어, A=010010, B=011011 이라고 하면, 세 번째 비트와 여섯 번째 비트만 서로 다르므로 이 두 코드 사이의 해밍 거리는 2이다. 우리는 총 N개의 이진 코드를 가지고 있고, 각 코드의 길이는 K로 같다. 예를 들어, 다음과 같이 길이가 3인 5개의 이진 코드들이 있다. A=000 B=111 C=010 D=110 E=001 두 코드 A와 B사이의 해밍 거리를 H(A,B)로 표현한다. 그러면, H(A,B)=3, H(A,C)=1, H(A,D)=2, H(A,E)=1 이다. 우리는 이진 코드들에..