🎯 위상 정렬이란? 은 순서가 정해져 있는 작업을 차례로 수행해야할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다. 가장 이해하기 쉬운 예로는 게임 캐릭터 키우기(?)가 있다. 예를 들어 주먹으로 때리기는 맨 처음에 배우는 기본 스킬이다. 하지만 몸통 박치기는 주먹으로 때리기라는 스킬을 배워야만 배울 수 있는 스킬이다. 또 고함 지르기 역시 주먹으로 때리기를 배워야만 익힐 수 있는 스킬이다. 필살기는 몸통 박치기와 고함 지르기를 모두 익혀야만 배울 수 있는 스킬이다. 이러한 흐름은 조건을 걸어줘서 해석할 수 있다. 한마디로 모든 일에 순서 제약이 걸려있는 셈이다. 은 사이클이 존재하지 않는 방향 그래프여야 한다는 전제조건이 있다. 사이클이 발생하면, 시작점이 없기 때문에 위상 정렬을 수행할 수 없기 때문이다. 🎯 위상 정렬 구현하는 법 (JS) 위상 정렬을 수행하는 알고리즘은 를 이용하여 구현하 수 있다. 모든 관계는 그래프화가 되어 있다고 가정한다. 해당 노드에 연결되는 들…

🎯 LIS(최장 증가 부분 수열) 원소의 개수가 N개인 배열이 있다고 가정을 해보자. 배열의 원소 index는 변하지 않는 조건 하에 각 원소가 이전 원소보다 큰, 그 길이가 최대인 부분 수열을 이라고 한다. 🎯 이분탐색을 활용한 LIS LIS 알고리즘을 구현하는 방법은 여러가지가 있지만 을 이용한 방법은 효율적으로 구현할 수 있다. 일반적으로 이분탐색은 O(logN)에 탐색이 가능하기 때문에 LIS를 구현하는 문제에서는 O(NlogN)의 시간복잡도로 문제를 해결할 수 있다. 위 이분탐색을 이용하여 LIS를 구하는 코드는 아래와 같다. 🎯 실제 LIS에 해당하는 배열 구하기 위 방법은 LIS의 길이를 구하는 방법이다. 따라서 실제 해당 길이에 포함되는 배열을 구하고 싶을 때는 추가적인 작업이 필요하다. 위에서 살펴봤던 LIS를 구하는 과정처럼 LIS 배열과 Record라는 배열을 생성한 후 LIS 배열에는 기존 과정을, Record라는 배열에는 LIS 몇번 째 배열에 값이 입…

🔠 알파벳을 사용해야 하는 경우 💡 JS에서 복사본 배열을 만들고 기존 배열을 유지하는 경우 ⏰ 시간초과가 발생할 것 같다면…? 시간초과가 발생할 것 같다면 코드를 뜯어 고치기보다는 하게 생각하는 습관을 갖자. 특히 이중 반복문 또는 삼중 반복문을 사용해야하는 경우라면 을 사용하는건 어떨까? 정말 중요한 포인트이다. 🔠 알파벳을 사용해야 하는 경우 💡 JS에서 복사본 배열을 만들고 기존 배열을 유지하는 경우 ⏰ 시간초과가 발생할 것 같다면…?

🎯 투포인터 는 두개 또는 그 이상의 포인터를 두고 값들을 비교하여 문제를 해결하는 알고리즘 패턴을 의미한다. 예를 들어 특정 숫자들이 들어있는 배열이 주어졌을 때, 배열 안에 숫자 합이 0이 되는 값 2개를 새로운 배열에 담아 리턴하는 함수를 만들어보자. 위 방법은 가장 흔한 방법이다. 이중 for문을 사용하여 두 값의 합이 0인 경우를 찾아서 리턴하면 해결할 수 있는 문제이다. 배열의 길이가 짧으면 상관이 없겠지만 이중 for문을 사용하기 때문에 시간 복잡도가 O(n^2)이라는 점이 불편하다. 이때 시간 복잡도를 O(n)에 해결할 수 있는 것이 이다. 위 예시에서는 시작 인덱스(p1)와 마지막 인덱스(p2) 2개를 정한다. p1과 p2의 합을 구한다. 만약 0이면 새로운 배열에 넣는다. 0보다 작으면 p1을 한칸 올리고, 0보다 크면 p2를 한칸 내린다. p1과 p2가 같아질 때까지 반복한다. 🎯 코드 구현 (JS) 👉 문제 확인하기 : 프로그래머스 - 숫자게임 🎯 투포인터 🎯…

