본문 바로가기

Computer Science/알고리즘

 (19)
[파이썬 알고리즘 인터뷰] 19. 가장 긴 동일 값의 경로 1. 문제 LeetCode 687. Longest Univalue Path 이진트리 root 가 주어지면 같은 값으로 이어진 경로 중 가장 긴 경로의 길이를 리턴하여라. 2. 풀이 dfs 방식을 이용해서 풀었다. 함수가 노드를 인자로 받으면 현재 노드부터 아래로 이어지는 같은 값을 가진 노드 경로 길이를 state에 저장해 리턴한다. 또한 클래스 변수 longest를 만들고, 경로를 탐색하는 중 가장 긴 경로가 새롭게 등장하면 longest의 값을 업데이트했다. 우선 리프노드가 state가 0을 가지게 하기 위해서 현재 노드가 존재하지 않는다면 -1을 리턴한다. 그리고 왼쪽/오른쪽 자식 노드에 대해 재귀호출을 실행하고, 그 결과로 return된 state 값을 right, left 변수에 저장한다. 모든..
[파이썬 알고리즘] 18. 순열 1. 문제 leetcode 46. Permutations 서로 다른 정수를 입력받아 가능한 모든 순열을 리턴하라. 2. DFS를 이용한 풀이 이 문제는 재귀 dfs로 그래프를 탐색하여 풀 수 있다. 그래프는 []을 루트 노드로, [1,2,3], [2,1,3] 등 각 순열을 리프 노드로 삼고, 중간의 노드는 각 순열이 만들어지는 과정([1,2] 등)으로 가진다. DFS 함수의 인자로는 지금까지 만들어진 순열을 넣는 path, path에 아직 순열에 추가되지 않은 candidates를 준다. 주어진 수를 모두 순열에 사용해서 candidates가 남아있지 않다면, 지금까지 만든 순열인 path를 결과에 추가한다. 만약 순열 path에 추가할 candidates가 남아 있다면 남아있는 숫자를 모두 넣어서 DF..
[파이썬 알고리즘 인터뷰] 17. 전화번호 문자 조합 1. 문제 leetcode 17. letter combinations of a phone number 2에서 9까지 숫자가 주어졌을 때 전화번호로 조합 가능한 모든 문자를 출력하라. 숫자와 문자의 관계는 다음과 같다. 2. DFS를 이용한 해결 방법 이 문제는 하나의 경로로 탐색을 시작하면 해당 경로로 탐색을 마쳐야 한다. 따라서 DFS(깊이 우선 탐색)를 사용해야 한다. def letterCombinations(self, digits: str) -> List[str]: def dfs(index, path): # 끝까지 탐색하면 백트래킹 if len(path) == len(digits): result.append(path) return # 입력값 자릿수 단위 반복 for i in range(index, ..
[파이썬 알고리즘] DFS와 BFS를 이용한 그래프 탐색 1. 그래프란? 연결된 객체 간의 관계를 표현하는 자료구조 그래프 G(V, E)는 어떤 자료나 개념을 포함하는 정점의 집합 V(vertex)와 이를 연결하는 간선의 집합 E(edge)로 구성된다. 정점(node, vertex): 여러 가지 특성을 가질 수 있는 객체 간선(Edge): 정점 사이의 관계 2. 그래프의 표현 방식 1) 인접 리스트: 딕셔너리를 이용해 출발 노드를 키로, 도착 노드를 값으로 저장하는 방식 실제 연결된 노드에 대한 정보만 저장하기 때문에 공간을 덜 차지한다. 특정 두 노드를 연결하는 간선이 있는지 확인하기 위한 시간이 오래 걸린다. 2) 인접 행렬: i에서 j로 향하는 경로가 있다면 matrix[i][j] = 1, 없다면 0으로 설정하는 방식 많은 공간을 차지하지만, 원하는 경로..
[파이썬 알고리즘] 16. 페어의 노드 스왑 1. 문제 leetcode 24. swap nodes in pairs 한방향 연결리스트가 주어지면 인접한 모든 두 노드의 방향을 바꾸어 바뀐 리스트의 head를 리턴하여라. 2. 반복을 이용한 풀이 이 문제를 해결하기 위해서는 인접한 두 노드 간의 포인터 방향만 바꾸면 안된다. 앞에 있던 노드가 가리키는 포인터 방향도 바꾸어야한다. 포인터 세개를 관리하면서 반복문을 통해 문제를 해결할 수 있다. 먼저 head 뒤 노드를 b, 앞 노드를 prev라고 지정한다. 그리고 b가 head를 가리키고, head는 b 다음의 노드를 가리키도록 한다. 원래 head를 가리키던 prev는 p를 가리키도록 한다. 마지막으로 다음 비교를 위해 head, prev를 뒤로 한칸씩 옮긴다. 이 과정을 두 개 이상의 노드가 남아 ..
[파이썬 알고리즘] 14. 역순 연결리스트 1. 문제 leetcode 206. Reverse linked list 한방향 연결리스트 head가 주어지면, 이를 뒤집어서 리턴하여라. 2. 반복을 이용한 내 풀이 현재노드 head, 이전노드 prev를 이용해 리스트의 끝까지 탐색하며 연결의 방향을 바꾸었다. 먼저, head 뒤 노드를 가리키는 포인터 prev를 만든다. 그리고 리스트가 종료되어 head가 None이 될 때까지 prev와 head를 한칸씩 앞으로 옮기며 리스트를 탐색한다. 동시에 이전에 prev에 있었던 노드를 현재 앞으로 옮겨진 prev가 가리키게 하며 리스트 연결의 방향을 바꾼다. 리스트 탐색이 종료되면 뒤집어진 리스트의 시작부분인 prev를 리턴한다. 이 방법으로 실행속도와 메모리 사용량 모두 상위 1.56%를 달성하였다. 3. ..
[파이썬 알고리즘 인터뷰] 13. 두 정렬 리스트의 병합 1. 문제 leetcode 21.Merge two sorted list 두개의 오름차순으로 정렬된 연결리스트 list1, list2가 주어진다. 두 리스트를 오름차순으로 정렬된 하나의 연결리스트로 만들어 리턴하여라. 두 리스트를 이루고 있는 노드들을 이용해야한다. 2. 연결리스트를 하나씩 탐색한 풀이 먼저 두 리스트 맨 앞에 값을 비교하고 작은 값을 sort 포인터로 가리킨다. sort로 가리킨 리스트는 리스트 포인터를 다음 노드로 옮긴다. 둘 중 어떤 한 리스트가 끝나면 반복을 종료한다. 그리고 남은 다른 리스트의 노드들을 sort에 연결시킨다. 3. 재귀함수를 이용한 풀이 책에서는 재귀함수를 이용해서 간결하게 문제를 풀었다. 별도의 포인터나 연결리스트를 만들지 않고 list1에 합친 연결리스트를 만들..
[파이썬 알고리즘 인터뷰] 12. 팰린드롬 연결리스트 1. 문제 leetcode 234. palindrome linked list 한방향 연결리스트의 head가 주어지면, 주어진 연결리스트가 팰린드롬(뒤집어도 내용이 변하지 않음)이면 True를 리턴하여라. 주어진 한방향 연결리스트는 다음과 같다. 2. 연결리스트를 배열로 바꾸어 풀기 팰린드롬 여부를 확인하기 위해서는 양쪽에서 탐색을 동시에 진행할 수 있어야한다. 한반향 연결리스트는 양방향 탐색이 어렵기 때문에 연결리스트를 배열로 바꾸어 풀었다. 먼저 연결리스트의 값을 저장할 배열 arr을 만들었다. 그리고 연결리스트가 끝날때까지 head.next로 리스트를 탐색하며 head.val을 arr에 추가했다. 마지막으로는 arr을 뒤집은 arr[::-1]이 arr과 같은지 여부를 리턴한다. 3. 런너를 활용한 풀..

티스토리툴바