문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 흡사 어렸을 적 수학 올림피아드(?)에서 볼 수 있을 법한 느낌의 문제다. (뭔가 낯이 익다..) 이 문제 역시 다이나믹 프로그래밍을 이용하여 쉽게 풀 수 있다. 문제의 제한사항처럼 움직일 수 있는 방향은 '오른쪽'과 '아래' 뿐이다. 따라서 해당 방향만 고려해서 풀이하면 된다. 그림과 함께 로직을 살펴보자. 풀이 방법 (0, 1)을 기준으..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 이 문제의 경우 효율성 검사가 들어가있다. 그 의미는 무엇이냐? 완전탐색이나 다중 for문과 같은 방식은 out이라는 뜻! 필자의 경우 다이나믹 프로그래밍(Dynamic Programming) 기법을 사용하였다. 다이나믹 프로그래밍이란? 다이나믹 프로그래밍이란 복잡한 문제를 간단한 여러개의 문제로 나눠 푸는 것을 의미한다. 한마디로 하나의 큰 문제를 여러개의 작은 단위로 쪼갠다는 뜻이다. 분할 정복 알고리즘(Divide and..