🎯 슬라이딩 윈도우 만약 [1, 2, 3, 4, 5, 6, 7]로 이루어진 배열에서 연속적인 3개의 숫자의 합의 최댓값을 구하는 문제를 마주했다고 가정해보자. 만약 반복문을 통해서 처음 3개, 그 다음 3개, 그 다음 3개… 이렇게 계속 구하다보면 시간초과가 발생할 가능성이 높다. 이럴 때 알고리즘을 사용한다. 먼저 처음 배열 [1, 2, 3]의 합을 구한다. 다음 배열 [2, 3, 4]를 구하는데 [1, 2, 3] 배열에서 맨 앞의 값이 빠지고, 그다음 값인 4가 들어온 모습이다. 이러한 규칙을 바탕으로 다음 배열의 값은 전 배열에서 처음 원소를 빼고 다음에 들어올 원소를 더해주면 된다. 결과적으로 는 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘을 의미한다. 🎯 코드 구현 (JS) 👉 문제 확인하기 : BOJ - DNA 비밀번호 🎯 슬라이딩 윈도우 🎯 코드 구현 (JS)

트리와 관련된 알고리즘은 알고리즘 준비하기 - 이진 트리와 이진 순회 글을 확인하면 된다. 하지만 해당 포스트에서 다룰 내용은 전위 순회, 중위 순회, 후위 순회 배열 중에서 2개가 주어졌을 때 다른 하나의 순회를 찾는 방법이다. 순회와 관련된 내용에서 의문이 있으면 위 포스트를 확인했으면 좋겠다. 👉 문제 확인하기 : BOJ - 트리 위 문제에서는 전위 순회, 중위 순회 값이 주어지고 후위 순회 배열을 찾는 문제이다. 가장 좋은 방법은 직접 전위 순회와 중위 순회를 트리 형태로 그림을 그려가며 규칙을 찾는 것이 좋다. 우선 스택 하나를 생성한다. 초기값으로는 왼쪽부터 전위순회 시작점, 전위순회 종점, 중위 순회 시작점, 중위 순회 종점이다. 스택이 비어있을 때까지 반복문을 진행할 것이다. 흐름은 BFS와 비슷하다. 가장 중요한 것은 루트 노드를 먼저 발견하는 것이다. 비록 구하고자 하는 후위 순회에서 루트는 가장 나중에 배열에 입력되기는 하지만 루트 노드를 기준으로 왼쪽과 오른쪽…

🎯 분할 정복을 통한 피보나치 수열의 이해 👉 문제 확인하기 : BOJ - 피보나티 수 6 문제를 확인해보면 n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. 우리가 흔히 아는 F(N+2) = F(N+1) + F(N) 공식을 적용한다면 n이 너무 크기 때문에 시간초과가 발생한다. 저 공식 말고는 마땅히 생각나는 공식이 없었다. 구글의 도움을 받으려고 하니 행렬을 이용한다면 피보나치 수열 문제를 빠르게 해결할 수 있었다. 만약 2의 N제곱의 값이 2의 A제곱 + 2의 B제곱이라고 한다면 N = A+B로 나타낼 수 있다. 이와 같은 원리를 위 그림에 적용해보자. [[F(N+1), F(N)], [F(N), F(N-1)]]과 같은 행렬은 [[F(A+1), F(A)], [F(A), F(A-1)]] + [[F(B+1), F(B)], [F(B), F(B-1)]]로 만들 수 있다. 그리고 이제부터 구하고자 하는 값이 홀수일 때와 짝수일 때로 나뉠 수 있는데 먼저 …

🎯 벨만 포드 알고리즘은 유향 그래프에서 최단 경로를 계산할 때 이용되는 알고리즘이다. 하지만 의문이 든다. 이전 포스트에서 유향 그래프 최단 경로를 계산할 때 알고리즘을 사용한다고 했었기 때문이다. 하지만 벨만 포드 알고리즘이 다익스트라 알고리즘과 가장 큰 차이를 보이는 곳은 이다. 다익스트라 알고리즘은 벨만 포드 알고리즘과 동일한 작업을 수행하지만 실행속도는 더 빠르다. 그렇다면 똑같이 최단 경로를 구하는 알고리즘인데 왜 가중치가 음수일 때 벨만 포드 알고리즘을 사용해야 할까? 이 질문에 답으로 아래와 같은 그래프를 한번 살펴보자. 만약 위 그래프에서 시작 노드가 2인 경우를 생각해보자. 만약 4에서 2로 가는 가중치가 양수이고, 다익스트라 알고리즘을 사용했을 경우 2 - 3 - 4를 순회하고 절대 2로 다시 돌아가지 않는다. 왜냐하면 가중치 합의 최소값이 2 - 3 - 4 이후에는 갱신될 수 없기 때문에 큐에는 노드 4가 남는다. 하지만 4에서 2로 가는 가중치가 음수…

