컴공과고씨

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문을 돌리면서 구해주면 ..

https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 문제 정리 1. 유저가 번호로 주어짐 2. 관계가 주어짐. 관계라는 것은 예를 들어 1 2 이렇게 주어지면 1과 2는 연결되어 있다는 것을 말함. 3. 관계가 1 2 주어지고 2 4 로 주어진다고 치면 1에서 4로 갈때의 단계는 1 2(1단계) 2 4(2단계) 그래서 총 2단계를 걸처 1에서 4가 연결되어 있다고 함. 이 때 다른 사람과의 관계의 총..

https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 정리 0이 아니면 원소 추가. 0이면 추가된 원소 중 절대값이 가장 작은 원소를 출력 후 제거. 원소의 개수가 0일 경우 0이 입력되면 0을 출력. 문제 해결 방법 우선순위 큐를 떠올리면 간단하게 풀 수 있는 문제이다. 우선 순위 큐를 간단하게 보려면 https://hagisilecoding.tistory.com/60?category=1050177 위 링크에서 간단하게 ..

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제 정리 n개의 숫자가 주어짐 구간이 주어지면 그 구간안에 있는 숫자의 합을 구하라. 문제 해결 방법 무작정 구간이 주어질때마다 더하게 되면 시간 초과가 남. 숫자가 주어질때마다 거기까지의 합을 구해놈. 그 후 구간이 주어지면 마지막 구간까지의 합에서 시작 구간 전까지의 합을 빼주면 됨. 전체코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 간단 정리. 상어가 물고기를 먹으러 다님. 상어는 물고기의 크기보다 크면 물고기를 먹을 수 있음. 크기가 같다면 지나갈 수만 있음. -> 작으면 못지나 감. 물고기를 먹으면 그 칸은 빈칸이 됨. 상어가 한 크기에서 물고기를 먹은 횟수와 상어의 크기가 같게 되면 상어 크기가 1 증가함. 물고기를 먹을 때는 가장 작은 것을 우선으로 먹고 같은 크기가 많다면 가장 위쪽 우선 그 다음은 왼쪽..