본문 바로가기

Wook's 개척일기234

[프로그래머스 : 레벨 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.
[프로그래머스 : 레벨 3] 단속카메라 (Java) 이번 문제는 문제 해결 방법을 위한 접근이 잘못되어서 많은 시간을 버렸다. 단속종료지점 >= 시작점 이개념으로 시작을 하긴 했지만 정렬 부분에 있어서 다른걸 정렬을 하다보니까 문제가 풀리지 않았다. 그래서 결국에 이번것도 답지를 보게 되었다. 문제를 보자. 문제 설명 고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다. 고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요. 제한사항 차량의 대수는 1대 이상 10,000대 이하입니다. routes에는 차량의 이동 경로가 포함되어 있.. 2021. 6. 15.

티스토리툴바