0-1 BFS란? BFS를 기반으로 가중치가 0,1로 주어진 그래프에서 최단경로를 찾아낼 수 있는 알고리즘이다. 기본적으로 그래프에 대한 이해와 최단경로 다익스트라 알고리즘에 대한 이해가 필요하다. 최단경로 알고리즘에는 다익스트라 알고리즘을 사용할 수 있지만, 시간복잡도가 O(ElogE) 또는 (ElogV)인 반면에 0-1 BFS는 O(V+E)의 시간 복잡도로 문제를 해결할 수 있다. 가중치 0인 정점이 존재하기 때문에, 실제로 정점의 방문 횟수가 더 많더라도 가중치가 더 낮은 경우를 고려해야한다. 그렇기 때문에 결과 값이 방문 횟수의 최소가 아닌 가중치의 최소인 경우를 찾기 위해서는 가중치가 낮은 경로부터 탐색해야한다. 가중치가 낮은 정점으로의 이동을 높은 우선 순위로 해야하기 때문에, 덱의 가장 앞단..
지금 현 상황 2023년 5월 4일(목) 내가 풀고 있는 알고리즘 사이트에 대해서 정리를 하여보자. 백준알고리즘 백준알고리즘 사이트이다. 내가 지금 현재 가장 주력으로 풀고있다. 앞으로 졸업까지 목표는 1000문제를 푸는 것이다.(할 수 있을까...) 내가 가장 좋아하는 사이트이다. 프로그래머스 프로그래머스이다. 최근에 네이버, 삼성 코테를 보면서 프로그래머스 또한 풀어야겠구나를 느꼈다. 특히나 네이버 코테때는 프로그래머스 환경에 익숙해져야함을 느꼈다. 목표는 lv3까지는 다 푸는 것이다. 삼성 SwExpertAcademy 최근에 다시 풀기 시작한 사이트이다. 삼성의 출제방식이랑 최대한 비슷해서 풀고있다. 삼성을 갈 수 있으나 모르겠다....
DFS와 BFS 란 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)는 그래프 탐색 알고리즘입니다. 이 두 알고리즘은 그래프의 노드를 탐색하는 방식에서 차이가 있습니다. DFS는 한 노드에서 시작하여 깊이를 우선으로 탐색하며, 해당 경로가 더 이상 진행할 수 없을 때 되돌아가서 다른 경로를 탐색합니다. 스택이나 재귀 함수를 사용하여 구현할 수 있습니다. DFS는 그래프의 깊은 부분을 우선적으로 탐색하므로, 해답이 깊은 단계에 위치한 경우 효율적일 수 있습니다. 하지만 무한 루프에 빠질 수 있으며, 최단 경로를 찾는 문제에서는 최적의 해를 보장하지 않을 수 있습니다. BFS는 한 노드에서 시작하여 인접한 모든 노드를 먼저 탐색한 후, 그 다음 레벨의 인접한 노드를 탐색합니다. 큐를 사용하여 구현할 수 있..
유니온 파인드(Union-Find) 알고리즘이란 유니온 파인드 알고리즘은 대표적인 그래프 알고리즘 중 하나로, 주어진 그래프의 노드들을 서로 다른 집합으로 분리하거나, 두 개의 노드가 같은 집합에 속하는지 여부를 판단하는 데 사용됩니다. 이 알고리즘은 일반적으로 노드들이 상호 연결된 그래프에서 사용됩니다. 초기에는 모든 노드들이 각각 서로 다른 집합에 속해 있습니다. 유니온 파인드 알고리즘은 두 개의 노드가 같은 집합에 속하도록 하거나, 두개의 집합을 하나로 합치는 연산을 수행합니다. 이 알고리즘의 핵심은 각각의 집합을 하나의 트리로 나타내는 것 입니다. 각 노드는 해당 집합의 루트 노드를 가리키는 포인터를 가지고 있습니다. 노드들이 합쳐지면, 두 트리의 루트 노드를 연결하고, 이전에 각 트리의 루트 노..
플로이드 와샬이란 모든 최단 경로를 구하는 알고리즘이다. 다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이라고 한다면, 플로이드-와샬은 한번 실행하여 모든 노드간 최단 경로를 구할 수 있는 것이다. 다익스트라 알고리즘이 가장 적은 비용을 하나씩 선택했다면 플로이드 와샬 알고리즘은 기본적으로 거쳐가는 정점을 기준으로 알고리즘을 수행한다는 점에서 그 특징이 있다. 플로이드 와샬 알고리즘의 과정 예시로 모든 노드간의 최단거리를 구해야하므로 2차원 인접 행렬을 구성한다. 알고리즘은 여러 라운드로 구성됩니다. 라운드마다 각 경로에서 새로운 중간 노드로 사용할 수 있는 노드를 선택하고, 더 짧은 길이를 선택하여 줄이는 과정을 반복한다. 초기 그래프를 인접행렬로 나타내면 다음과 같습니다..
그리디 알고리즘이란 탐욕법 알고리즘이란 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 그리디 알고리즘을 이용하면 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로' 와 같은 기준을 알게 모르게 제시해준다. 코딩 테스트에서 출제되는 그리디 알고리즘 유형의 문제는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 그렇기에 많은 연습이 필요하다. 코딩테스트에서는 바로 문제의 유형을 파악하기 어렵다. 우선 그리디알고리즘을 의심하고, 문제를 해결할 수 있는 해결법이 존재하는지 고민한 이후에 해결방..
브루트 포스 알고리즘이란? 쉽게 말하면 모든 경우의 수를 무식하게 전부 다 탐색한다는 뜻이다. 전체를 탐색한다는 의미에서 전체 탐색, 완전 탐색이라고 한다. 알고리즘 설계의 가장 기본적인 접근 방법은 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 방법이다. 선형 구조를 전체적으로 탐색하는 순차 탐색, 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS, Depth First Search)과 너비 우선 탐색(BFS, breadth first search)이 가장 기본적인 도구이다. 브루트 포스의 장단점 브루트 포스의 장점 알고리즘을 설계하고 구현하기 매우 쉽다. 복잡한 알고리즘 없이 빠르게 구현할 수 있다. 브루트 포스의 단점 알고리즘의 실행 시간이 매우 오래 걸린다. 메모리 효율면에서 매울..
Hash 란? 해시란 임의의 크기를 가진 데이터(Key)를 고정된 크기의 데이터(Value)로 변화시켜 저장하는 것이다. 키에 대한 해시값을 사용하여 값을 저장하고 키-값 쌍의 갯수에 따라 동적으로 크기가 증가하는 associate array이다. 키에 대한 해시값을 구하는 과정을 hashing(해싱)이라고 한다. 이때 사용하는 함수(알고리즘)를 해시함수라고 한다. 해시 값 자체를 index로 사용하기 때문에 평균 시간복잡도가 O(1)로 매우 빠르다. Hash 함수란? 위에서 설명한 것과 같이 키에 대한 해시값을 만드는 함수(알고리즘)이라고 한다. 계산이 복잡하지않고 키값에 대한 중복이 없고 해시값을 고르게 만들어 내는 함수가 좋은 함수이다. 특징 입력값이 일부만 변경되어도 전혀 다른 해시값을 출력한다...