🎯 팰린드롬 상당히 어려운 부분이었다. 우선적으로 이야기하자면 은 어떤 문자가 뒤집어도 대칭이 유지되는 것을 의미한다. 예를들어 ‘A’, ‘AA’, ‘ABCBA’가 팰린드롬에 해당된다. 👉 관련 문제 확인하기 : BOJ - 팰린드롬? 이것을 구현하기 위해서는 2차원 DP배열을 활용해야 한다. 순서는 상관이 없지만 i 인덱스를 문자열의 시작점, j 인덱스를 문자열의 종점이라고 둔다면 DP[i][j]는 문자열의 i번째부터 j번째까지의 팰린드롬 유무를 확인하는 작업이라고 생각하면 편하다. 여기서 주의해야할 점은 문자의 길이가 1일 때, 문자의 길이가 2일 때, 그리고 이상일 때, 총 3가지로 분류해서 DP배열에 값을 넣는 작업을 해주면 된다. 문자의 길이가 1일 때: 팰린드롬이 무조건 가능하다. 문자의 길이가 2일 때: 두글자 모두 동일한 경우에만 팰린드롬이 가능하다. 문자의 길이가 3일 때: 첫글자, 마지막 글자가 같은 경우에, 그리고 그 두 글자를 제외한 안에 있는 문자가 팰린드롬이…

알고리즘 문제를 풀다보면 트리 관련해서 이진 트리 혹은 이진 트리 순회 문제도 많이 확인할 수 있지만 그래프의 지름을 구하는 문제도 종종 확인할 수 있다. 👉 문제 확인하기 : BOJ - 트리의 지름 🎯 트리의 지름 트리의 지름 문제는 간략하게 설명하자면 하나의 노드부터 가장 멀리 떨어져있는 노드의 거리를 계산하는 문제이다. 하지만 가장 멀리 떨어져있다고 해서 트리의 leaf를 의미하는 것은 아니다. 보통 간선의 가중치를 알려주기 때문에 하나의 노드에서부터 연결된 모든 노드의 가중치의 합이 가장 큰 값이 해당 트리의 지름인 셈이다. 결과적으로 트리도 그래프와 같이 를 활용하여 최대한 갈 수 있을만큼 가며 가중치를 계산하는 방식으로 구하면 된다. 단, BFS는 최단 거리를 구할 때 많이 사용되기 때문에 이 문제에서는 DFS를 이용해야 한다. 모든 노드를 반복문을 이용하여 순회하는 것은 시간초과가 발생할 확률이 높다. 아니 거의 100% 시간초과가 발생한다. 여기서 1번 노드부터 가장…

🎯 트리 트리는 계층적인 자료를 표현하는 데 사용되는 자료구조이다. Node tree의 각 요소를 노드라고 한다. B를 A의 자식 노드, A를 B의 부모 노드라고 한다. 각 Node는 자신의 데이터를 가지고 있으며, 자식 노드의 주소를 가지고 있을 수도 있다. Root Node A와 같이 부모 노드가 없고 최상단에 위치한 Node를 루트 노드라고 한다. Leaf Node H, I, E, J, G처럼 자식 노드가 없는 노드를 Leaf Node라고 한다. Size 모든 Node의 갯수를 크기라고 한다. Depth Root Node로부터의 거리를 깊이라고 한다. 🎯 이진 트리 자식 노드의 갯수가 최대 2개로 한정된 tree를 말한다. 최대 자식 노드 갯수가 2개인 것 뿐이므로 위 그림에서 G노드가 없어도 이진 트리이다. 🎯 이진 탐색 트리 이진 탐색이 동작할 수 있도록 고안된 자료구조의 일종이다. 왼쪽 자식 노드가 부모 노드보다 작고 오른쪽 자식 노드가 부모 노드보다 큰 이진 트리를…

