algorithm

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를 하면서 저장한다..

https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 백트래킹을 이용하는 문제이다. 재귀함수의 작동원리를 완벽하게 알지 못하다면 디버깅을 통해서 한번 코드가 어떻게 작동되는지 확인하면 좋을거 같다. 백트래킹의 좋은 예시로 미로가 있는데, 길을 찾다가 막다른 길이 나오면 다시 갈림길로 돌아가서 다른 방향으로 가야한다. 그때 다시 갈림길로 돌아가는 것을 백트래킹과정이라고 하면 이해하기 쉽다. 문제의 경우에는 친구의 연결관계를 찾다가 5명이 연결되기 전에 끊기면 끊기기 한단계 전 친구로 돌아가서 끊기는 쪽말고 다른 친구와 연결해봐야하는데 이 과정이 백트래킹 과..

https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 문제를 처음 보면 딱 드는 생각이 에라토스테네스의 체이다. 소수는 구하는 문제로는 백준 1929번에서 에라토스테네스의 체를 활용하여 소수를 빠르게 구했었다. 이번 문제도 똑같이 완전탐색으로 for문을 돌리면서 가능한 모든 경우를 다 에라테스테네스의 체를 이용하여 걸러내려고 했지만 시간초과가 떴다. 조금만 생각해봐도 N = 8이면 숫자가 9천만개가 있는데 그걸다 계산하려하니 시간초과가 뜰..