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에 익은 토마토를 모..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제를 보자마자 BFS써야겠다라는 생각뿐. 단순하게 농장을 2차원 배열로 받아서 배추가 있는 부분만 1로 표시한다. 농장 전체를 훑으면서 배추가 있고 아직 탐색을 안한 부분이면 BFS를 돌리면 된다. BFS가 끝나면 그 부분에 배추흰지렁이가 필요하므로 count += 1을 해주면 된다. 그렇게 농장 전체를 훑으면 인접한 부분당 배추흰지렁이가 있는 것으로 탐색되므로 농장을 탐색하면서 BFS를 한 횟수가 결국 배..