Algorithm/백준
-
[ C++ ] 1918 - 후위표기식Algorithm/백준 2020. 7. 1. 16:48
풀이 과정 1. A-Z가 오면 ex에 담습니다. 2. A-Z가 아닌 연산자가 오면 stack에 쌓습니다. 3. ( 조건을 만족하는 동안 계속 ) stack의 맨 위 연산자가 새로 들어오는 연산자보다 가중치가 높거나 같으면 ex에 옮겨담습니다. 4. '(' 가중치에 상관 없이 무조건 stack에 쌓는다. 5. ')'를 만나면 '(' 위에 있는 모든 연산자를 ex에 옮긴다. (A+B*C-D) → ABC*+D- 이 반례에서 문제가 생겨서 보니까 3번 과정의 조건을 만족하는 동안 계속 진행해줘야 해서 문제가 발생했다. Code #pragma warning(disable:C4996) #include #include #include #include using namespace std; char cmd[105]; c..
-
[ C++ ] 2718 - 타일 채우기Algorithm/백준 2020. 6. 10. 21:13
문제의 대분류를 보면 비트마스킹과 DP로 되어있다. 하지만 아무리 생각을 해도 DP로는 어떻게 풀어야할지 몰라서 재귀를 이용해서 문제를 푸는 방법으로 접근하였다. 4 x 2인 경우 아래와 같이 5가지로 나올 수 있다. 위의 5가지 경우를 보면 현재 상태에 따라서 다음 상태가 어떻게 나올 수 있는지 알 수 있다. 이를 토대로 나올 수 있는 경우의 수를 계산하면 아래와 같다. 이를 토대로 코드를 작성하고 메모이제이션을 이용하면 시간을 줄일 수 있다.
-
[ c++ ][ Python ] 퇴사Algorithm/백준 2020. 4. 30. 17:31
처음에 문제를 읽고나서 가장 먼저 든 생각은 DFS면 풀리겠다 였다. 생각대로 i번째 날짜에서 상담을 하는 경우와 하지 않는 경우로 나누면 답을 빨리 구할 수 있었다. 이 경우 N이 최대 15이기 때문에 재귀로 문제를 풀어도 문제가 발생하지 않는다. DFS code C++ #include #define MAXSZ 17 using namespace std; int N, res = -1; int day[MAXSZ]; int price[MAXSZ]; void solve(int cur, int sum) { if (cur == N) { if (res N) return; solve(cur + 1, sum); solve(cur + day[c..
-
[ Python ] 오르막수Algorithm/백준 2020. 4. 28. 16:55
python을 잘 사용하지 못해서 시작을 어떻게 할지에 대해 열심히 고민했다. dp = [[1]*10 for _ in range(N)] 해당 코드를 통해 2차원 리스트를 생성할 수 있다. 문제를 풀 때 출력에서 가장 큰 고생을 해서 여러 방면으로 출력을 해보려고 노력했다. print (dp[N-1][9] % MOD) print (dp[-1][-1] % MOD) print (sum(dp[-1])%MOD) python에서는 배열의 index에 마이너스 기호(-)를 붙이면 뒤에서부터 index를 가르킨다. 단순히 dp[-1] 이라고 선언하면 dp 배열의 마지막행 전체를 나타낸다. Code N = int(input()) MOD = 10007 dp = [[1]*10 for _ in range(N)] for r i..