안녕

0. 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/154538 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 풀이 방법 DP를 이용해서 문제를 풀었다. 조금 더 최적화를 하기 위해서 for loop의 범위에도 제한을 주었고, 아래의 조건에도 제한을 주었다. BFS로 풀까 잠시 고민했는데, x = 1이고, y = 1,000,000이고, n = 1일 경우에 제일 빠른 경우는 19번이다. 첫 번째 단계에서 3개, 두 번째 단계에서 3^2개.... 19번째 단계에서는 3^19개.. 가 생..

0. 문제 링크 https://www.acmicpc.net/problem/2637 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 1. 풀이 방법 DP를 이용해서 풀었다. 장난감은 중간 부품, 기본 부품 들로 만들 수 있는데, 우선 기본 부품으로 만들 수 있으면 기본 부품으로 만든다. 장난감을 만들 수 있는 중간 부품 또한 어떤 중간 부품이 필요할 수 있다. 따라서 재귀를 통해 중간 부품을 만들 수 있는 기본 부품들을 구한다. 이런 식으로 재귀를 통해 장난감까지 올라가면, 장난감을 ..

0. 문제 링크 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 1. 풀이 방법 이 문제는 DFS + DP이다. 안 그래도 어려운 두 개를 붙였으니 더 어려웠던 것 같다. https://minny27.tistory.com/42 [백준 1937] 욕심쟁이 판다 (Python) 문제 : https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤..

0. 문제 링크 https://www.acmicpc.net/problem/1577 1577번: 도로의 개수 첫째 줄에 도로의 가로 크기 N과 세로 크기 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 둘째 줄에는 공사중인 도로의 개수 K가 주어진다. K는 0보다 크거나 같고, 50보다 작거나 같은 자 www.acmicpc.net 1. 풀이 방법 일단 맨 처음에는 BFS로 문제를 풀었는데, 시간 초과, 메모리 초과가 발생하였다. BFS가 아님을 깨달았고, 고등학교의 확통에서 비슷한 문제를 풀었던 경험이 생각났다. 현재 위치로 올 수 있는 애는 내 좌측과 위이므로, 좌측과 위로 갈 수 있는 경우의 수를 더하면 현재 위치에 도달할 수 있다.는 것이 확통에서 문제를 푼 방법이다. 물론 조합을 사용..

0. 문제 링크 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 1. 풀이 방법 예전 알고리즘 시간에 풀었던 문제라 비교적 간단하게 풀 수 있었음 2022.04.15 - [Computer Science/알고리즘] - [알고리즘] 동적 계획법 - 연쇄 행렬곱셈 (Chained Matrix Multiplication) 예전에 내가 쓴 글을 보면 자세히 설명해 놓았음 키 포인트는 i ~ i + dia까지의 최적을 구하기 위해서는 i ~ ..

0. 문제 링크 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 1. 풀이 방법 일단 문제를 보자마자 이건 DP라는 생각이 들었다. 가장 문제는 마지막 집과 첫 번째 집의 색이 달라야 한다는 것이다. 사실 마지막 집과 첫 번째 집의 색을 고려하지 않고 짰는데, 알고 보니 고려해야 해서 조금 수정을 했다. 그러면 고려를 한다면 어떻게 해야할까? 많은 고민을 했다. 누가 봐도 DP인데, 어떻게 첫 번째 집의 정보를 저장..

0. 문제 링크 https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 1. 풀이 방법 1번 시도(트리라 생각함) 1. defaultDict을 이용해서 자신의 직속 후임을 리스트로 만들어놓음 2. 그리고 우선 자신에게 칭찬을 더하고, 후임들을 또 재귀함 3. 재귀 제한에 걸려서, 다시 수정하고 제출하니 이번엔 시간 초과 2번 시도(트리에 BFS를 적용함) 1. 재귀 때문에 시간 초과라 생각함 2. 그래서 재귀를 bfs로 변경해서 구현함 3. 시간 초..

0. 문제 링크 https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 1. 풀이 방법 우선 0이 있다는 것은 +도 되고, -도 되므로 그냥 0이 n개 있으면, 0을 빼고 결과값에 2^n 만큼 곱해주며 된다. 아무튼 다른 숫자들은 2차원 배열을 만들어서 dp에 넣으면 된다. dp[가능한 숫자][현재까지 수행 횟수] 이런 식으로 하면, 최종적으로 원하는 숫자까지 가는데 만들 수 있는 등식의 수가 나온다. 항상 마지막에는 0의 개수만큼 2의 거듭제..

0. 문제 링크 https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 1. 풀이 방법 사실 해당 부분은 너무 어려워서 구글링을 하였다. https://hooongs.tistory.com/184 해당 블로그에서 설명을 잘 해놓았다.... 2. 코드 s1, s2 = input().strip(), input().strip() l1, l2 = len(s1), len(s2) dp = [[0] * (l2 + 1)..

0. 문제 링크 https://www.acmicpc.net/problem/11058 11058번: 크리보드 N = 3인 경우에 A, A, A를 눌러 A 3개를 출력할 수 있다. N = 7인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V를 눌러 9개를 출력할 수 있다. N = 11인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl www.acmicpc.net 1. 풀이 방법 문제에서 파악을 잘 해야 하는 것이, 전체 선택 -> 복사 -> 붙여넣기 과정은 한 번에 수행되어야 한다. 그리고 만약 buffer에 1보다 큰 값이 들어가있다면, 무조건 붙여넣기를 하는게 이득이다. 그러면 문제는 이제 어디서 전체..