🎯 다익스트라 다익스트라 알고리즘은 하나의 시작 지점으로부터 모든 다른 지점까지의 최단 경로를 찾는 알고리즘이다. 다익스트라 알고리즘은 기본적으로 그리디 알고리즘으로 분류된다. ‘매번 경로의 길이가 짧은 노드를 선택하는 과정’을 반복하기 때문이다. 🎯 다익스트라 알고리즘의 과정 시작 정점을 설정하고, 시작 정점의 거리 값을 0으로 설정한다. 시작 정점을 제외한 모든 정점의 거리 값을 무핟내로 설정한다. 현재까지 방문하지 않은 정점 중에서 출발점에서 가장 가까운 정점을 선택한다. 해당 정점의 이웃 정점에 대해서, 출발점에서 해당 이웃 정점까지의 거리를 계산한다. 계산된 거리가 해당 이웃 정점의 현재 거리 값보다 작다면, 해당 이웃 정점의 거리 값을 갱신한다. 모든 정점을 방문할 때까지 위 과정을 반복한다. 🎯 다익스트라 알고리즘 구현 다익스트라 알고리즘은 을 사용하여 구현한다. 우선순위 큐를 사용하면 구현이 더 빠르고 간단해진다. 큐에서 뽑힌 정점은 해당 정점에서부터 가장 짧은 거리…

🎯 우선순위 큐 우선순위 큐를 구현할 때 내부적으로 최소 힙 또는 최대 힙을 이용한다. 최소 힙을 이용하는 경우 ‘값이 가장 낮은 데이터가 먼저 삭제’되며, 최대 힙을 이용하는 경우 ‘값이 큰 데이터가 먼저 삭제’된다. 이때 힙은 삽입과 삭제에 O(NlogN)의 시간 복잡도를 가진다. 🎯 힙의 특징 힙의 부모와 자식 간에 다음과 같은 관계가 성립한다. 왼쪽 자식의 index : 부모의 index * 2 + 1 오른쪽 자식의 index : (부모의 index * 2) + 2 부모의 index : Math.floor((자식의 index - 1) / 2) 🎯 삽입 연산 (bubbleUp) 의 삽입 연산은 다음과 같은 단계로 이루어진다. Heap의 마지막 위치에 요소를 추가한다. 새로운 요소를 추가한 위치에서부터, 부모 노드와 새로 추가된 노드의 값을 비교한다. 만약 새로 추가된 노드의 값이 부모 노드의 값보다 작다면, 부모 노드와 새로 추가된 노드의 위치를 교환한다. 이전 단계에서 교환…

🎯 LCS 알고리즘 알고리즘은 최장 공통 부분수열(Longest Common Subsequence), 혹은 최장 공통 문자열(Longest Common Substring)을 의미한다. 문자열 하나하나 모두 비교를 하다보면 시간복잡도가 최대 O(n^4)이 되기때문에 DP를 이용하는 것을 추천한다. 🎯 최장 공통 문자열 구하기 최장 공통 문자열을 구하는 과정은 상당히 쉽다. 최장 공통 부분수열을 구하기 이전에 다루고 가면 도움이 될 것 같아서 정리를 해보고자 한다. 문자열A와 문자열B를 한글자씩 비교한다. 두 문자가 다르다면 LCS[i][j]에 0을 표시한다. 두 문자가 같다면 LCS[i-1][j-1] 값을 찾아서 해당 값보다 +1한 값을 LCS[i][j]에 넣는다. 위 과정을 이중배열 끝까지 반복한다. 위 과정이 공통 문자열을 구하는 것에서 성립되는 이유는 공통 문자열은 문자가 모두 연속되어야 하는 특성때문이다. 현재 두 문자가 같을 때 두 문자의 앞글자까지가 공통 문자열이라면 계…

우선 DP 알고리즘의 기본 개념은 알고리즘 준비하기 - 다이나믹 프로그래밍에 잘 정리해두었으니 참고하면 좋을 것 같다. 👉 문제 확인하기 : BOJ - 평범한 배낭 🎯 배낭문제 다이나믹 프로그래밍 (DP) 문제 중 대표적인 유형이 바로 0/1 배낭 문제이다. 물건의 개수 N이 주어지고, 배낭이 최대로 버틸 수 있는 무게 K가 주어진다. 각 물건의 무게와 가치가 주어질 때 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 구하는 문제가 바로 배낭 문제이다. 그 중에서 0/1인 이유는 물건을 쪼개서 넣을 수는 없고 물건을 넣거나, 혹은 넣지 않거나 둘 중 하나의 선택만 할 수 있기 때문이다. 문제를 인용해서 설명을 해보도록 하자. 물건의 개수(N)는 4개, 배낭의 무게(K)는 7이다. 물건1 물건2 물건3 물건4 무게 6 4 3 5 가치 13 8 6 12 물건의 개수가 4개라서 브루트포스 알고리즘으로 구하더라도 짧은 시간내에 구할 수는 있으나 물건의 개수가 조금만 더 늘어난다면 따져보…

