# 문제 풀이

Array
---
1. Array: O(N^2) 걸리는 문제 O(N) 으로 끝내는 방법

### 문제 1) 부분 배열의 최대합 (leetcode | 53)
- 배열에 음수 ~ 양수의 값이 있을 때, 어떤 부분 배열이 최대합을 나타내는지 알 수 있을까?
- 일반적으로 모든 배열의 조합을 보기 위해서는 I 번째 값이 있을 때 j = I ~ len(arr)-1 까지를 살펴보면서 모든 합을 구한다. 하지만 Kandane's algorithm 을 사용하면 O(N) 시간에 끝낼 수 있다. 어떻게 가능할까.
- -1 3 4 -10 9 가 있다고 하면 부분 배열의 최대합은 얼핏 봤을 떄 9 이다.
- 일단 maxsum 값을 두고,
1) 현재 값이 maxsum보다 크면 현재값부터 새로운 부분 배열을 시작한다
2) 만약에 그렇지 않으면 부분 배열을 현재값 포함해서 연장을 한다

maxsum = -inf
Maxsum -1 < -1 : -1 로 maxsum 을 업데이트
Maxsum = -1 + 3 < 3 : 3 을 maxsum 으로 업데이트
Maxsum = 3 + 4 > 4: maxsum 에 4를 포함해서 연장 7
Maxsum = 7 - 10 > -10 maxsum 에 -10을 포함해서 연장 -3
Maxsum = -3 < 9 : 9를 maxsum 으로 업데이트

### 문제 2) two sum (leetcode | 1)
- Target 값이 있고, 배열의 두 원소의 합이 target 인 pair 를 찾는 문제이다. 여기서 target 값에 해당하는 pair 는 하나만 있다고 가정한다.
- Naïve 한 접근 방법으로는 I 와 j = i+1 ~ len(arr)-1 의 각 원소를 loop 돌면서 target 값과 비교를 해본다. 만약에 같으면 그 pair 를 반환하면 된다. 이런 경우 O(N^2) 의 시간이 소요되는데, (정확히는 O(N(N-1)/2)) 이것도 O(N)으로 끝내는 방법이 있다. 어떻게 가능할까? 전체 배열을 탐색하면서 값이 존재한다고 표시를 해놓는다. 그리고 다시 한번 배열을 탐색하면서 target 값에서 i번째 있는 값을 뺐을 때 차이가 존재하는지 여부를 확인하면 된다. 조금 더 최적화 시키면, 처음 배열을 순회할 때, 차이가 존재하는지 확인하면서 값을 넣으면 어떨까.
- -1, 3, 4, -10 ,9 가 있을 때, target 이 13 이라고 하면 13 과 -1, 3, 4 를 빼보고, diff 값이 존재하면 그 diff 의 위치와 현재 인덱스 위치를 반환하면 되고, 만약에 그렇지 않는 경우 존재한다에 표시해놓고 index 도 같이 저장해놓으면 된다. 답이 항상 존재한다고 가능했을 때 N 개의 배열을 모두 탐색하기 전에는 항상 pair 를 찾을 수 있다.

