컴공과고씨

백준을 풀다보면 마주하는 최단 경로 탐색 알고리즘 다익스트라이다. 다이나믹 프로그래밍을 활용한 알고리즘으로 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 다만 이때 음의 간선을 포함하면 안된다. 간선에 음수가 포함 되어있을 때에는 벨만-포드 알고리즘을 사용해야하는데 이것은 나중에 다루어 보고 일단 다익스트라에 대해서 살펴보자. 핵심은 1. 목표 정점까지의 최단 거리는 여러개의 최단 거리로 이루어져있다. 2. 그래서 하나의 최단 거리를 구할 때 그 전까지 최단거리를 이용해준다. 먼저 선언해주어야 하는 것이 우선순위 큐, 각 정점까지의 거리를 담을 dst[] 배열이다. 우선순위 큐는 다음 정점의 번호와, 다음 정점까지 거리를 담고 있고 다음 정점까지 거리를 최소로 하는 것이 루트로 갈 수 ..

https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 문제 간단 정리 지민이가 여러 개의 파티에 감. 파티마다 참석하는 사람이 주어짐. 지민이가 거짓말을 할 건데 진실을 아는 사람이 주어짐. 진실을 아는 사람에게 거짓말을 하면 안됨. 또한 어느 파티에서는 거짓을 듣고 다른 파티에서 진실을 듣는 것도 안됨. 즉, 거짓말이라는 것을 아무도 알아채지 못하게 거짓말을 많이 할 수 있는 파티의 개수를 구하라. 문제 해결 방법 이 문제 같은 경우 유니온 파인드를 쓰면 쉽..

https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 문제 간단 정리 이 문제는 말 그대로 nCm을 구해주면 되는 문제이다. nCm 이란 서로 다른 n개 중 m개를 뽑는 방법을 말한다. 구하는 법은 n!/m!(n-m)! 이다. 문제 해결 방법 이런 문제 같은 경우 공식을 구현하기 할 수는 있겠지만 답이 겁나게 크게 나오는 걸 볼 수 있다. 즉, c++에서는 저런 큰 수를 정수로 담을 변수가 없기도 하고 공식 구현 하더라도 일일이 다 곱하는 팩토리얼이 있기 때문에 시간초과가 걸릴 수 밖에 없다. 일단 써봐서 규칙을 찾아보는 것이다. 1C0 1C1 2C0 2C1 2C2..

https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제 간단 정리 정말 간단하다 a,b,c가 주어짐. a^b을 구하는 문제임. 단 a^b값이 너무 클 수 있으니 c로 나눈 나머지를 구하면됨. 문제 해결 방법 일단 나머지 정리를 알아야함. 나머지 정리는 그냥 간단하게 그냥 ((a%c) * (b%c) %c) 하고 (a*b)%c 같다. 즉, 이런 문제가 나오면 그냥 나머지 구하고 곱해주고 나머지 구해주면 된다. 제한 시간이 2초이기 때문에 1초에 3~5억번 연산을 한다고 했을 때 문제의 주어진 수가 최대 21억이기 ..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 문제 정리 7 3 8 8 1 0 2 7 4 4 처럼 삼각형이 주어짐 이때 삼각형의 크기가 주어지는데 높이를 나타냄 이 삼각형의 크기는 4임. 이렇게 해서 위에서 부터 숫자를 더해 밑으로 내려온다. 내려갈때는 왼쪽, 오른쪽 대각선으로 이동이 가능하다. 이때 숫자의 최대 합은? 문제 해결 방법 일단 다이나믹 프로그래밍을 이용해서 문제를 풀어야한다. 그리고 쉽게 문제를 풀기 위해 위 삼각형을 0 7 ------ 1번 줄 0 3 8 ------ 2번 줄 0 8 1 0 ----..

https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 문제 간단 정리 이진트리가 있음 - 노드의 왼쪽 서브트리에 있는 모든 노드의 값은 부모의 값보다 작음. - 노드의 오른쪽 서브트리에 있는 모든 노드이 값은 부모의 값보다 큼. 이 이진 트리에서 전위 순회 -> 루트 - 왼쪽 - 오른쪽 방문 하며 출력. 후위 순회 -> 왼쪽 - 오른쪽 - 루트 방문 하며 출력. 인데 전위 순회 결과가 주어졌을 때 후위 순회한 결과를 한 줄에 하나씩 출력..

https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 문제 간단 정리 문자열이 2개 주어짐 하나는 전체 문자열 다른 하나는 폭발 문자열. 전체 문자열 안에 폭발 문자열이 있으면 그 폭발 문자열이 폭발하여 없어짐. 모든 폭발 문자열이 없어지고 난 후 전체 문자열에 남아 있는 문자열 구하라. 해결 방법 최대한 반복을 적게 해야지 시간 초과가 나지 않는다. 즉, 그냥 무작정 한 개씩 비교하다 폭발이 일어나고 다시 앞에서 비교하면 당연히 시간..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 정리 집을 3가지 색으로 칠할 수 있음. 각 집마다 각 색으로 칠하는 비용이 다름. 각 집의 색깔은 바로 앞 집과 바로 다음 집의 색깔과 같으면 안됨. 비용을 최소로 칠하는 비용은? 문제 해결 방법 이 문제의 경우 다이나믹 프로그래밍을 이용하면 쉽게 풀 수 있다. 일단 dp[3][n]이라는 배열을 만든다. 이 배열의 의미를 먼저 알아보자. 앞에 3이라는 것은 3가지 색깔..

https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제 정리 1. 행렬이 주어짐. 2. 시작 좌표 (x1,y1)이 주어지고 도착 좌표 (x2,y2)가 주어짐 3. 좌표 사이에 있는 값의 합들을 구해야함. 예를 들어 초록색이 시작 좌표, 파란색이 끝 좌표라고 하면 저런식으로 보라색 빗금의 부분의 합들을 구해주면됨. 문제 해결 방법 그 전 구간 합 구하기를 해보면 알듯이 일일이 for문을 돌리면서 구해주면 ..

알고리즘 문제들을 풀다보면 각 원소들이 속해 있는 집합을 구별해야하는 문제를 볼 수 있다. 유니온 파인드에 대한 자세한 설명은 생략하고 간단히 설명하고 구현 함수들을 보여드리겠습니다. 기본 개념 속해있는 집합이라고 생각하시면 됩니다. 1,2,3,4,5 라는 원소가 있다고 하면 처음에는 자신의 숫자가 속해있는 그룹 번호라고 합시다. 그룹 번호-원소로 나타내면 1-1 2-2 3-3 4-4 5-5. 여기서 1번 원소와 2번 원소를 합친다는 것은 1번 원소가 속한 그룹과 2번 원소가 속한 그룹을 합치는 것입니다. 나타내면 1-1,2 3-3, 4-4, 5-5 가 되겠죠. 여기서 2번원소와 4번 원소를 합치면? -> 1-1,2,4 3-3 4-4 5-5 가 됩니다. 이렇게 해서 같은 그룹을 만들어 나가는 것을 유니온..