본문 바로가기

알고리즘

매트릭스 회전시키기 leetcode 48. Rotate Image 문제풀이 문제: 주어진 행렬을 시계반향으로 90도 회전시켜라. 아이디어 회전된 행렬의 원소들이 원래 어떤 인덱스를 가지고 있었는지 관찰해보면 힌트를 얻을 수 있다. 원본 |00|01|02| |10|11|12| |20|21|22| 회전된 행렬 |20|10|00| |21|11|01| |22|12|02| 첫번째 행의 원소들은 모두 첫번째 열에서 왔다. 열과 행이 바뀌었다. 각 행의 원소들은 [2x, 1x, 0x] 역순으로 정렬되어있다. 알고리즘 원본 |00|01|02| |10|11|12| |20|21|22| 전치 행렬 |00|10|20| |01|11|21| |02|12|22| 그리고나서 각 행이 반전된 행렬 |20|10|00| |21|11|01| |22|12|02.. 더보기
뒤에서 n번째 노드 삭제하기 알고리즘 1. 포인터 hare를 n만큼 먼저 이동시킨다. 2. curr와 hare를 같은 속도로 이동시킨다. 이때 curr는 헤드에서 hare는 n번째 노드에서 출발한다. 3. curr과 hare사이에는 n개의 노드가 있으므로, hare가 뒤에서부터 1번째에 있을 때 curr는 뒤에서부터 n+1번째 노드에 있다. 그러므로 curr.next가 다음다음 노드를 가르키도록 수정하여 n번째 노드를 삭제할 수 있다. 엣지 케이스 n이 연결리스트의 길이와 같을때가 엣지케이스이다. curr의 다음 노드를 삭제하는 것이 아니라, 리스트의 첫번째 노드를 삭제해야해야한다. 길이가 n인 연결리스트의 헤드에서 n번 떨어진 곳은 null이다. 그러므로 hare가 null값인지에 따라 이를 구분할 수 있다. 복잡도 분석 시간복잡.. 더보기
서로 다른 두 연결리스트 교차점찾기 2 leetcode 160. Intersection of Two Linked Lists 문제풀이. 문제: 서로 다른 두 연결리스트가 주어졌을 때, 첫 교차점을 찾아라. 두 연결리스트의 노드 수 차이 1. 두 연결리스트의 길이를 잰다. 2. 길이차이가 있다면 그만큼 둘 중 더 긴 리스트의 포인터를 스킵한다. 3. 길이가 같은 두 연결리스트의 포인터를 같은 속도로 이동시키며 비교했을때, 서로 같은 노드가 첫 교차점이다. Time Complexity: O(A+B) Space Complexity: O(1) 이 방법으로 통과를 했으나 첫 교차점를 지난 후 노드가 서로 다를 경우를 포함하지 못한다. 더보기
서로 다른 두 연결리스트의 교차점 찾기 leetcode 160. Intersection of Two Linked Lists 문제풀이. 문제: 서로 다른 두 연결리스트가 주어졌을 때, 첫 교차점을 찾아라. Hash Set 1. A 리스트를 먼저 순회하며 hash set에 노드들을 저장한다. 2. B 리스트 순회하며 노드들이 이미 hash set에 저장되어있는지 확인한다. 이미 저장되어 있다면 해당 노드를 반환한다. 3. 무사히 B리스트 순회를 마지막 노드까지 마쳤다면, 교차되는 노드가 없다는 뜻이므로 null을 반환한다. Floyd's Tortoise and Hare algorithm 이 문제 또한 토끼와 거북이 알고리즘으로 메모리를 사용을 O(1)으로 줄여줄 수 있다. Time Complexity: O(N) Space Complexity: O.. 더보기
사이클 감지하기 leetcode 141. Linked List Cycle 문제풀이 문제: 주어진 연결리스트에 사이클이 있다면 true를 없다면 false를 반환하라 Hash Set 1. 각 노드를 set에 추가해가며 순회한다. 2. 다음에 순회할 노드가 이미 set에 들어있다면 true를 반환. 3. 순회를 무사히 마쳤다면 사이클이 없는 것이므로 false를 반환. 모든 노드를 set에 저장하려면 O(N)공간이 필요하다. set에 노드를 저장하는 것 대신, 노드의 val값에 이미 방문했음을 표시한다면 메모리를 아낄 수있다. Two Pointer 투 포인터 테크닉을 활용해서도 공간복잡도를 O(1)으로 제한할 수 있다. 투 포인터 테크닉은 한 포인터는 더 빠르게 또 다른 포인터는 더 느리게 움직이도록하는 테크닉을 말한다. .. 더보기
Sieve of Eratosthenes, 에라토스테네스의 체 에라토스테네스의 체Sieve of Eratosthenes는 2부터 n까지의 숫자 중 모든 소수prime number를 찾기 위한 간단한 알고리즘이다.1. 오름차순으로 2 부터 n까지의 모든 숫자를 set={ 2, 3, ..., n} 집합에 갖고있다.2. 아직 처리하지 않은 숫자 중 가장 작은 숫자를 선택한다.3. 해당 숫자의 배수들을 집합에서 모두 지운다. 4. 2로 돌아간다. 끝. 위의 방법으로 모든 합성수들을 집합에서 지울 수 있다. 하지만 2-4번을 N번 반복하는 코드를 작성한다면 O(n**2)시간이 걸릴 것이다. O(n log log n) 시간 걸리는 코드를 작성하기 위해서는 합성수composite number를 제거하는 동작의 중복을 줄이면된다.- 모든 합성수composite number 는 최.. 더보기
Asymptotic analysis, 점근적 표기법. 알고리즘의 성능을 분석하기위해 점근적 표기법을 이용해 시간복잡도 사용한다. 단순히 특정 입력 값에 따른 실행시간(running time)을 비교하는게 아니라, 입력값이 증가함에 따른 Running time의 rate of growth를 표현한 것이 시간 복잡도(time complexity)이다. ​ ​Big-theta Running time에 대한 점근적인 한계값을 Big theta라 한다. 즉, 알고리즘의 평균 시간복잡도를 말한다. ​Big-O 빅오는 running time에 대한 점근적인 상한값을 말한다. 즉, 알고리즘의 최악의 시간 복잡도이다. 보편적으로 ‘시간 복잡도’는 최악의 케이스를 커버하능 빅오를 말한다. ​Big-omega 빅 오메가는 running time에 대한 점근적인 하한값을 말한다.. 더보기
Binary search, 이진 탐색 리스트 A = [ 0, 1, ,2, 3 ] 이 있을 때, 마지막 원소인 '3'을 찾는다고 해보자. Simple search, 단순 탐색의 경우처음부터 순차적으로 원소 값을 확인한다. 마지막에 위치하고 있는 원소인 '3'을 찾기 위해서는 리스트의 길이와 같은 시간이 걸린다. 리스트의 길이와 같은시간을 O(n), linear time 선형시간 이라고 한다. Binary search, 이진 탐색은리스트의 중간에 있는 원소의 크기에 따라 탐색할 구간(range)를 반씩 줄여나가 O(log n), logarithm time 로그 시간이 걸리는 방식이다. 만약 100개의 원소를 가지고 있는 리스트라면 탐색할 구간이 100 에서 50, 25, 13, 7, 4, 2, 1 순으로 줄어든다. 따라서, A의 중간에 위치한 .. 더보기

티스토리툴바