문제 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net 문제 풀이 수식이 주어질 때, 괄호를 추가하여 최대가 되는 수를 반환하는 문제이다. 괄호를 추가하기 위해서는 2가지 방법이 있을 수 있다. 예를 들어 예제 입력 1의 경우 `3 + 8 * 7 - 9 * 2`를 괄호를 추가할 수 있는 경우를 `DFS`로 탐색하는 방법은 다음과 같다. 두수 사이에 하나의 연산자 기호가 있어야 한다. `(3 + 8) * 7 - 9 * 2`와 같이 가장 앞의 연산자부터 우선 처리한다. `3 + (8 * 7) - 9 ..
프로그래머스: 등굣길
문제 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 문제 풀이 집에서 학교까지 가는 길은 MxN 일 때, 폭우로 인해 갈 수 없는 길이 있다. 이때, 등교를 할 수 있는 경우의 수를 반환하는 문제이다. 문제는 x, y에 따른 2차원 배열을 생성하여 방문하는 경로를 기록하는 방식으로 풀 수 있다. 기존의 그래프에서 위의 그림과 같이 0을 추가한 DP 배열을 초기화한다. 그리고 처음 출발점인 집을 1로 초기화한 후 점화식인 `dp[x][y] = dp[x - 1][y] + dp[x][y - 1]`을 각..
문제 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 문제 풀이 NxN 격자판에서 파이프를 한쪽 끝 (N, N)으로 이동시키는 방법의 수를 출력하는 문제이다. 파이프는 가로, 세로, 대각선으로 움직일 수 있으며 움직이는 각도는 45도이다. 즉 가로에서 세로, 세로에서 가로는 즉시 변환할 수 없다. 경우의 수를 계산하기 위해 아래와 같이 `DFS`로 풀었다. from sys import stdin def visitable(x, y, direction): if direction == DIA..
문제 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제 풀이 N개의 수가 차례대로 입력될 때, 중간 값을 출력하여 반환하는 문제이다. 문제를 풀기 위해서는 `heap`을 left, right로 나누고, left의 루트가 중간값이 되도록 로직을 구현하면 쉽게 해결할 수 있다. left는 최대 힙으로 만들고, right는 최소 힙으로 만들면 pop연산을 활용하기 좋다. 코드 from sys import stdin import heapq if __name__ == '__main__': n = i..