👉 참고할 문제 : BOJ - IOIO 🎯 KMP 알고리즘 백준 브론즈 - 실버 문제를 접할 때 정말 많이 나오는 유형이 문자열 문제이다. 문제의 길이도 짧고, 직관적으로 이해가 가는 문제였기 때문에 어렵게 느껴지지도 않는다. 하지만 메모리 초과나 시간 초과가 무조건 한번씩은 발생한다. 특히 Node.js로 문제를 해결하고자 할 때 문자열을 다루는 내장함수 , , 가 존재하기 때문에 시간복잡도가 문자열 길이의 곱에 비례하여 O(NM)이 된다. 시간복잡도가 O(NM)인 것을 O(N+M)으로 줄일 수 있는 알고리즘이 바로 이다. 이 KMP 알고리즘의 핵심 키워드는 패턴을 정의해서 했던 비교를 또 하지 않는다. 이다. 💎 패턴을 관리하는 Failure 배열 만들기 우리에게는 검색의 대상이되는 문자열(origin)과, 찾아야하는 패턴의 문자(keyword), 추가적으로 KMP를 위해 추가되는 개념인 이 존재한다. 예를 들어 origin은 전체 길이가 16인 ‘aabcacabcabcacab…

우선 BFS 알고리즘의 기본 개념은 알고리즘 준비하기 -BFS 에 잘 정리해두었으니 참고하면 좋을 것 같다. 👉 문제 확인하기 : BOJ - 벽 부수고 이동하기 🎯 문제 🎯 접근 방법 우선 이번 포스트를 작성하게 된 계기는 문제를 풀면서 끝없는 메모리 초과 문제때문이었다. 다른 사람들의 풀이를 보면 3차원 배열을 사용하여 접근하였지만 2차원 배열만으로도 충분히 문제가 풀렸기에 내 풀이에 고집이 있었다. 💎 1차 시도 (❌) 다른 사람들의 게시판 글 후기를 보면 큐(Queue)를 구현하는 것에 있어서 시간초과가 많이 발생했다고 한다. 다양한 BFS 문제를 겪어본 결과 Node.js에서는 무조건 Queue를 직접 구현해서 사용해야 한다. 즉 shift를 사용하는 순간 어마무시한 배열을 한칸식 옮겨줘야 하기 때문에 사용을 지양한다. 여기까지는 별 문제가 없었다. 벽을 1번은 깰 수 있다고 하는데 그렇다면 백트래킹을 이용해서 배열에 있는 모든 1을 0으로 한번씩 바꿔서 BFS를 돌리면 …

👉 문제 확인하기 : BOJ 15685 치킨배달 🎯 문제 🎯 접근 방법 이 문제는 백트래킹 알고리즘을 이용하는 구현에 조금 더 가까운 문제이다. 문제를 한번 쭉 읽고 어떤 데이터 값이 필요하고 어떻게 가공하면 원하는 답에 접근할 수 있는지에 대해 고민한다면 빠른 시간 내에 해결이 가능하다. 집(1)의 위치를 배열로 저장해야 한다. -> 최종적으로는 집에서부터 치킨 집까지의 거리를 구해야 하기 때문이다. 치킨집(2)의 위치를 배열로 저장해야 한다. -> 주어진 입력값에는 치킨집이 여러개 존재한다. 하지만 M개 만큼의 치킨집만 거리 계산에 이용될 수 있기 때문이다. 위에서 M개 만큼의 치킨집만 거리 계산에 이용이 된다고 했는데 그럼 M개의 치킨집을 가정하여 집에서부터의 M개의 치킨집까지의 최소 거리를 구해야 한다. -> 중복되지 않는 M개의 치킨집의 좌표를 구해야 하기 때문에 백트래킹 알고리즘을 사용한다. M개의 치킨집이 정해졌다면 해당 치킨집에서부터 집까지의 거리를 구해 더해준다.…

