2020/0215 동전 교환(CC: Coin Change) 동전 교환(CC: Coin Change)은 다이나믹 알고리즘 중 하나입니다. CC는 동전의 종류들로 특정 금액을 만드는 경우의 수를 구하는 알고리즘입니다. 예를 들어서 1원, 2원, 5원, 10원 4가지 종류의 동전으로 10원을 만드는 경우의 수를 구해보겠습니다. 동전의 가치는 cost 배열에 넣었다고 생각하겠습니다. 즉, cost[] = {0, 1, 2, 5, 10} 입니다. 모든 경우의 수를 구하기 위해서는 2차원 배열이 필요합니다. d[i][j] = i가지 종류의 동전을 사용해서 j금액을 만드는 모든 경우의 수 입니다. 따라서 우리가 구하고자 하는 경우의 수는 d[4][10]이 됩니다. 이제 배열을 채워봅시다. 0행은 0원으로 j금액을 만드는 경우의 수라고 생각하변 됩니다. 0금액을 만드는 방법은 .. 2020. 2. 23. [codeup][3740] 0/1 배낭 문제(Knapsack Problem) 문제 : http://codeup.kr/JudgeOnline/problem.php?id=3740 다이나믹 프로그래밍 DP의 대표 문제 중 하나인 물건을 넣느냐 빼느냐를 선택하는 0/1 배낭문제. 물건의 개수가 N이고 배낭에 담을 수 있는 최대 무게가 W이다. 물건은 종류별로 1개씩 있다. d[i][j] = 물건을 i번째 까지 배낭에 넣는다고 가정했을 때, 무게 j를 초과하지 않으면서 배낭에 넣을 수 있는 물건들의 가격의 총합의 최대값 d[i][j] = d[i - 1][j] (j = w[i]인 경우, i번째 물건을.. 2020. 2. 22. 다이나믹 프로그래밍(Dynamic Programming) 다이나믹 프로그래밍은 동적계획법이라고도 불리며 짧게 DP라고 많이 사용합니다. DP의 중점은 "작은 문제를 해결하고 이를 이용해 큰 문제를 해결하자 / 큰 문제를 작은 문제로 쪼개서 해결하자."입니다. DP를 배우지는 않으셨더라도 피보나치 수를 재귀로 구하는 방법은 한번쯤 들어보셨을 거라 생각합니다. 이를 DP를 사용하는 방법으로 한 번 바꿔보겠습니다. int fibo(int n){ if(n==1 || n==0) return n; return fibo(n-1) + fibo(n-2); } 일단 기존 방법의 재귀 소스코드는 위와 같습니다. 4번째 피보나치 수를 구하려면 위와 같이 함수를 호출하게 되는데 2번째 피보나치 수를 구하는 함수를 중복해서 호출하게 됩니다. 2번째 피보나치 수는 상황에 따라서 변하는 .. 2020. 2. 22. [hackerrank] Grid Challenge 문제 : https://www.hackerrank.com/challenges/grid-challenge/problem NxM 배열이 주어지면 각 열이 사전 순 배열이 될 수 있는지 판단하는 문제. 같은 행에 있는 문자들은 순서를 변경할 수 있다. 각 열을 사전순으로 배열한 후 같은 행에 있는 문자들이 사전순으로 정렬되어 있는지 판단하면 된다. 각 열을 사전순으로 배열한다면 a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 c4 d1 d2 d3 d4 a1 b2여서 2번째 열이 사전순 배열이 안되어 a2보다 작은 a1을 a2대신 사용한다고 하더라도 b1.. 2020. 2. 22. [hackerrank] Sherlock and Anagrams 문제 : https://www.hackerrank.com/challenges/sherlock-and-anagrams/problem 입력 문자열의 부분문자열들 중 애너그램 문자열이 되는 문자열 pair 개수를 구하는 문제. 애너그램이 될 수 있는 문자열들은 길이가 서로 같아야 하므로 먼저 길이가 같은 부분 문자열들을 구한다. 그리고 구한 부분 문자열을 오름차순 정렬한뒤 map에 저장한다. map의 key는 정렬된 문자열이고 value는 key가 나온 횟수이다. 즉, "mom"이 입력 문자열로 주어지고 길이가 2인 부분 문자열을 구했을 때, ["mo", "om"] 이 나오고 각 문자열들을 오름차순 정렬하면 ["mo", "mo"] 가 된다. 이를 map에 넣으면 map에는 1개의 요소가 저장되고 이는 "mo".. 2020. 2. 16. CGV 겨울왕국2 포토티켓 이벤트 굿즈 도착 도차악. 도착한지는 꽤 됐는데, 그때의 감정을 되새기면서 이제서야 적는 언박싱 포스팅 열면 위와 같은 종이가 한 장 있다. 요걸 치우면 감동 포스터가 생각보다 크진 않았다. 홀로그램이다. 반짝반짝하다. 빨리 큰 집으로 이사가서 벽에 장식해두고 싶다. 배지랑 스티커도 있다. 왼쪽 아래 나사는 전용 액자 만들때 사용된다. 그러고보니 아이맥스 관람권 1장도 있었던 것 같은데 어디뒀는지 기억이 안나네 스티커는 아까우니까 서랍에 고이 모셔두고 배지는 핀 콜렉션에 꽂아두었다. 마지막으로 요 판때기가 왔는데, 첨엔 선이 그어져 있어서 당황했다. 스티커 같이 붙어져 있어서 포토티켓 위치 다 맞추고 떼버렸다. 나사까지 다 조이고 나서 세웠는데 포토티켓이 안에서 고정이 안되고 돌아다녔다. 알고보니 박스에 붙어서 온 이 테.. 2020. 2. 16. 이전 1 2 3 다음
