printf("Hello dev_TORY!");

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 여러 DP 문제들을 풀면서 여태껏 한 두 문제 빼고는 DP를 1차원 배열로 선언해서 풀었기 때문에 본능적으로 DP를 1차원으로 고정해버리는 못쓸 습관이 생겨버림.. 이것도 문제랑 원리는 다 이해가 됐는데 구현해서 막혀버렸다.. DP에 소질이 없는걸로 쩝,, 이 문제는 여러 포스팅을 봐도 이해가 쉽지 않았다. 그 중에서 내가 이해하는..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이 문제는 DP에서 계속 다뤘었던 부분 증가 수열의 최대 길이를 구하는 문제와 비슷하지만 그냥 증가 부분 수열이 아닌, 두 문자열의 부분 수열의 최대 길이를 구하는 문제이다. 롸 너무 어렵다 또 구글링함...ㅋ 참고한 포스팅은 이거다. https://happylsm76.tistory.com/entry/%EB%B0%B1%EC%A4%80-9251%EB%B2..

https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 이 문제는 전봇대 A에서 전봇대 B로 여러 전깃줄을 설치할건데, 모든 전깃줄이 겹치지 않기 위해서 제거해야 할 전기줄의 최소 갯수를 구하는 문제이다. 거의 1시간 들여서 코드 작성을 했는데, 9퍼센트에서 오답이 나왔는데, 어디에서 틀린건지는 아직도 모르겠다.. 오답코드) n = int(input()) line = [] for i in range(n): line.append(list(map(int, inp..

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 롸 2시간 넘게 썼는데 아니다 3시간? 이게 수열마다 맞는게 있고 아닌게 있어서 if문으로 조건 엄청 걸다가 포기했다ㅋ 머리가 녹을 것 같다...,, 구글링해 본 결과, 전혀 다른 방법으로 접근해서 간단히 풀더라 쩝 나는 이 포스팅을 참고 했는데 이해가 잘 갔다. https://velog.io/@rjqnr928/%EB%B0%B1%EC%A4%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-110..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 이 문제는 풀긴 했는데 시간초과가 나서 제대로 푼게 맞는지 모르겠다. 시간초과 코드) n = int(input()) nums = list(map(int, input().split())) dp = [[1]] * n d = [1] * n s = 0 flag = 0 for i in range(n-2, -1, -1): for ..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 이 문제는 N을 입력 받아 길이가 N인 계단 수의 갯수를 구하는 문제이다. 문제는 이해가 갔는데 도저히 코드로 옮길 수 없어서 결국엔 또 구글링ㅋ,, 코드는 의외로 굉장히 간단했다. https://velog.io/@minchoul2/%EB%B0%B1%EC%A4%80-10844-%EC%89%AC%EC%9A%B4-%EA%B3%84%EB%8B%A8-%EC%88%98-Python [백준] 10844 쉬운 계단 수 - Python 백준 10884 쉬운 계단 수45656이란 수를 보자.이 수는 인접한 모든 자리의 차이가 ..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 드디어 구글링을 하지 않고 DP문제를 풀어내었다 ㅎㅅㅎ 근데 다른 사람들의 코드와 비교해보았을 때, 내 코드는 시간이 좀 더 걸리는 편이라.. 다른 사람의 코드를 공부해보기 위한 포스팅을 작성해보도록 하겠다. 이왕하는 김에 내 코드도 같이 리뷰해보려고 한다. 이 문제를 보자마자 백준 2579번- 계단 오르기와 굉장히 유사한 문제라고 생각했다. 결국 숫자들을 연속적으로 합하여 최고 점수를 산출해야되는..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 우르누ㅏㅓ룬아ㅜㄹ나ㅣㅜㄹ나ㅣㅜ dp계속 못 푸는중,, 코테볼라믄 이 dp를 뿌셔야되는데 내가 뿌셔지고 잇네.. 이 문제는 진짜 단순히 어떤 수를 입력받아서 1로 만들어야되는데 1로 만들 때 필요한 연산의 최소 횟수를 구하는 문제이다. 연산은 1을 빼기, 2로 나누기, 3으로 나누기 이렇게 세 종류가 있다. 너무 문제가 단순해서 오히려 더 규칙을 찾아 알고리즘화하는 것이 어려운 것 같다. 그래서 다른 분의 풀이 코드를 참고했다. https://seongonion.tistory.com/40 [백준] 1463번 1로..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 이 문제는 dp로 풀이하는건 알았는데 규칙을 못 찾아서 풀이하지 못했다. dp리스트에 각 계단까지의 최대 점수값을 구하여 넣으면 된다. 문제의 제약 조건은 다음과 같다. 1. 계단은 한 번에 한 개 or 두 개씩 오를 수 있다. => 연속해서 3개는 불가능 2. 마지막 도착 계단은 반드시 밟아야 한다. 풀이코드 리뷰) n = int(input()) st = [] dp = [0 for i in range(n)]..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 문제는 이해가 갔는데 머리쓰느라 머리가 터져버리는줄 알았지만 결국 못 풀었다,,,ㅠ 그래서 구글링을 했다ㅎ 문제는 정확하게 이해한 것 같은데 구현하기 위해 원리를 뜯어보니까 머릿 속에서 원리가 둥둥 떠다녀서 좀 힘들었다. dp는 쉬운 것 같으면서도 어렵다.. 나중에 다시 보면 또 헷갈릴 것 같아서 그림을 첨부하도록 하겠다. 맨 꼭대기 층에서 맨 아래층으로 내려오면서 합을 계속 구하여 가장 큰 합을 출력하는 문제인데, 이 또한 바로 전 포스팅에서 다룬 RGB거리 문제와 ..