CHAAANY ARCHIVE
3개의 기록을 주제별로 둘러보세요.
백준 1918은 중위 표기식의 operand는 바로 출력하고, operator는 stack에서 우선순위와 괄호를 처리하는 문제다. 예전에 비슷한 문제를 풀었어도 오랜만에 다시 보니 시간이 걸렸다. 그때 남긴 “알고리즘은 꾸준함이 중요하다”는 메모와 함께, 조건문을 줄인 현재 풀이를 정리한다.문제를 바꾸어 읽기중위 표기식은 operator가 operand 사이에 온다.A*(B+C)후위 표기식은 operator를 두 operand 뒤에 둔다.ABC+*후위 표기식에는 계산 순서를 위한 괄호가 필요 없다. 입력은 대문자 operand가 한 번씩 나오고 +, -, *, /, (, )만 사용하므로 unary minus나 exponent의 associativity는 고려하지 않는다.Stack에 무엇을 남길까outpu..
백준 24444번과 24445번은 같은 무방향 그래프를 BFS로 탐색하되, 인접 정점을 각각 오름차순과 내림차순으로 방문한다. 핵심은 각 정점의 인접 리스트를 먼저 정렬한 뒤 일반 FIFO queue로 BFS를 실행하는 것이다.백준 24444번 알고리즘 수업 - 너비 우선 탐색 1백준 24445번 알고리즘 수업 - 너비 우선 탐색 2PriorityQueue가 아니라 인접 리스트를 정렬한다“인접 정점을 오름차순으로 방문한다”는 조건은 현재 정점의 이웃을 번호 순서대로 queue에 넣으라는 뜻이다. BFS 자체의 선입선출 순서는 바꾸지 않는다.전체 frontier를 PriorityQueue에 넣으면 이전에 먼저 발견한 정점보다 번호가 작은 정점을 뒤늦게 꺼낼 수 있다. 그러면 거리별 탐색 순서와 발견 순서가..
백준 2178번 ‘미로 탐색’은 1인 칸만 지나 (1, 1)에서 (N, M)까지 이동할 때 지나야 하는 최소 칸 수를 구한다. 모든 이동 비용이 1이므로 FIFO queue를 쓰는 BFS가 출발점에서 가까운 칸부터 탐색한다.백준 2178번 미로 탐색BFS에서 처음 발견한 거리가 최단 거리인 이유queue에는 거리 d인 칸이 거리 d+1인 칸보다 먼저 들어간다. 아직 방문하지 않은 이웃을 처음 발견했을 때 현재 거리에 1을 더해 기록하면, 그보다 짧은 경로가 나중에 나타날 수 없다.시작 칸도 문제에서 세는 칸에 포함하므로 distance[0][0] = 1로 시작한다. 방문 여부를 별도 배열로 만들지 않고 distance가 0인지로 구분할 수 있다.Java 코드import java.io.BufferedRea..