### 문제 3) string에서 중복된 character가 존재하지 않는 가장 긴 substring
- 문자열이 주어졌을 때, 반복되지 않는 가장 긴 문자열은 무엇일까? 예를 들어, abcabcbb 가 있을 때, abc 가 가장 긴 문자열임을 알 수 있다.
- Naïve 하게 접근하는 방법으로는 모든 가능한 문자열을 구해서, 각각이 반복되는 문자가 존재하는지 체크를 한다. 그리고 반복되는 문자가 없는 문자열 중에서 가장 긴 문자열을 구한다. 이렇게 되면 O(N^2)의 시간이 소요되어서 모든 문자열을 구할 수 있고, 그들을 또 탐색하면서 O(N^2) 이 걸리고 최종적으로 그 중 가장 긴 길이를 구하는데 시간이 소요된다.
- 이것을 O(N) 의 시간으로 줄일 수 있는 방법이 없을까 생각을 해봤다. 반복되는 문자가 등장한 위치 다음에서 부분 문자열을 다시 찾아야 하기 때문에, 그 index 를 알고 있어야 한다. 그래서 pos 라는 dict 변수를 갖고 항상 문자의 위치를 기억해야한다. 그리고 중복되는 문자가 발견되면 이전에 등장했던 위치부터 현재 위치까지 substring 을 다시 초기화해주고 (또는 len 을 업데이트 해주고) 다시 새로운 문자열을 찾으러 가야한다.
- 근데 여기서 하나 걸리는게, 중복된 문자라고 하는 부분이 매번 중복된 문자가 있는지 체크하는 과정이 낭비인 것 같다. String 안에 존재하는지 체크하는 것이 아니라 O(1) 시간안에 체크할 수 있는 방법은 없을까? 그러면 중복이 발생한 경우 후보 문자열의 시작 ~ 중복 문자열의 위치까지 있는 문자들은 모두 not visited 로 초기화 시켜줘야하는데 이걸 어떻게 빨리할 수 있을까?
- 솔루션 중 하나는 pos 를 저장하는데, 이 pos 가 지금 현재 윈도우 안에 있는지를 체크해야한다, 윈도우 안에 있으면 중복된 것이라고 판단할 수 있고, 윈도우 밖에 있으면 중복되지 않은 것이라고 판단할 수 있다. 이것을 구현하기 위해서 left 와 right 의 포인터를 사용하고 right 는 마지막 값의 + 1 인덱스를 가리킨다고 생각하면 된다. Left 는 substring 의 첫번째라고 볼 수 있다. 만약에 중복되는 값이고, left 와 같거나 큰 위치에 있으면, 중복이라고 판단하고 처리한다. 만약에 그렇지 않은 경우, 항상 right 를 하나씩 증가시켜주고 현재 c 의 pos 를 지금 idx 로 체크해준다. (코드를 보면 깔끔하게 정리된 것을 볼 수 있다. 이거 너무 많이 틀려서 잊지 말아야 하는 문제임)

Tree, Graph
---

### 문제 1) BST 노드 간 최소 거리 (leetcode | 783)
- 이 문제는 너무 어렵게 생각했었는데, 생각해보면 간단한 내용이었던 문제이다. 최소의 거리라고 하는 것 j 와 j+1 간 거리가 최소인 것을 의미한다. 정렬된 형태라고 봤을 때, 인접한 노드의 거리를 비교해야지 최소가 되는 것이고, j 와 j+2 가 더 클 순 없다. 그래서 bst 노드를 inorder 순으로 방문하면서 이전 노드와 비교하면서 min 값을 찾으면 된다

### 문제 2) 전체 노드가 zero 로 가도록 graph 방향을 바꾸는 문제 (leetcode | 1466)
- 이 문제는 문제의 틀을 깨고 생각하는데 도움을 주는 문제이다. 처음에 생각했을 때는 복잡하게 생각했는데, 단방향 그래프라고 해도, 시작은 zero 에서 하는 bi-direct 문제로 바꿔서 생각하면 되는 문제였다. 대신 이게 연결되어있는지 연결되어있지 않는지 checker를 표시해서 연결되어있는 경우에는 count 를 늘려주는 방법을 생각하면 됐다. 가끔 복잡한 문제를 간단히 생각하는 방법도 중요한 것 같다

### 문제 3) 최대 importance 합이 되도록 importance 를 부여하고, 그 총합을 구하는 문제 (leetcode | 2285)
- 이 문제는 그래프에서 degree 에 대한 이해를 높일 수 있는 문제이다. 총 importance 를 높일 수 있는 방법은 가장 많은 degree 를 갖고 있는 노드가 가장 높은 점수를 갖고 있으면 된다. 따라서 이 문제는 degree 순서대로 정렬을 먼저 하면 된다. 근데 여기서 동일한 degree 를 갖는 건 어떻게 처리를 하면 좋을지에 대한 고민이 생긴다. 이 부분은 전체 결과에 어떤 순서여도 상관없는 것으로 보인다. 따라서 간단히 생각해서 풀면 되는 문제였다.

