백준링크: 바로가기 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net #그리디 알고리즘 #정렬 일단 접근방법은 맞았고 IntelliJ 결과값도 잘 나왔는데 백준 런타임 에러 가 4번 떠서 당황한 문제. 원인은 문제해결과 무관한 코드 입력 때문이었다(a.k.a 쓸모없는 코드입력이나 접근방법은 배제하라 아님 에러를 주겠어) 요즘 유튜브로 DP(다이나믹 프로그래밍)을 공부해서 최소값과 현재 배열 index 전까지의 총합을 구하는 부분이 타일링이나 피보나치와 유사하다고 생각해 dp[] 배열을 만들어서 total을 구했다. = (런타임 에러 구덩이로 ..

문제링크: 바로가기 #DP(다이나믹 프로그래밍) 피보나치 함수는 다양한 유형으로 백준 문제에 출제된다. 이전 재귀함수를 활용한 제일 기초적인 피보나치 함수는 풀어보았는데 이번 문제는 간단한 설명임에도 접근방법이 어려웠다. 결국 해결하지 못했지만, 다음 번엔 꼭 성공하리라 다짐하면서 간략한 복기를 해본다. 친절하게 피보나치 함수 코드를 제공해준다. 물론 본 문제를 내기 위한 참고설명일 뿐이지만. 피보나치 특성 상 재귀로 연산을 중복/반복하게 되는데 fibonacci(0)과 fibonacci(1)이 각각 몇 번씩 출력되는지를 구하면 된다. 앞선 타일링 문제에서 적용한 DP(다이나믹 프로그래밍)을 사용해야겠단 것은 알았으나 출력을 어떻게 잡아(catch)줘야할지 꼬인 실타래가 끝내 풀리지 않았다. 다수 블로그..

문제링크: 바로가기 # 그리디 알고리즘 # 정렬 스터디 과제로 풀었다가 틀린 문제인데, 스터디원이 다 맞았는데 왜 틀린지를 모르겠다고 피드백 줬었다. 12일 후인 오늘 그리디 알고리즘 연습삼아 복습 겸 풀어봤다. 구글링한 부분은 Array.Sort를 Reverse, 즉 내림차순으로 하는 부분이다. Collection과 Comparator 인터페이스를 사용하면 된다. 유의할 점은 data type을 primitive(ex.int)가 아닌 객체로 지정해줘야 한다는 것이다. (ex.Integer) 그리고 이번에도 보기만 해도 짜증이 나는 틀렸습니다! 가 떴는데 그 이유를 알아냈다. 받을 수 있는 팁 최대값 변수 data type을 int로 선언했기 때문이다. 이놈의 함정은 내가 문제를 제대로 못 읽고 파악 못..

DP(Dynamic Programming) - 동적 프로그래밍 데이터 값들을 배열에 저장해 필요할 경우 빼서 사용할 수 있는 알고리즘 피보나치 때 썼던 재귀함수와 비슷하지만 트리가 하위 Degree로 내려가면서 이미 했던 연산을 중복 연산하지 않고 점화식 배열에 저장해 둔 값을 꺼내어 쓴다. 따라서 시간 복잡도가 줄어들며 메모리를 적게 쓸 수 있다는 장점이 있다. 문제 풀이 접근방식인 동적 프로그래밍을 처음 봤고 방식을 도출하지 못해 나동빈 알고리즘 강의 유튜브를 참고했다. 그럼에도 점화식 이해를 못하여 황진경코딩영재학원 채널에서 동일한 올림피아드 문제를 설명해주신 영상을 보고 난 뒤에 완전히 이해할 수 있었다. 점화식은 dp[n] = dp[n-1] + dp[n-2] 이다. 주어진 타일 형태는 1x2, ..