본문 바로가기

전체 글657

다이나믹 프로그래밍(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.
[leetcode][1329] Sort the Matrix Diagonally 문제 : https://leetcode.com/problems/sort-the-matrix-diagonally/ 입력으로 받은 배열의 대각선 요소들을 오름차순 정렬한 뒤 반환하는 문제 최소힙으로 풀었다. 대각선 요소들을 하나의 힙에 넣어야 한다. 인덱스 0 1 2 3 0 2 3 4 5 1 1 2 3 4 2 0 1 2 3 3x4 배열의 대각선 인덱스를 구하면 위와 같다. (구현에 따라 달라질 수 있음) 대각선 배열의 최대 크기는 n+m-1 이다. (m: 행, n: 열) mat[i][j]의 대각선 인덱스는 i+j-m-1 이다. 위 표를 보았을 때 열의 가장 아래부터 시작하기 때문에 m을 빼주었다. 1은 인덱스는 0부터 시작하기 때문에 뺐다. 따라서 n+m-1 개의 최소 힙을 배열에 저장한뒤, mat 배열을 .. 2020. 2. 15.
[hackerrank] Largest Pyramid 문제 : https://www.hackerrank.com/contests/hourrank-23/challenges/largest-pyramid/problem int arr[351][351]; //arr[i][j] : (i,j) 요소 값. (입력값) int max_down[400][351][351] = {0}; //max_down[size][i][j] : j열의 arr[i][j] 부터 arr[i+size-1][j] 중 최대 값 int max_right[400][351][351] = {0}; //max_right[size][i][j] : i행의 arr[i][j] 부터 arr[i][j+size-1] 중 최대 값 int sum[351][351] = {0}; //sum[i][j] : (1,1) ~ (i,j) 까지.. 2020. 2. 15.

티스토리툴바