https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 분할정복 알고리즘으로 Z(2X2)모양이 나올때까지 좌표를 분할하여 Z가 되면 탐색을 하였다. 처음에는 좌표를 2차원 배열로 만들어서 직접 분할하였다. 숫자를 다 쓰면서 해당 좌표가 (r,c)이면 프로그램을 종료하게 했지만 시간초과가 떴다. 그래서 좌표를 분할할때 분할한 범위 안에 (r,c)가 없으면 탐색을 아에 하지 않도록 return을 추가해주었다. 하지만 그래도 시간초과가 떠서...다..

https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 정사각형안에 1만 존재하거나, 0만 존재하면 색종이를 카운트 하는 문제이다. 알고리즘은 분할정복이라고 나와있긴하지만, 문제를 분할한 다음에 다시 합치는 과정이 없기 때문에 그냥 재귀라고 생각해도 충분히 풀수 있는 문제이다. 분할정복을 더 알아보고 싶다면 파이썬의 정렬모듈로 사용되고 있는 병합정렬을 공부해보면 좋다. 풀이는 처음 시작점의 숫자를 저장해두고 탐색하다가 처음 ..

https://www.acmicpc.net/problem/24511 24511번: queuestack 첫째 줄에 queuestack을 구성하는 자료구조의 개수 $N$이 주어진다. ($1 \leq N \leq 100\,000$) 둘째 줄에 길이 $N$의 수열 $A$가 주어진다. $i$번 자료구조가 큐라면 $A_i = 0$, 스택이라면 $A_i = 1$이다. 셋째 줄 www.acmicpc.net 큐와 스택의 자료구조를 합쳐놓았을 때 프로그램이 어떻게 작동하는지 묻는 문제이다. 스택인 부분에 값이 추가되면 어차피 그 추가된 값이 pop되므로 스택은 없는셈 쳐서 문제를 해결할 수 있다. 큐는 여러개의 큐가 마치 하나의 큐인것 마냥 작동되는 기이한 현상이 일어난다. (사고가 어렵다면 직접 써보는것도 좋다) 결론적..

https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 섞는 횟수를 최소로 하기 위해서는 가장 적은 묶음 끼리 더하면서 카드를 합해야 횟수를 최소로 할 수 있다. 최소묶음 끼리 더하면 되기 때문에 최소값을 다루기 쉬운 우선순위큐 heapq 모듈을 이용하여 문제를 해결 할 수 있다. 최소묶음끼리 더하고, 나온 묶음을 다시 heappush하고, 다시 최소묶음끼리 더하고 ... 반복하면 끝! 코드는 다음고 같다. import sys impor..

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 문자열을 평소에 많이 다루어봤다면 무난하게 해결할 수 있을만한 문제라고 생각한다. (필자는 많이 안다뤄봐서 개인적으로 어려웠음)처음에는 P 리스트를 만들어서 S에서 I가 나올때마다 비교하는 방식으로 구현한 결과 50점이 나왔다.그렇게 코드를 짜면, 똑같은 부분도 계속 확인해야하기 때문에 시간이 상당히 오래걸린다. 문자열을 다루는 ..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 백준 2178번과 거의 똑같은 문제라고 할 수 있다. 2178번에서 미로를 탐색할때 몇번만에 갈 수 있는지 깊이 지도를 그려서 문제를 해결했었다. 이번 문제도 마찬가지로 어차피 하루당 한 칸씩 토마토가 익으므로 깊이지도를 그리면된다. 미로 문제와 다른점은 미로는 BFS의 출발점이 하나였지만, 토마토는 시작할 때 부터 여러개가 익어 있을 수 있기 때문에 queue에 익은 토마토를 모..