SW 공부노트

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 위 문제는 그래프를 이용해 최대값을 구하는 문제이다. 보통 그래프 관련 문제로는 BFS를 이용한 최단거리, 최소값 문제를 많이 풀었어서 처음에는 조금 낯설었다. 최대값을 구하는 문제에서는 DFS를 많이 사용한다. 가능한 모든 루트를 돌아 최대값을 구해야 하는데 visited 처리 부분에서 어려움을 겪었다. 백트래킹을 통해 DFS가 리턴되면 해당 좌표 visited를 false 처리해 다른 ..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net BFS를 활용한 최소비용 문제이다. 간단한 BFS 문제라고 생각했지만 익은 토마토가 여러 개일 경우, 각 위치에서 하루마다 익는 토마토를 어떻게 처리해야할 지 고민했다. 이를 포함해서 문제를 풀면서 고려한 부분은 총 3가지 이다. 1. 익은 토마토가 여러 개일 경우 하루마다 익는 토마토 처리 방식 처음에는 토마토가 익을 때마다 count를 증가시키는 방식으로 생각했지만, 하루에 여..

https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 이 문제는 중위 표기식을 후위 표기식으로 변환하는 문제이다. 스택이나 큐를 사용하면 되겠다고 생각은 했지만 연산 순서나 괄호를 어떻게 처리해야 할지 모르겠어서 결국 여러 답변을 참고했다 😢 풀이에서 주요한 부분은 연산 우선순위를 정하는 함수와 기호 별 처리 조건문이다. 1. 연산 우선순위 함수 처음에는 괄호가 우선순위가 가장 높다고 생각했는데, 결국 괄호 내 기호들의 우선순위를 정해야 하므로 ..

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제를 보고 바로 우선순위 큐를 사용하면 되겠구나! 하고 생각했다. 하지만 우선순위 큐는 인덱싱 기능이 없어서 가운데 값을 어떻게 구해야 되나 헤매다 우선순위 큐를 빌 때까지 poll 해 temp 우선순위 큐에 넣고, 이를 List로 변환 후 인덱스를 통해 가운데 값을 구했다. 답은 제대로 출력됐지만 메모리 초과 때문에 실패했다😢 풀면서도 더 나은 방식이 있을 것 같아서 검색해 본..