짱아의 개발 기록장

String문제였는데 여기에 DP를 가미한... 근데 글쓴이는 DP로는 도저히 풀이방법이 생각나지 않고 다른 정답코드를 봐도 이해가 잘 되지 않아..서 BFS코드를 참고해서 풀었다. [메인 로직] String+BFS로 풀었다. 맨처음 큐에 0을 넣어주고 for문으로 맨 뒤 idx부터 현재 idx까지 역순으로 탐색하며 팰린드롬이 되는 지 확인한다. 만약 팰린드롬이 완성된다면 큐에 해당 idx를 넣어주었다. 이 과정을 반복! 한 레벨이 반복될 수록 cuts가 1씩 늘어나는 것! 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 class Solutio..

LCS와 매우 유사한 유형이다.. LCS와 Edit Distance모두 2차원 DP를 이용한다? 그리고 전체적인 로직 부분이 매우 유사합니다. 다만! LCS는 공통된 부분을 찾으면 +1을 해나가는 로직이지만, Edit Distance는 공통된 부분을 찾으면 그냥 놔두고 공통되지 않은 부분이 나오면 오히려 insert, delete, replace작업을 해주어야 하기 때문에 +1만큼 더해준다. 사실 처음에는 어떻게 풀지 감이 오지 않아서...ㅎㅎ 유투브를 참고해서 풀었다. www.youtube.com/watch?v=b6AGUjqIPsA&feature=youtu.be 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 clas..

[메인 로직] false (2) -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 false인 경우는 특정 숫자가 계속적으로 반복되는 현상이 일어난다. 즉, 사이클이 생기는 경우는 거짓이라고 판별하는 알고리즘을 구현하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 // 반복되는지 살펴보기..visit 처리 class Solution { public: map m; bool isHappy(int n) { do{ string s = to_string(n); int num = 0; for(int i=0; i

간단한 구현문제였다. 0이 있는 곳을 기준으로 4방향으로 탐색해서 모든 값들을 0으로 만들어주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution { public: int dx[4] = {-1, 1, 0, 0}; // 위, 아래, 왼, 오 int dy[4] = {0, 0, -1, 1}; int visited[201][201] = {0, }; void setZeroes(vector& matrix) { int n = matrix.size(); int m = matrix[0].size(); for(int i=0; i

중첩된 범위를 가지는 부분을 하나로 합쳐주는 문제였다. [메인 로직] 가장 핵심 부분이, 만약 [Start, End]로 구성된 배열이 있을 때, End값보다 작거나 같은 Start값을 갖는 또 다른 배열이 있다면 2개의 배열을 합쳐서 하나의 배열로 만들 수 있다. ex) [2, 4], [3, 6]이라면 4>=3이기 때문에 [2, 6]으로 만들 수 있다. 또한, [2, 5], [3, 4] => [2, 5]이기 때문에 합쳐진 후의 End값은 두 배열의 End값중 큰 값으로 정해지는 것도 고려해야 한다! (내가 틀렸던 부분...^^) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 class Sol..

C언어를 처음 배울 때 익혔던? 달팽이 알고리즘이다.ㅎㅎ 오랜만에 풀어봐서 좋았닼ㅋㅋ 근데 이 풀이 방법이 사실 for문을 4번써서 간단하게 해결하는 방법도 있지만... 편한대로 풀었다. 방문배열을 통해 이미 방문한 좌표인지를 확인했고 범위를 벗어나거나 이미 방문한 좌표일 경우에는 방향을 바꾸도록 했다. 그래서 오, 아래, 왼, 위, 오, 아래...이런식으로 4방향이 계속적으로 반복되는 형식으로 달팽이 알고리즘이 진행된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution { public: vector generateMatrix(int n) { i..

[메인 로직] idx1, idx2, idx3으로 2, 3, 5각각의 인덱스를 설정해주었다. 1을 먼저 배열에 넣어준 뒤, 1*2, 1*3, 1*5 각각의 값중 가장 작은 값을 그 다음 값으로 넣어준다. 그 후, 배열의 맨 뒤의 값과 2, 3, 5각각을 곱한 값이 같다면 해당 인덱스를 한 칸씩 이동해주었다. 아무래도 코드를 참고하는게 더 이해가 빠를 것 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public: int nthUglyNumber(int n) { if(n==1){ return 1; } int ans = 0; int idx1 = 0, idx2 = 0, idx3 = 0; vector v;..

간단한 String문제였다. [메인 로직] 각 자리수의 합이 2이상이라면 next변수에 1을 넣어서 넘겨주고 2을 뺀 남은 값을 계속 문자열에 붙여주었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 class Solution { public: string addBinary(string a, string b) { int idx1 = a.size()-1; int idx2 = b.size()-1; int next = 0; string s = ""; while(idx1>=0 || idx2>=0){ int x=0, y=0; int temp = 0; if(idx..