본문 바로가기

알고리즘 문제/Leetcode283

[leetcode][416] Partition Equal Subset Sum 문제 : leetcode.com/problems/partition-equal-subset-sum/ 양의 정수로 이루어진 nums 배열이 주어질 때, 동일한 배열 합을 가지는 두 개의 배열로 분리시킬 수 있는지 구하라. nums 배열의 합을 구한다. 동일한 배열 합을 가질 수 있다는 뜻은 배열 합이 짝수라는 뜻이다. 따라서 만약 홀수라면 false를 반환한다. 배열 합 / 2를 nums 배열을 탐색하면서 요소들의 합으로 만들 수 있는지 판단하고 만들 수 있으면 true, 아니면 false를 반환한다. nums 배열 요소들의 합으로 sum/2 를 구할 수 있는지는 배낭 문제로 풀 수 있다. dp[i][j] = nums[0~i]개의 요소들로 부분집합을 만들 때, 그 요소들의 합으로 j를 만들 수 있는지 여부... 2020. 11. 28.
[leetcode][394] Decode String 문제 : leetcode.com/problems/decode-string/ k[encoded_string] 의 룰을 가진 문자열이 주어진다. 이 룰은 encoded_string 문자열을 k번 반복한다는 뜻이다. 룰은 중첩되서 나올 수 있다. k는 반드시 숫자이며 encoded_string에는 숫자가 포함되지 않는다. 위 룰을 적용한 문자열이 주어질 때 decode한 결과를 구하라. 괄호? => 스택. 백퍼는 아니지만 대부분의 문제에 적용된다. k와 encoded_string을 pair로 가지는 스택을 만든다. 이 때 입력 문자열을 "3[a]"라 하였을 때 이는 "1[3[a]]" 와 동일하기 때문에 코드의 일관성을 맞춰주기 위해(예외처리 덜하려고. ex. "ab3[a]" 와 같은 문자열은 초기에 나오는 a.. 2020. 11. 21.
[leetcode][116] Populating Next Right Pointers in Each Node 문제 : leetcode.com/problems/populating-next-right-pointers-in-each-node/ 같은 depth를 가진 노드들을 왼쪽에서부터 오른쪽 형제들을 각 노드들의 next 포인터로 연결한다. 노드들을 왼 -> 오 순으로 연결하기 때문에 노드들을 탐색하면서 왼쪽 자식, 오른쪽 자식 순으로 탐색해나간다. 같은 depth를 가진 노드들을 연결하기 때문에 depth를 key 값으로 하고 해당 depth들 중 가장 마지막에 탐색된 노드 포인터를 value 값으로 하는 map을 만든다. 탐색하면서 탐색 중인 노드의 depth로 가장 마지막 노드 정보를 가져와서 가져온 노드의 next 포인터에 현재 탐색 중인 노드 포인터를 넣는다. 그리고 value 를 현재 탐색중인 노드로 갱.. 2020. 11. 15.
[leetcode][310] Minimum Height Trees 문제 : leetcode.com/problems/minimum-height-trees/ N개의 노드가 있고 N-1개의 간선으로 연결된 무방향 그래프가 주어진다. 그래프는 순환 경로가 없고 모든 노드가 연결되어 있다. 노드들 중 루트 노드가 된다면 최소 높이를 가진 트리를 가질 수 있는 노드들을 구하라. 지난번에 푼 트리지름 관련 문제 참고. 임의의 지점 0 노드를 시작점으로 BFS를 한 번 돌려서 가장 멀리 있는 노드들을 가져온다. 이 노드들로 다시 한 번 BFS를 돌려서 가장 멀리있는 노드들을 가져오면 트리의 지름을 가지는 2개의 노드(let, a, b)를 알 수 있다 BFS를 만들면서 이전에 방문한 노드 번호를 저장하고 a -> b (트리 지름) 경로를 지날 때 방문하는 노드들을 임의의 배열에 저장한.. 2020. 11. 6.
[leetcode][735] Asteroid Collision 문제 : leetcode.com/problems/asteroid-collision/ 0이 아닌 정수 값을 가진 asteroids 배열이 주어진다. 요소의 절대값은 크기를 의미하고 부호는 방향을 의미한다. 같은 방향을 가지는 운석들은 부딪히지 않는다. 다른 방향을 가지는 운석들이 만날때 크기가 크거나 같은 운석들이 파괴된다. asteroids 배열에서 충돌가능한 운석들이 충돌한 뒤 남은 운석들의 배열을 반환하라. [1,2,3,4,-5] 가 주어졌을 때, -5는 4,3,2,1을 차례대로 파괴시킬 수 있고, 만약 [1,2,6,3,-5] 과 같은 운석들이 있다면 -5 운석은 3까지만 파괴시키고 6을 만나 파괴되므로 1,2 운석은 확인하지 않아도 되기 때문에 스택을 사용했다. 배열을 앞에서부터 탐색하면서 스택에 .. 2020. 10. 24.
[leetcode][133] Clone Graph 문제 : leetcode.com/problems/clone-graph/ 모든 노드들이 연결된 방향성 없는 그래프가 주어진다. 이를 깊은 복사한 트리를 생성한 뒤 반환하라. 트리 노드부터 탐색해가면서 노드를 붙여나가는 BFS 방식으로 풀었다. 생성된 노드들에 대한 정보를 저장하기 위한 map 을 추가했다. 해당 map의 key는 node.val이 고유하다고 명시되어 있기 때문에 이를 사용하고 map의 value는 Node*을 저장한다. 탐색 중인 노드의 neighbors 들 중 생성되지 않은 노드가 있다면 생성한 뒤 map에 저장, 탐색 중인 노드의 clone 노드에 생성한 노드를 neighbors로 등록. 이미 생성된 노드라면 map에서 해당 노드를 가져온 뒤 clone 노드의 neighbors로 등록하.. 2020. 10. 21.

티스토리툴바