컴공과고씨

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 간단 정리 N x N 도시에 집과 치킨집이 있음. 한 집과 치킨 집의 거리는 | 집의 행 - 치킨집의 행 | + | 열 - 열 | 이런식으로 계산됨. 각 집과 가장 가까운 치킨 집 사이의 거리를 모두 합한 거리를 도시의 치킨 거리라고 한다. 문제에 M이 주어지는데 M개 만큼 치킨 집을 폐업했을 때 도시의 치킨 거리 가장 작게 되는 도시의 치킨 거리를 구하시오. 문제 해결..

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/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가지 색깔..

알고리즘 문제들을 풀다보면 각 원소들이 속해 있는 집합을 구별해야하는 문제를 볼 수 있다. 유니온 파인드에 대한 자세한 설명은 생략하고 간단히 설명하고 구현 함수들을 보여드리겠습니다. 기본 개념 속해있는 집합이라고 생각하시면 됩니다. 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 가 됩니다. 이렇게 해서 같은 그룹을 만들어 나가는 것을 유니온..

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

https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 이 문제는 굉장히 간단합니다. map 컨테이너를 사용하면 간단히 풀 수 있습니다. 이러한 문제류는 pair같은 것으로 저장 후 탐색을 for문으로 돌리게 되면 시간초과가 나기 때문에 map 컨테이너를 이용해 key값을 찾아주는 것이 시간 복잡도 측면에서 유리합니다. 전체 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ..

https://www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net 문제 정리 I와 O가 반복된 배열이 주어짐. 1: IOI 2: IOIOI 3: IOIOIOI 이런 식으로 반복되는 수열의 길이 N이 주어짐. 배열안에 N으로 이루어진 IOI가 얼마나 있는지 구함. 예를 들어 N이 4라는 것은 IOIOIOIOI 이 부분이 배열에 얼마나 있냐는 것이다. 주어진 배열이 OOOIOIOIOIOIOIOOO라..

https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net 문제 정리 몇번 째 해인지 나타내는 방법을 라고 정의 여기서 x와 y의 최대값이 문제에서 주어짐. 예를 들어 m = 10, n = 12 라는 것은 x의 최대값은 10 y의 최대값은 12 1번째 해 = 1,1 2번째 해 = 2,2 이런식으로 해가 최대값을 넘지 않으면 +1 씩 증가 그러다가 최대값을 넘어가면 1로 다시 시작 10번째 해 = 10, 10 11번째 해 = 1, 10 이렇게 넘어감. 이 때 ..

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 문제 정리 배열이 주어짐. 명령어가 주어짐. 명령어는 문자열 형태로 R은 배열 뒤집기 D는 배열의 맨 앞 원소 빼기 두 가지로 구성됨. 명령어를 수행후 남은 배열 원소를 구해라. 단, 원소가 없을 때 D가 수행되면 error를 출력하라. 문제 해결 방법 이 문제 같은 경우는 deque를 이용해서 풀 수 있습니다. 저 같은 경우는 인덱스를 조작을 이용해서 deque를 사용하지 않고 풀었습니다. deque는 queue와 비슷하지만 다른 점은 양쪽에서 pop..