[알고리즘] 이론 & 문제풀이
1.선형탐색과 이분탐색 (Linear & Binary Search Algorithm)
이진(이분) 탐색 (이하 이진탐색)은 검색 알고리즘의 기초적인 알고리즘으로 검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘이다. 이진탐색 전에 선형탐색에 대해 먼저 알아보자.
2.백준 나무 자르기 (이분탐색 )
이진탐색 개념에 이어서.. 개념 자체는 어렵지 않았는데, 문제를 접하니까 어떻게 접근을 해야 하는지 꽤 난해하다.자연을 사랑하는 상근이가 필요한 만큼만 M미터의 나무를 가져갈 수 있도록, 절단기 높이를 설정하는데 도와주자.
3.하노이의 탑 (재귀)
하노이의 탑은 '작은 원반 위에 큰 원반을 올릴 수 없다'는 규칙을 가지로 원판을 다른 막대로 전부 옮기는 게임이다. 알고리즘으로는 재귀함수의 좋은 예제가 된다. 프로그래머스, 백준 하노이의 탑 문제 풀이
4.N-Queen (DFS)
일단 너무 만만하게 봤다. DFS인줄도 모르고.. 퀸즈갬빗을 재밌게 보고, 체스판만 보고 고른 문제라서.퀸은 자기가 위치한 행, 열, 대각선으로 움직일 수 있다. 어떤 퀸도 다른 퀸을 잡지 못하도록 배치해야 한다.즉, n * n 체스보드에
5.트리 & 이진탐색트리 (BST)
뒤집힌 나무 사진일반적인 트리 구조트리는 노드로 이루어진 데이터 구조이다. 노드들 사이에 부모와 자식 관계를 가진 가지(branch)가 있다. 한 가지에서 여러개의 노드가 0~n개의 노드를 가질 수 있다. 알고리즘의 트리 데이터 구조를 알아보자.
6.백준 javascript 입력받기 (readFileSync | readline)
14681|사분면 고르기 제출하는 과정에서 평소 사용하던 fs readFileSync가 런타임 에러 (EACCES)가 나서 readline 적어둡니다. vs code에서 테스트를 실행할 수 있는 확장 runner도 메모해 둡니다.
7.백준 고양이, 개, 새싹 만들기 \ 특수문자 escape sequence
난이도를 보고 가벼운 마음으로 시작했는데 생각보다 똑같이 작성하기 어려웠다. escape sequence \\ 를 정확하게 입력하는 것이 포인트였다! 보통은 \\n처럼 키보드로 표현하기 힘든 특수 문자열을 입력할 수 있다. 몇가지 기록.
8.백준 색종이 만들기 javascript
2630. 색종이 만들기 항상 정방형으로만 자르기 때문에 시작좌표 (r, c)와 사이즈 N을 전달하여 범위 안에 색종이가 색깔에 상관없이 모두 동일한지 확인한다. 만약 범위 안의 색이 동일하지 않으면 N / 2로 범위를 줄여 4분면을 재귀적으로 반복한다.
9.아스키ASCII 코드 ↔️ 문자열 치환 javascript
✏️ 아스키코드에 관해서는 예전에 CRLF 문제 해결에서 잠깐 알아본 적이 있다. 그 외 백준 알고리즘 hashing과 대소문자 바꾸기 문제를 풀면서 둔다.
10.First Bad Version (이분 탐색)
이분탐색으로 절반씩 전체 배열을 검사하여 가장 처음으로 생긴 bad version을 찾는다.
11.53. Maximum Subarray 알고리즘 DP (Brute-force, Kadane's)
모든 부분 배열의 합을 비교하는 완전 탐색(Brute force)로 문제를 풀었는데, DP(Kadane 알고리즘)로 푼 해설을 보고 비교해보았다.
12.Search Insert Position (이분 탐색)
278\. First Bad Version "First Bad Version"에 이어서 이분탐색 응용코드는 이전 이분 탐색 코드이다.
13.배열의 요소를 제곱하고 정렬하기 (Two pointer - O(n))
앞서 이분탐색 중 배열의 모든 요소를 탐색하는 방법이다. left와 right 인덱스 포인터를 하나씩 옮겨가면서 numsleft의 제곱한 값과 numsright의 제곱한 값 중 더 큰 값을 새로운 배열인 result에 추가한다.
14.정렬된 배열에서 더해서 target이 되는 두 요소의 index 찾기 (Two pointer)
이미 정렬되어 있는 배열의 두 수 합이 target이 되는 두 요소의 인덱스를 찾는 문제이다.인덱스는 1-based, 1부터 시작하므로 결과 배열에서 1씩 더해주면 된다.
15.k범위 만큼 배열 뒤집기 (Two pointer - O(n))
계속해서 Leetcode의 two pointers과 관련된 문제들을 풀고 있다. 문제를 보자마자 k만큼 pop(), unshift()를 반복하는 방법이 떠올랐지만, 속지.. 않았다 start, end 포인터를 활용하여 k만큼 reverse 한다.
16.N번째 노드 제거하기 (Linked List, Two pointer)
링크드 리스트에서 끝에서 `n`번째 노드를 삭제하는 문제이다. 단 한 번 순회하여야 하고, 전체길이를 모른채 `n`번째 노드를 삭제하기 위해 두 포인터를 이용한다.
17.백준 A+B 큰 수 더하기 (javascript)
다국어로 된 문제인데, 폴란드? 언뜻보면 돌려보면 단순한 사칙연산 같지만 큰 수 연산에 대한 문제이다. 5,000 자릿수까지 올 수 있기 때문에 javascript에서 number의 범위를 벗어나 문자열로 처리하여 해결하였다.
18.부분 문자열(substring) 구하기, Sliding Window
3. Longest Substring Without Repeating Characters 주어진 문자열에서 중복되지 않는 가장 긴 부분 문자열의 길이를 반환한다.
19.DFS, 색깔 칠하기 (floodFill) 알고리즘
기본적인 DFS 알고리즘을 이용하는 문제이다. 시작점 i와 j가 주어지고 이웃한 상하좌우를 탐색하여 동일한 색상을 업데이트한다. 이웃한 모든 셀을 방문할 때까지 재귀적으로 탐색한다.
20.가장 큰 섬 찾기 Max Area of Island (DFS)
어떤 섬이 가장 큰 면적을 가지고 있는지 구하는 문제이다. DFS로 섬을 탐색하여 면적을 계산하고 maxArea에 저장된 값 중 가장 큰 값을 반환한다.
21.각 노드의 next 포인터 채우기 (Tree)
116. Populating Next Right Pointers in Each Node 완전 이진 트리에서 next 포인터에 동일 레벨의 인접한 다음 노드를 추가하는 문제이다. 트리는 언제 나와도 당혹스러운 것 같다. 반복해서 익숙해지는 수 밖에..
22.큐(queue) 인접한 정점으로 범위를 넓히며 탐색하는 BFS
각 셀마다 상한 오렌지, 신선한 오렌지, 빈 칸이 주어진다. 매 분이 지날 때마다 상한 오렌지에서 4방향으로 인접한 신선한 오렌지가 감염된다고 가정할 때 인접한 모든 오렌지가 상할 때 걸리는 시간(분)을 구하는 문제이다.
23.Spiral Matrix 회오리 모양으로 2차원 배열 탐색하기 (구현)
좌표를 잡을 때 면적이 아닌 바둑판처럼 점을 기준으로 보면 이해가 쉽다. 회오리 모양으로 반복하기 위해서 다음 규칙을 반복한다. m*n의 매트릭스가 주어질 때 회오리 모양으로 숫자를 반환하는 알고리즘이다.
24.배열에서 더해서 target이 되는 두 요소의 index 찾기 (Two Sum)
정렬되어 있지 않은 배열의 두 수 합이 target이 되는 두 요소의 인덱스를 찾는 문제이다.이중 for문으로 찾을 수 있지만, 문제에는 O(n^2)보다 나은 시간 복잡도라는 조건이 있다.
25.정렬된 두 배열 합치기 O(m+n)
정렬된 두 배열nums1, nums2을 nums1에 병합하는 문제이다. 둘 중 한 배열은 최종적으로 병합될 m + n의 length를 가지고 있고, 나머지는 0으로 채워진다.
26.링크드 리스트에 사이클 찾기 (플로이드의 토끼와 거북이 알고리즘)
링크드 리스트에 사이클이 존재하면 사이클의 시작노드를 반환하고, 사이클이 존재하지 않는다면 null을 반환하는 문제이다. 주어진 링크드 리스트에 사이클 유무를 알기 위해서 일명 토끼와 거북이 알고리즘을 사용한다.
27.가장 긴 회문(Palindrome) 문자열 구하기 (그리디)
앞으로 읽으나 뒤로 읽으나 동일한 문자열을 펠린드롬(palindrome), 회문이라고 한다. 주어진 s문자열을 이용하여 가장 긴 회문을 반환하는 문제이다.
28.전위순회 (preorder Traversal) 트리 순회 알고리즘
전위 순회(preorder)는 다음과 같은 방법으로 진행한다.노드를 방문한다.왼쪽 서브 트리를 전위 순회한다.오른쪽 서브 트리를 전위 순회한다. 전위 순회는 깊이 우선 순회(depth-first traversal)라고도 한다.
29.스도쿠 알고리즘 valid sudoku (1)
스도쿠는 즐겨하는 게임이어서 코드로 접근하는 것도 재밌었다. 2차원 배열의 9*9 배열이 주어진다. 스도쿠의 기본 룰에 따라 1*9 가로줄, 9*1세로줄, 3*3서브 박스에 1-9까지 숫자가 한번씩만 들어간다.
30.레벨순회 (lever-order Traversal) 이진트리 순회 알고리즘
레벨 순서 순회(level-order)는 모든 노드를 낮은 레벨부터 차례대로 순회한다. 레벨 순서 순회는 너비 우선 순회(breadth-first traversal)라고도 한다.
31.유효한 이진 탐색 트리인지 확인하기 (재귀 접근 방식)
이진 트리의 루트가 주어지면 유효한 이진 검색 트리(BST)인지 확인한다. 1. 왼쪽 자식 노드는 부모 노드의 값보다 작아야 한다. 2. 오른쪽 자식 노드는 부모 노드의 값보다 커야 한다. 3. 왼쪽 및 오른쪽 하위 서브트리도 모두 이진 검색 트리여야 한다.
32.섬의 갯수 찾기 (DFS)
200. Number of Islands 200. Number of Islands 문제 테스트 케이스 풀이 변수 'islandCounts'로 섬의 갯수를 카운팅한다. 반복문으로 셀을 방문하면서 1(육지) 또는 0(바다)인지 확인한다. 육지를 발견했으니 islandCounts를 하나 증가시킨다. 발견한 육지(일부)를 시작으로 dfs를 반복해 상하...
33.n까지 k 자릿수 조합 만들기 (재귀)
1부터 n까지 k자릿수 수열만들기 문제이다. 수열 문제는 처음에 접근하기가 쉽지 않았는데, 여러 문제를 풀면서 공식을 익히니까 조금씩 눈에 들어오는 것 같다.
34.n개 요소 순열 permutation 찾기 (재귀)
입력받은 nums 배열의 요소의 모든 순열을 생성하기 위해서 재귀적으로 permuted 함수를 호출한다. 1부터 n까지 k자리수까지 조만들기 문제 응용해서 접근해 보았다.
35.대소문자 구분한 문자열 경우의 수 찾기
입력값 s 문자열에 대해 대소문자 구분하는 모든 문자열 조합을 찾는 문제이다. 모든 조합을 찾는 문제이므로 dfs를 쉽게 연상할 수 있었고, 숫자와 문자를 구분하여 문자열일 경우 upperCase와 lowerCase 각각 dfs를 호출한다.
36.계단 오르기, 타일링 DP 기초 문제 dynamic programming
한번에 1단 혹은 2단으로 올라갈 수 있을 때, n단까지 오를 수 있는 모든 방법을 구하는 문제이다. 가장 기초적인 DP 문제이며 비슷한 문제로 타일링, 피보나치 문제 등이 있다. 각 스텝을 오를 수 있는 방법의 수를 저장할n+1
37.연속되지 않은 집, 가장 많이 훔치기 (DP, greedy) 알고리즘
거리에 집들이 나란히 있다. 문제는 인접한 집을 연속해서 털면 경보시스템이 작동하여 자동으로 구속된다. 첫번째 집에서 마지막 집까지(경찰에 알리지 않고) 훔칠 수 있는 최대 금액을 구하는 문제이다.
38.삼각형 탑에서 최소 경로 합계 구하기
주어진 triangle 삼각형의 상단에서 하단까지의 최소 경로 합계를 계산하는 문제이다. 행 triangle 에 해당하는 dp 배열을 생성하고 첫번째 행은 초기화한다.
39.javascript 2진수 ↔ 1진수 변환, 비트 연산자로 2의 거듭제곱 수인지 확인하기
반복문이나 재귀를 사용하지 않고 n이 2의 거듭제곱인지 확인하는 문제이다. 만약 거듭제곱이라면 그 수의 2진수는 예를 들면, '10', '100', '1000'과 같은 형식으로 변환된다. 만약 n이 2의 거듭제곱이라면 n-1은 n의 반전된 비트이다.