나만의 길

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 그리디 알고리즘. 해당문제는 구현방식은 떠올리는데 크게 어렵지 않았습니다. - 뒤에 나오는 모든 숫자를 다음 -가 나오기 전까지 모두 더한 값을 빼주면 된다. 다만, 문자열을 indexing 하는 방식이 다소 까다로웠던 문제였습니다. 확실히 입출력 기본기가 단단해야 한다는 점을 많이 느낄수 있었던 문제였습니다. ※ 고려사항 1. 입력 indexing 2. 구현 1. 입력 indexing 생각..

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net BFS를 이용하여 구현하는 문제. 그러나, 구현방식을 생각하지 못했습니다. 뱀과 사다리를 처리하는 방법을 생각하지 못해, 풀이를 참고해서 제 방식대로 구현했습니다. 먼저, 각각의 보드판에 이동 횟수를 저장하고, 방문여부와 뱀과 사다리를 적절하게 구현하여, BFS를 구현하면 됩니다. 해당 내용은 아래에서 설명하겠습니다. ※ 고려 사항 1. 뱀, 사다리 ..

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 입출력 인덱싱과 R처리만 구현하면 크게 어렵지 않았던 문제. 남들은 시간초과가 발생했다고 했는데, 오히려 틀렸습니다.. 이후 정답.. 생각보다 문제에 잘 접근했었던 것 같습니다. 시간초과를 해결하는 중요 포인트가 R에서 reverse를 최종적으로 1번만 처리하는 것입니다. 이에 대해서는 아래에서 설명하겠습니다. ※ 고려사항 1. 입력 인덱싱 2. 함수 처리 3. 출력 처리 1. 입력 인덱싱 생각보다 이 곳에서 시간을 많이 소비했습니다. split과 st..

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net DFS, BFS를 이용하여 구현하는 그래프 문제. 단, 기존의 그래프문제와 살짝 다른 점은 3차원 공간상에서 문제를 해결해야 합니다. 2차원에서 해결하는 토마토 문제를 잘 해결하셨다면, 해당문제를 푸는데 크게 어려움은 없을 거 같습니다. 공간을 3차원으로 만들어주고, BFS를 이용하여, 각 상하좌우위아래로 움직여주면 됩니다. ※ 고려사항 1. 3차원 입력 2. BFS 3. ..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net BFS로 구현하는 문제. 해당 위치까지 최단경로로 이동하는 문제입니다. 해당문제를 단순히 재귀로 구현할 경우, 굉장히 까다로워 집니다. 왜냐하면, 상하좌우 방향 순서에 따라 도착하는 최단 경로가 달라집니다. 이에 대한 설명은 아래에서 하겠습니다. 따라서 Queue를 이용하여 BFS를 구현한 후, 문제를 해결할 수 있습니다. 유사한 문제로 7576번 토마토 문제를 푸시면 됩니다. ※ 고려사항 1. 입출력 구현 2. BFS 구현 1..

https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 전형적인 분할정복 문제. 앞서 포스팅한 분할정복 문제와 크게 다르지 않습니다. 다만, 괄호를 열고 닫는 구현이 추가된 문제입니다. 이 부분만 해결해 준다면, 큰 어려움 없이 해결할 수 있었습니다. 문제는 모든 행렬이 동일한 값이 아니라면 4 분할이 되므로, 색종이 개수 구하는 문제와 동일합니다. ※ 고려사항 1. 입출력 구현 2. 분할정복 구현 + 괄호 1. 입출력 구현 2차원 배열을..

https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 문제의 형태를 보니, 전형적인 분할정복 문제입니다. 단순히 재귀로 구현하게 되면 메모리초과나 시간초과가 발생하니, 경우를 나누어서 접근하는 것이 중요합니다. 2630번 색종이 만들기와 사실상 동일한 문제라고 봐도 무방합니다. 같은 값을 가졌는지 판별 후, Divide and Conquer을 실행합니다. 함수가 종료되면, 횟수를 카운팅 하면 됩니다. ※ 고려사항 1. 입출력 형식 2. 분..

https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 시간 초과를 어떻게 해결하느냐가 중요했던 문제입니다. 3번의 시간초과 끝에, 문제를 풀 수 있었습니다. 해당문제에서 중요한 것은 heap을 통한 Queue 구현인데, 바로 2개의 heap을 통해서 문제를 해결했어야 합니다. 개인적으로 시간초과를 해결하는 데까지 굉장히 어려웠던 문제였습니다. ※ 고려사항 1. heap, 방문 처리 2. 연산처리 3. 출력처리 1. heap, 방문 처리 해당문제에..