### 문제 4) Pseudo palindrome path (leetcode | 1457)
- 이 문제는 DFS 개념과 palindrome, 그리고 Bit manipulation의 개념을 활용하여 깔끔하게 구현해낼 수 있는 방법이다. 다른 문제와의 특징은, 주어진 tree 의 path 의 순서는 중요하지 않고, path 안에 있는 요소의 조합을 통해서 palindrome 이 나오면 palindrome 이라고 인정한다.
- 일단 하나의 path 를 먼저 구해서 palindrome 인지 확인해야하므로 가장 빨리 path 를 구할 수 있는 DFS 를 사용하기로 한다. 그리고 각 노드를 방문할 때마다 배열을 사용하는 것이 아니라 bit 를 활용해서 배열을 deepcopy 해야하는 불편함을 없앨 수 있다. 어떻게 하면 path의 노드를 하나의 값에 저장해서 관리할 수 있을까?
- 이러한 트릭이 가능한 이유는 노드가 가지는 값이 1~9 사이를 가지기 때문이다. Dfs 안에서 이 값이 들어오면 1 을 그 수의 비트만큼 (최대 9bit) 왼쪽으로 shift 한다. 그리고 기존에 있는 path 와 XOR operation 을 한다. 그리고 그 노드가 leaf 노드일 때, path & path-1 계산을 해서 만약 0 이라고 하면 palindrome 이라고 판단하고 그렇지 않으면 palindrome 이 아니라고 판단한다.

- 예를 들어보면, 2-1-1 이라는 path 가 존재할 때, path = 0 부터 시작한다.

0^(1 << 2) 를 하면, 0^4 = 4
4^(1 << 1) 을 하면, 4^1 = 5
5^(1 << 1) 을 하면, 5^1 = 4

- 최종 결과 4 와 4-1 을 and 처리하면 결과는 0. 따라서 palindrome 이다
- 이 원리는 다음과 같다. Digit 의 frequency 가 짝수면 최종 결과는 0이 나온다는 것이다. 즉 path 값이 0 이기 때문에 0^-1 을 하면 0 이 나온다. 만약에 하나의 digit만 홀수면 path 는 2^x 의 값을 가지게 된다. 따라서 path & (path-1) = 0 를 하면 0이 된다.
- 이러한 방식을 `Bitmask` 라고 부르는데, Btmask 에 대해서 좀 더 알아보자.

> 출처: https://jooncco.com/algorithms/bitmask/
> 유의사항
1) Bit operation 보다 등호 및 부등호 연산이 더 먼저 수행되기 때문에 괄호를 잘 써줘야한다
2) Overflow 를 조심하자

