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를 한 횟수가 결국 배..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 특정 위치까지 몇칸을 가야하는지 구하는 문제로 BFS를 사용하여 해결하였다. 탐색을 하면서 갈래길을 탐색해야하므로 상/하/좌/우를 검사하기 위한 좌표 리스트를 Cross_x, Cross_y로 만들었다. 그리고 BFS를 작성하고 나니 어떻게 특정 위치까지의 거리를 계산할까 하다가 BFS로 탐색한 깊이 지도를 하나 만들었다. 이 지도는 처음 시작부분부터 최소 몇번을 가야지 도달할 수 있는지 저장해놓는 지도로 BFS를 하면서 저장한다..