dp (3) 썸네일형 리스트형 [python] 백준 - 정수 삼각형(1932) 요즘 dp를 공부하기 시작하면서 백준 문제를 풀기 시작했다. 프로그래머스에서만 문제를 풀다가 오래간만에 input부터 다시 받으려 하니 은근히 헷갈리는 부분이 많다. 여하튼 오늘은 백준의 정수 삼각형이라는 간단한 dp 문제를 들고 왔다. https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 정수 삼각형은 간단하지만 dp의 개념을 잘 보여준 문제라고 생각한다. 1. 아이디어 현재 자신의 위치를 기준으로 좌상단 우상단 데이터 중 큰 데이터를 더해가며 나올 수 있는 가장 큰 값을 구하는 문제다. 2. 코드 1 2 3 4 5 6.. [python] programmers - 등굣길 요즘 DP 문제를 위주로 알고리즘 공부를 하고 있다. DP를 풀면서 느끼는 것은 재귀를 사용하면 거의 열에 아홉은 비효율적인 코드가 되는 거 같다. 오늘 문제 역시 처음에 재귀로 풀었다가 이중 for문으로 다시 풀어서 통과할 수 있었다. 우선 오늘의 문제는 프로그래머스의 등굣길로 링크는 아래 첨부하겠다. https://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 1. 실패 코드 실패한 코드는 재귀로 짠 코드이.. [python] programmers - N으로 표현 오늘의 알고리즘은 이전에 이해하지 못했던 문제와 유사한 문제였기에 ( 백준의 동전1 https://www.acmicpc.net/problem/2293 ) 해설을 찾아보면서도 이해하지 못할까 걱정을 많이 했다. 다행히 잘 정리해주신 분들이 많이 있었고 특히 아래에 기재한 블로그가 해설 이해에 큰 도움을 주었다. 참고한 블로그는 맨 밑에 기재해 놓겠다. https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 1. 아이디어 구축 문제의 핵심은 답안을 구하기 위해 과정을 하나씩 거쳐가 보는 것이 아닌 나올 수 있는 모든 수들을 저장하며 진행하는 것이다. 3개에서 나올 수 있는 결과는 1개와 2개를 경우.. 이전 1 다음
