짱아의 개발 기록장

간단한 배열 문제였다. [메인 로직] 배열을 처음부터 탐색해서 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..

오우.. 이런 ListNode로 푸는 문제가 c++로는 익숙하지 않아서 힘들었다. 말 그대로 연결리스트의 특성을 잘 살려서 구현하면 된다! [메인 로직] 각 노드의 값을 합하고 나머지는 dummy노드에 넣어주고 몫은 다음으로 넘겨준다. ListNode만 익숙하다면, 계산하는 과정을 그닥 어렵지 않다. 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: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { bool check = false; ListNode* dummy = new ListNode(); ListNo..

LeetCode에서 전에 이런 문제를 풀었던 기억이?... Merge Sort을 할때에 두 개로 나눈 배열을 합병하는 과정을 그대로 구현하면 된다. 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 43 44 class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { // int idx = 0; ListNode* dummy = new ListNode(); ListNode* curr = dummy; if(l1==NULL || l2==NULL){ if(l1==NULL){..

String을 다루는 문제였다. [메인 로직] map을 사용하여 각각의 문자열을 정렬한 결과와 같은 문자열들을 하나의 vector에 넣어 분류해주었다. aet -> ["eat", "tea", "ate"] ant -> ["tan", "nat"] ... 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 class Solution { public: map m; vector ans; vector groupAnagrams(vector& strs) { ans.resize(strs.size()); int idx = 0; for(int i=0; i