개인적인 알고리즘 문제 풀이 팁 기록

투 포인터

두 점을 이동하면서 하는 알고리즘인데, n^2 형식으로 나오면 별로 좋지않다. 

두 점을 어떻게 잡고 시작하느냐가 포인트인데 증가와 감소가 이루어 질 수 있도록 잡아야 한다.

1 2 3 4   배열이 있고 해당 배열의 각 2개를 뽑아서 더해서 m 값에 가깝도록 한다고 하면 왼쪽 점을 1 오른쪽 점을 4에 두고 시작하게 되면 왼쪽 점을 올리면 더한 값의 증가가 이루어지고, 오른쪽 점을 내리면 더한 값의 감소가 이루어질 것이다. 

그런데 만약 덧셈이 아니라 뺀 값이 m에 가깝도록 한다면?? 기존과 같이 왼쪽 점을 1 오른쪽 점을 4에 둔다면 왼쪽점을 증가시키면 뺀 값의 감소가 이루어지고 오른쪽 점을 감소시켜도 뺀 값의 감소가 이루어 질것이다. 

이럴 때에는 한 쪽에 두 점을 같이 놔야한다. 왼쪽 점을 1 오른쪽 점을 2로 두면 오른쪽 점을 올리면 뺀 값의 결과가 증가할 것이고 왼쪽 점을 올리면 뺀 값의 결과가 감소할 것이다. 이렇게, 두 점의 배치를 증감이 적절히 이루어지도록 잘 배치하는 것이 포인트이다.

 

트리

Tree, Node 이 2개의 클래스를 구현해서 사용해버림. preOrder, postOrder, inOrder 등은 재귀적으로 짬. 아 Tree에 Node 추가하는 부분 또한 재귀적으로 짜면 된다. dfs와 엮어서 나오는 문제가 많다.

ArrayList로 구현해야하는지도 고려해보아야함. 역으로 올라가고 뭐 그런식으로 이동하고 그런 문제면 ArrayList가 편함.

만약 이진트리이고 부모와 자식의 관계가 확실하면 Tree를 구현해서 하는 것이 좋은 것 같다. 하지만 지금까지 겪은거로는 ArrayList를 이용한 문제해결이 더 많았다.

 

분할 정복

분할 정복은 그림을 일단 크게 봐야되는 것 같다. 만약 4개로 나누는거면 해당 4개의 재귀를 보낼 수 있게끔 너무 큰 케이스면 생각하기가 어려우니깐 가장 작은 케이스에서 그 다음 케이스를 생각해서 짜면 더 쉽게 짜지는 것 같다. 그리고 기준 점을 보통 나뉘는 구간의 시작 점으로 두는 것이 일반적인 것 같다.