Written

백준에서 알고리즘 문제를 푸는건 오랜만입니다. 뭐니뭐니해도 역시 알고리즘 문제풀이 할 때가 가장 재미있는 것 같습니다.. https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 어떤 수 N이 주어지면 N을 만드는 또다른 M중 최솟값을 구하는 문제였습니다. 여기서 M은 M과 각 자리수의 합을 더했을 때 N을 만드는, 문제에서 말하는 생성자입니다. 처음에는 특별한 규칙이 있나 생각을 해봤는데 딱히 그런건 없는 느낌이 들어서 시..

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 시간초과로 인해 애를 많이 먹었던 문제입니다. 맨 처음에 문제를 보고 떠올린 풀이는 vector에 넣고 sort함수를 사용해서 가운데 수를 출력하는 것이었습니다. 문제의 시간제한이 0.1초이기 때문에 왠지 시간초과가 날 것 같다는 생각이 들었지만 ... 다른 풀이가 딱히 떠오르지 않아 풀이를 제출해보았는데 역시나 시간초과가 났습니다 :D 그래서 밑에 힌트를 확인해보니 , 우선순위 ..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제를 보고나서 드는 생각은 DFS로도 풀 수 있을것 같고, Union-Find로도 풀 수 있을 것 같다고 생각했는데 DFS로 문제를 풀어본지가 좀 오래된것 같아 DFS로 구현해서 풀어보았습니다. 컴퓨터간의 방향이 따로 없어서 인접리스트 형식으로 서로 연결되어 있게끔 데이터를 저장합니다. 그리고 문제가 1번 컴퓨터를 기준으로 시작하기 때문에 DFS(1)로 구현한 DFS함수를 호출합니다. DFS에 들어오..

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 이번 문제의 핵심은 '연결되어있기만 하다면' 다른 곳을 통하여 목적지까지 갈수 만 있으면 되는 것 입니다. 그래프의 연결관계를 확인하고 싶을 때, 사용되는 Union Find알고리즘으로 문제를 풀어보았습니다. 입력으로 주어지는 정보를 바탕으로 두 도시가 연결되어있다면 Union함수를 통해 이어주고, 마지막으로 답을 구하기 위한 최종 여행 루트의 연결관계를 파악해서 그 중 하나의 도시라도 이어져있지..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 큐에 좌표값을 저장해서 이동할 수 있는 곳이면 거리값들을 1씩 증가시키면서 마지막에 거리 정보를 저장한 배열의 [N][M]값을 출력하는 BFS탐색으로 문제를 해결해보았습니다. 그런데 첫번째 코드에서 메모리초과가 발생했습니다. 메모리제한이 192MB인데 , 배열의 크기도 크지않은데 어째서 메모리초과가 나는 것인지 ..궁금해 하다가 구글링 해본 결과 BFS를 사용할 때, 종종 발생하는 일이더라구요. 예를 들면 아직 (3,3)의 좌표..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net BFS를 사용해서 큐에 익힐 수 있는 조건의 토마토의 위치와 익는데까지 걸리는 날짜를 넣고 익힐 수 있는 모든 토마토를 탐색하는 방식으로 풀어보았습니다. 출력을 위해서 zeroCnt라는 변수를 만들어서 0의 개수를 세면서 토마토를 다 익힐수 없는경우와 처음부터 다 익혀져있는 경우에 대해서 정상적으로 출력할 수 있도록 했습니다. 최종적인 날짜 출력은 max라는 변수를 만들어서 큐에있..