🎯 백트래킹 은 해를 찾아가는 도중, 지금의 경로가 정답이 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아가는 방법이다. 백트래킹은 알고리즘을 사용하는데 기존 DFS는 엄청나게 큰 경우의 수라면 모든 케이스를 다 순회해야 하기 때문에 비효율적인 방법을 대체하고자 등장한 알고리즘이다. 즉, 코딩에서는 반복문의 횟수까지 줄일 수 있는 아주 효율적인 알고리즘이다. 이를 흔한 용어로 가지 치기리고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미로 불린다. 일반적으로, 불필요한 경로를 조기에 차단할 수 있게 되어 경우의 수가 줄어들지만, 만약 N!의 경우의 수를 가진 문제에서 최악의 경우에는 여전히 지수함수 시간을 필요로 하므로 처리가 불가능 할 수도 있다. 즉 가지 치기를 얼마나 잘하느냐에 따라 효율성이 결정된다. 정리하자면, 백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것이다. 즉 답이 될 만한지 판단하고 그렇지 않으면 그 …

🎯 CCW 알고리즘은 3개의 점 A, B, C가 있을 때 이 점 3개를 이은 직선의 방향을 알고자 할 때 유용한 방법이다. 경우의 수는 총 시계방향, 반시계방향, 직선 3가지가 존재한다. 기하와 벡터에서 을 사용해서 구한다고 하는데 본인은 문과 수학만 배웠기에 외적에 대해 많은 문서를 읽어봐도 이해가 잘 가지 않았다. 따라서 직선의 방정식을 이용해서 이에 대해 설명하고자 한다. 💎 직선의 방정식 구하기 좌표 A(X1, X2)와 B(X2, Y2)의 직선의 방정식을 구해보자. 💎 C 대입하기 X2 - X1 값이 양수인 경우 (직선의 방향이 오른쪽인 경우) X2 - X1 값이 음수인 경우 (직선의 방향이 왼쪽인 경우) 💎 통일 시켜서 하나의 식으로 정리하기 X2 - X1 값의 양수 여부에 따라 부등호의 결과가 반대이므로 X2 - X1을 양쪽에 곱해서 부등호를 통일시킨다. 이후 X2 - X1이 양수일 때에는 곱해도 부등호가 유지되고, 음수일 경우는 곱하면 부등호가 반대로 뒤집히는 것을 …

🎯 플로이드-워셜 알고리즘 모든 최단 경로를 구하는 알고리즘이다. 이후에 정리할 은 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이었다면, 플로이드-워셜 알고리즘은 한 번 실행하여 모든 노드 간 최단 경로를 구할 수 있다. 💎 플로이드-워셜 알고리즘의 과정 모든 노드 간의 최단거리를 구해야 하는 것이 의 목표이다. 따라서 2차원 인접 행렬로 구한다. 알고리즘은 여러 라운드로 구성이 되는데 라운드마다 각 경로에서 중간 노드로 사용할 수 있는 노드를 선택하고, 더 짧은 길이를 선택하여 줄이는 과정을 반복한다. [STEP 0] 그래프의 노드와 간선에 따라 최단 거리 테이블을 갱신한다. [STEP 1] 1번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다. [STEP 2] 2번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다. [STEP 3] 3번, 4번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다. 🎯 플로이드-워셜 알고리즘 코드 구현 (JS)…

