짱아의 개발 기록장

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..

간단한 배열 문제였다. [메인 로직] 배열을 처음부터 탐색해서 target값과 같거나 큰 값을 찾으면 break하면 된다. 단, 그러한 값을 못 찾았을 경우는 target이 배열에 존재하는 값들보다 큰 경우이기 때문에 idx+1을 해주어야 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public: int searchInsert(vector& nums, int target) { int idx = 0; bool check = false; for(int i=0; i

아마 기업에서 출제할 수 있는 가장 정석적인? dp문제가 아닐까 생각된다. 그렇게 쉽지도 어렵지도 않은? 적당한 난이도의 문제이다. [메인 로직] (i, j)에서는 dp[i][j-1]과 dp[i-1][j]와 각각 자신의 원래 값 grid[i][j]을 더한 것 중 더 작은 값을 dp값으로 저장해둔다. 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 class Solution { public: int dp[201][201] = {0, }; int minPathSum(vector& grid) { int m = grid.size(); int n = grid[0].size(); for(int i=0; i

62번 문제의 연장선인 dp문제이다. [메인 로직] 이해를 돕기위해서 그림을 그려서 첨부해보았다. 일단, 보석이 0행쪽에 있거나, 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 32 33 34 35 36 37 38 39 40 41 42 class Solution { public: int dp[101][101] = {0, }; int uniquePathsWithObstacles(vector& obstacleGrid) { int m = obstacleGrid.size(); i..

전형적인 dp문제이다! 백준에도 아마 이러한 문제가 많았던 걸로 기억한다. [메인 로직] (i, j)를 기준으로, (i-1, j)와 (i, j-1)에서 온 경로를 더해주면 된다. 장애물이나 이런 것이 없기 때문에 다른 예외처리도 딱히 필요없다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public: int dp[101][101] = {0, }; int uniquePaths(int m, int n) { for(int i=0; i

기본적인 Tree의 높이를 확인한느 문제였다. Tree는 bfs, dfs로 모두 풀 수 있는데,,, 문제의 분류가 bfs길래 bfs로 풀이해보았다! [메인 로직] node의 right, left부분이 모두 NULL일때가 그 node가 leftNode라는 것을 의미한다. 따라서, 그 때 높이를 측정해주었다. bfs일 경우 너비 우선탐색을 하기 때문에 먼저 발견된 leftNode가 가장 최소의 높이를 가진 노드일 수밖에 없다. 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 Solution { public: queue q; int MinLevel = INT_MAX; int minDept..