본문 바로가기

코딩일기/알고리즘75

[프로그래머스 : 레벨 3] 등굣길 : Dynamic Programing(Java) 이번 문제도 DP 알고리즘을 적용하니 금방 풀리는 문제였다. 문제 자체에서 가로세로의 변수 설정 부분이 이상해서 자꾸 틀려서 한번 가로와 세로 변수를 바꾸니 금방 적용이 잘되었다. 문제를 살펴보자. 문제 설명 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = 4, n = 3 인 경우입니다. 가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다. 격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움.. 2021. 6. 17.
[프로그래머스 : 레벨 3] 정수 삼각형 : Dynamic Programing(Java) 이번 문제는 생각보다 쉬웠다. 동적계획법 알고리즘에 대해서 잘 알고 있다면 누구나 풀수 있는 문제였던것 같다. 문제부터 보자. 문제설명 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요. 제한사항 삼각형의 높이는 1 이상 500 이하입니다. 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다. 입출력 예 triangle resul.. 2021. 6. 16.
[프로그래머스 : 레벨3] N으로 표현 : Dynamic Programing 이번 문제도 풀다가 도저히 감이 잡히질 않아서 답을 검색했다. 이번 문제는 풀이를 봐도 쉽게 이해가 가질 않았는데 손코딩 + 디버깅을 하니까 이해가 갔다. (자바 이클립스 디버깅에 대해 잘 모르는 사람은 아래 링크 참고하면 될것 같다.) https://wpioneer.tistory.com/92 [Java] 이클립스 디버깅 하는 방법 소스를 짜다보면 디버깅을 해야할때가 있다. 그래서 이번엔 자바에서 디버깅을 하는 방법에 대해서 공부해봤다. 일단 어디부터 디버깅을 시작할건지를 정해야 한다. 방법은 아래와 같다. 1. 디 wpioneer.tistory.com 일단 그럼 문제부터 보자. 문제 설명 아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다. 12 = 5 + 5 + (5 / 5) + (5 / 5).. 2021. 6. 16.
[자료구조] 동적계획법 알고리즘 ( Dynamic Algorithm) 동적계획법 알고리즘은 하나의 문제를 반복해서 풀지 않고 한번만 풀도록 해주는 알고리즘이다. 동일한 문제를 풀게되는 방식의 가장 대표적인것이 분할정복 기법이 있다. 분할 정복 기법은 하나의 문제를 잘게 쪼개서 작은 문제를 해결이 완료되고 나면 return을 하여서 작은 문제들의 결과를 하나로 취합해 큰 문제를 해결해 나가는 방식이다. 퀵정렬과 같은 알고리즘에는 분할 정복 기법이 잘 적용되서 빠르게 문제를 해결해 나갈수 있지만 피보나치 수열을 구하는 문제에서 분할정복 기법이 적용되면 시간복잡도는 엄청나게 커진다. 피보나치 수열은 1, 1, 2, 3, 5, 8, 13... 이처럼 수를 구하는것이다. 그래서 맨 처음 index인 1과 2까지 재귀호출을 하면서 내려가게된다. 그런 상황에서 분할정복 기법을 사용하면.. 2021. 6. 16.