🎯 BFS 는 너비 우선 탐색이라고 하며 시작 노드로부터 가까운 노드를 먼저 방문하고 멀리 떨어져있는 노드를 나중에 방문하는 탐색 방법이다. DFS는 최대한 멀리 있는 노드를 우선으로 탐색하는데, BFS는 그 반대다. 보통 BFS는 선입선출 방식인 큐 자료구조를 이용하는 것이 일반적이다. 다른 언어의 경우는 보통 내장 라이브러리에 큐를 제공하고 있지만 자바스크립트는 큐와 관련된 객체가 내장되어 있지 않다. 따라서 BFS를 이용하기 위해서는 큐 자료구조를 따로 구현해줘야 한다. 💎 BFS의 동작 방식 우선 탐색 시작 노드를 큐에 삽입하고 방문 처리한다. 다음으로 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다. 이 과정을 더 이상 수행할 수 없을 때까지 반복한다. 🎯 BFS 구현 (JS) 큐(Queue) 구현 코드 🎯 BFS의 시간 복잡도 BFS는 DFS와 마찬가지로 그래프가 인접 리스트로 표현되어 있으면 전체 수행시간이 O(…

🎯 그래프(Graph) 그래프는 객체 사이의 연결 관계를 표현할 수 있는 자료 구조로 실제 세계의 현상이나 사물을 정점(V)과 간선(E)으로 표현한 것이다. 한마디로 그래프는 정점과 간선들의 유한집합이라고 통칭할 수 있다. 💎 그래프의 표현 방법 프로그래밍에서 그래프는 크게 2가지 방식으로 표현할 수 있는데 과 이다. 은 2차원 배열로 각 노드의 연결 관계를 표현하는 방식이다. 연결이 되어 있지 않은 노트끼리 무한의 비용이라고 작성한다. 노드에 대해 가중치가 있을 때는 가중치를 입력해주고 가중치가 없는 경우에는 1과 0으로 표기한다. 인접 행렬 방식을 사용하면 노드의 연결 관계를 담은 배열이 중앙 대각선을 기준으로 대칭을 이루게 된다. 반면 는 리스트로 그래프의 연결 관계를 표현하는 방식으로 모든 노드에 연결 정보를 차례대로 연결하여 저장한다. 노드에 대해 가중치가 있을 때는 아래와 같이 가중치를 입력해주고 가중치가 없는 경우에는 2차원 배열로 표기한다. 💎 인접 행렬과 인접 리스…

🎯 그리디 알고리즘 그리디 알고리즘, 즉 은 말 그대로 선택의 순간마다 눈앞에 보이는 최적의 상황만을 쫓아서 최종적인 해답에 도달하는 방법이다. 을 이용하여 문제를 해결하는 순서는 아래와 같다. 현재 상태에서의 최적의 해답을 선택한다. 선택된 해가 문제의 조건을 만족하는지 검사한다. 원래의 문제가 해결되었는지 체크하고, 해결되지 않았다면 최적의 해답을 찾는 과정으로 돌아가 위의 과정을 반복한다. 은 문제를 해결하는 과정에서 매 순간 최적이라고 생각되는 해답을 찾으며, 이를 토대로 최종 문제의 해답에 도달하는 문제 해결 방식이다. 하지만 항상 최적의 결과를 보장하지 못한다는 점을 명심해야 한다. 따라서 아래와 같이 2가지 조건을 모두 성립하지 못한다면 탐욕법을 사용하면 안된다. 앞의 선택이 이후의 선택에 영향을 주지 않는다. 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다. 은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값…

🎯 다이나믹 프로그래밍 개념 라고도 불리는 다이나믹 프로그래밍은 명칭과 의미의 상관관계는 없다. 보통 큰 문제를 작은 문제로 나눠서 문제를 해결할 때 이용되는 알고리즘이다. 사람들에게 익숙한 예시는 피보나치 수열이 있다. 피보나치 수열 역시 를 사용하여 수열의 큰 문제를 작은 문제로 나눠서 해결하는 과정이다. 하지만 피보나치 수열과 다이나믹 프로그래밍은 개념적으로 조금 다른 점을 갖는다. 💎 피보나치 수열의 핵심 문제의 크기에 상관 없이 어떤 한 문제의 정답이 일정하다. 몇번째 피보나치 수를 구하든지에 상관없이 n번째 피보나치수는 항상 동일하다. 💎 다이나믹 프로그래밍의 핵심 각 작은 문제는 한 번만 풀어야 한다. 같은 문제는 구할 때마다 정답이 같다. 정답을 한 번 구했으면, 어딘가에 메모해놓는다. 메모하는 것을 코드에서는 배열로 구현할 수 있다. 메모한다고 해서 Memoization이라는 용어를 사용한다. 🎯 다이나믹 프로그래밍 구현 위는 일반적으로 재귀를 이용하는 피보나치 수…

🎯 우선순위 큐 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조의 일부이며 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다. 🎯 우선순위 큐의 구현 방법 크게 2가지로 분류할 수 있다. 로 구현하는 방법과 으로 구현하는 방법. 우선 배열로 구현하는 것은 구현 자체가 간단하다는 장점이 있지만 데이터를 삭제하거나 삽입해야하는 경우 모든 인덱스를 탐색해야 하는 과정이 있기 때문에 시간복잡도가 **O(N)**이 되므로 상대적으로 부족한 성능을 보여준다. 하지만 힙으로 구현하는 것은 구현 자체에서 난이도가 높지만 시간복잡도가 **O(logN)**이기 때문에 좋은 성능을 보여준다. 🎯 힙의 특징 그렇다면 힙의 특징은 무엇일까? 힙은 완전 이진 트리 자료구조이다. 완전 이진 트리란 마지막 레벨을 제외하고 모든 레벨이 모두 채워져있으며, 마지막 레벨의 모든 노드는 가능한 왼쪽에 위치한다. 즉, 루트 노드로부터 시작하여 왼쪽에서 오른쪽 자식 노드 순서대로 데이터가 순…

💡forEach 와 map의 정확한 차이 파악 기억해야 할 점은 map은 새로운 배열을 반환한다는 점이다. 반환 값은 단순히 버려지기 때문에 에서 반환하지 않는다. 반면 은 새로운 배열을 반환한다. 만약 함수형 프로그래밍을 선호한다면 을 사용하는 것이 더 바람직하다. 를 사용한다면 기존 Array에 영향을 주는 반면에 은 완전히 새로운 Array를 반환하기 때문에 원래의 배열을 건들지 않는다. 또한 데이터를 변경할 때 다른 메서드를 연결하는 것도 이 훨씬 수월하다. 💡 slice와 splice의 차이 파악 함수는 인자로 시작 인덱스와 종료 인덱스를 받는다. **중요한 점은 종료 인덱스는 반환에 포함시키지 않고, 원본 배열은 절대 변경되지 않는다. ** 함수는 와 다르게 원본 배열을 변경시킨다. 또한 시작 인덱스부터 몇개를 삭제할 것인지, 즉 시작 인덱스와 개수를 인자로 받는다. 이 부분은 예시와 함께 살펴보자. 또한 특정 배열의 값을 제거하고 그 자리에 다른 값을 채워 넣을 …

🎯 에라토스테네스의 체 백준, 프로그래머스 문제를 풀다보면 정말 많이 등장하는 유형이 바로 이다. 는 바로 소수를 찾는 방법 중 하나이다. 알고리즘의 원리는 다음과 같다. 숫자 2를 시작으로 2를 빈 곳에 적어두고, 정해진 숫자의 범위의 마지막 숫자까지 모든 2의 배수를 제거한다. 다음 숫자인 3을 빈 곳에 적어두고, 정해진 숫자의 범위의 마지막 숫자까지 모든 3의 배수를 제거한다. 4는 제거했기 때문에 다음 숫자인 5로 넘어간다. 정해진 숫자의 범위의 마지막 숫자까지 모든 5의 배수를 제거한다. 위 과정을 마지막 숫자까지 반복한다. 빈 곳에 적어둔 숫자가 소수에 해당한다. 🎯 메모리를 효율적으로 관리하는 방법 위에서 설명하는 과정을 조금 더 분석해보면 정해진 숫자의 범위의 마지막 숫자까지의 수의 제곱근까지만 반복문을 진행해 배수를 제거하면 된다. 예를 들어 120까지의 숫자를 순회하면서 소수를 찾는 과정이라면 11^2 > 120인 11까지만 배수를 제거하고, 그 이후의 모든…

🎯 스택(Stack) 스택은 쉽게 생각하면 박스에 물건을 차곡차곡 정리하는 형태이다. 먼저 들어간 것이 밑에 위치하기 때문에 나중에 나오게 되고, 나중에 들어간 것이 맨 위에 위치하기 때문에 먼저 나오는 형태의 자료구조이다. 때문에 스택의 모든 연산은 스택의 최상단에서 일어난다. LIFO(Last In First Out) 스택은 서로 관계가 있는 여러 작업을 연달아 수행하면서 이전의 작업 내용을 저장해 둘 필요가 있을 때 사용된다. 스택 구현 코드 (JS) 스택 시간복잡도 push: O(1) pop: O(1) 🎯 큐(Queue) 큐는 대기 줄을 생각하면 이해가 쉽다. 대기 줄에서는 먼저 들어온 사람이 먼저 나가듯 큐에서도 먼저 들어온 데이터가 먼저 나가고 나중에 들어온 데이터가 나중에 나가는 형태의 자료구조이다. 데이터의 삽입과 삭제가 큐의 양끝에서 각각 일어나므로 큐의 앞과 뒤를 명확하게 구분지을 필요가 있다. FIFO(First In First Out) 큐는 순서대로 처리해야 …