#### 활용사례: 집합의 표현
- N 개의 아이템이 있다고 할 때, 각 bit 는 그 set 이 존재하는지 존재하지 않는지를 나타낸다. 이 값이 최대 32개를 넘지 않으면, 32 bit 크기의 int 형 변수를 하나 선언해서 사용할 수 있다. 위의 예시의 경우 숫자는 1~9 사이의 값을 가지기 때문에 9개의 아이템을 가진 하나의 집합으로 표현할 수 있다. 예를 들어, 101001110 인 경우 (2,3,4,7,9) 가 존재한다고 볼 수 있다.
- 집합에 원소가 존재하는지 확인하는 방법
- 9번째 item 이면 set & 1 << 9`
- 집합의 원소 계산
- 비트를 하나씩 오른쪽으로 shift 하면서 1의 개수를 세준다.
- 그러면 이 문제에서 하는 것은 같은 값이 나오면 XOR 로 없애버리는거다! 만약에 palindrome 이어서 짝수개가 있으면 위에 말한대로 최종 값은 0 이 될 것 이고, 하나의 digit 에 하나의 bit 만 있으면 1을 빼준 후 and operation 을 하면 된다. 1을 빼는 것은 bit 관점에서는 어떤 일이 발생하는걸까?
- A = 7, B = 6 이라고 하면

111 과 110. 두 개를 and 하면 2개의 bit 110 이 된다 (원래의 값이 3개의 bit 이 있음)
100 과 011 을 and 하면 0 이 된다 (원래 값이 1개의 bit 만 있음)
010 과 001 을 and 하면 0 이 된다 (원래 값이 1개의 bit 만 있음) 

### 문제 5) 링크드 리스트에서 최대의 twin sum 을 찾는 것 (leetcode | 2130)
- 이 문제는 Singly Linked List를 reverse 하게 순회할 수 있냐의 문제이다. 일반적으로 Linked List 를 reverse 하기 위해서는 doubly 로 구현되어 있는 경우 쉽지만, Singly 인 경우는 이야기가 달라진다. Singly Linked List 를 reverse 하는 방법은 three pointer 와 two pointer 방법이 있다. Three pointer 방법의 경우 prev, curr, next 3 가지의 포인터를 사용해서 curr.next 가 prev 를 가리키도록 직관적으로 작업할 수 있다. 하지만 이것은 two pointer 로도 동일하게 구현할 수 있는데, 아이디어는 curr 와 next 두 개면 구현할 수 있다. 먼저 각각의 역할을 보면, curr 는 계속 같은 위치에서 curr.next 만 next 를 위해서 사용된다. 그리고 head 가 실제로 움직이는 현재 노드의 포인터와 같은 역할을 하고 next 는 말그래도 현재 노드의 다음 노드가 된다. 한 회차에서는 먼저 next 값을 curr.next (저장된 next) 값으로 업데이트 되고, curr.next 를 다시 next.next 로 업데이트 한다. Next의 다음 값은 head 값으로 설정하고, head 는 next 로 업데이트 한다. 이렇게 되면 head 는 하나씩 움직이는 노드가 되고 curr.next 는 head 다음 노드를 계속 갖고 있고, 매 회마다 현재 노드 다음의 노드 포인터를 현재 노드를 가리키도록 한다.
- 예를 들어, 1->2->3->4->5 가 있다고 가정하자. 위 방식대로라면 curr = 1, head = 1 이다. Curr.next 가 None 이 아닐 경우 next = 2 가 된다. 먼저 next 의 next 를 curr.next 로 하면 curr,next 는 3을 가리키고, next.next 를 head 를 가리키도록 하면 1<-2 3->4->5 그리고 1->3이 된다. 그리고 head 를 next 로 업데이트 해주면 curr =1 , head = 2, next = 3 이 된다. 이런 방식으로 하면 최종 결과는 역순이 된다!
- 이 문제를 푸는 2번쨰 아이디어는 어디가 중간 노드냐는 것이다. 즉 중간이 어딘지 파악하고, 중간 다음 노드는 reverse 할 것인데, mid 를 파악하는 방법은 slow 와 fast 변수를 사용하는 것이다 fast 와 fast.next 값이 존재할 때까지 fast 는 2 step씩 이동, slow 는 1 step 씩 이동하게 되는데, slow 가 멈추는 순간이 mid 가 된다. Slow 가 mid 라고 하면 slow.next 부터는 위의 방법으로 reverse 하면 된다. 그리고 mid 전의 노드와 mid 다음의 노드를 더하면서 최대합을 찾으면 된다.

### 문제 6) Symmetric Tree (leetcode | 101)
- 이 문제는 recursion 을 활용해서 간단히 풀 수 있는 문제인데, 너무 어렵게 생각해서 문제 푸는데 오랜 시간이 걸렸던 것으로 기억하고 있다. 문제는 tree 를 반으로 갈랐을 때 서로 대칭이냐 하는 것이었다. 이 문제를 풀기 위해서 BFS 로 풀면 빈 노드에도 dummy 를 넣어서 같은 레벨에 있는 노드들이 palindrome 한지 비교해보면 됐다.
- DFS 로 비교하는 방법은 어떘을까? 코드가 더 심플했던 것으로 기억하는데 아예 하나의 recursion 안에 mirror 위치에 있는 노드를 던져버리는 것이다. 그리고 그 값이 같을 때 sym 이라고 판단하고 그렇지 않은 경우에는 false 를 return 종료되는 지점은 두 node 가 None 일 때까 끝나는 지점