![]()
알고리즘 스터디를 하다가 새로운 알고리즘을 발견해서 호다닥 공부해서 정리하는 "아주 주관적인" 글입니다. 🔎투 포인터 알고리즘을 쓰는 이유 완전 탐색을 할 경우 시간초과를 피하기 위해서 쓰는 방법이다. 예를 들어서 N칸의 1차원 배열이 있을 때, 모든 경우의 수를 다 테스트 하면 O(N^2)이 된다. 입력인 N의 최대 범위가 너무 크다면 시간초과를 피 할수 없을 것이다. 이럴 때 사용하는 알고리즘이 투 포인터 알고리즘이다. 우선 해당 알고리즘은 포인터 포인터 2개를 사용한다. 2개의 포인터는 start, end, left, right 와 같은 배열의 시작과 끝을 의미하는 두개의 포인터를 사용한다는 뜻이다. 저는 포인터 2개를 start와 end로 사용하겠습니다. start와 end의 초기값은 모두 0이며..
![]()
다익스트라 알고리즘은 그래프에서 한 정점(노드)에서 다른 정점까지의 최단 경로를 구하는 알고리즘이다. [여기서 그래프에는 음의 가중치가 없어야 한다!] 왜냐하면 다익스트라 알고리즘은 탐욕 법(Greedy)을 기반의 알고리즘인데 최소 거리에 최소 거리를 계속 붙여가면서 최종적으로 최적의 경로를 찾기 때문에 음수 가중치를 고려하지 못하는 것이 현실이다. 하지만 무조건적으로 다익스트라 알고리즘이 음수 가중치가 포함된 그래프에서 최단경로를 못 구하는 것은 아니다. 구할 수도 있고, 못 구할 수도 있다. 자세한 것은 밑에 주소에 적혀 있고, 나도 이 블로그를 보면서 참고했다 https://kangworld.tistory.com/76https://kangworld.tistory.com/76 [Algorithm] 다..
![]()
코딩 테스트에서 자주 사용되는 알고리즘이자 탐색 알고리즘에서 가장 유명한 방법들인 DFS와 BFS를 알아볼 것이다. 📕DFS란? DFS는 (Depth First Search)의 약칭으로 우리말로는 깊이 우선 탐색이라고 한다. 간단하게 말하면 트리나 그래프에서 한 루트로 최대한 깊숙하게 들어가면서 탐색한 뒤 다시 돌아가 다른 루트를 탐색하는 방법이다. 위의 그림처럼 1번에서 2번으로 간뒤 2번의 하위 트리를 끝까지 탐색한 후 되돌아가 다른 경로를 탐색한다. 대표적으로는 백트래킹[Backtracking]에 사용한다. 👍장점 현 견로상의 노드들만을 기억하면 되므로 저장 공간의 수요가 비교적 적다. 목표 노드가 깊은 단계에 있을수록, 그 노드가 좌측에 있을수록 BFS보다 해를 빨리 구할 수 있다. 👎단점 해가 ..
![]()
탐욕알고리즘은 선택할 당시의 최적의 값을 구한다. 하지만 그 최적의 선택이 전체적으로 볼때 최적의 선택일지는 보장이 안됨. 진약수는 1과 자기자신을 제외한다. 여기서 최소값과 최대값을 찾아서 곱하면 N이 나올것이다. 따라서 N을 구할때의 최소비교횟수는 진약수의 개수를 최대 최소 동시에 찾기 공식에 넣으면 됨. 최대값 찾기 : n-1 차대값 찾기 : n+lgn-2 중앙값 찾기 : 5/6 * n 최대최소 동시에 찾기 : 홀수일때[ 3n/2- 3/2] 짝수일떄[3n/2-2] 차대키의 후보들의 집합은 : 최대키한테 진 집합들이다. 적대적 논증 : 최악시간복잡도가의 lower bound를 구함. 몬테 카를로 알고리즘 : 반드시 맞는 답을 주지는 않음. 오히려 그 답의 추정치를 제공하고 그 추정치가 맞는 답에 가까..
![]()
💡Intractability 사전적인 의미로는 취급하거나 작업하기 어렵다는 뜻이다. CS적인 관점에서는 문제가 Intractable하다는 뜻은 polynomial-time-algorithm(다차시간 알고리즘)으로 못푼다는 의미이다. polynomial-time algorithm은 최악 시간복잡도의 상한이 입력크기의 다항식 함수가 되는 알고리즘이다. 다루기 힘든 정도는 문제를 푸는 어떤 특정 알고리즘의 성질이 아니라 문제의 성질이라는 사실을 반드시 알아야한다. 다루기 힘든 정도에 대하여 3가지 종류로 문제를 분류할 수 있다. 1.다차시간 알고리즘을 찾은 문제 2.다루기 힘들다고 증명된 문제 3.다루기 힘들다고 증명되지도 않았지만, 다차시간 알고리즘도 찾지 못한 문제(NP-complete) 예를 들어 TSP..
![]()
📕문제 아래 그림과 같이 삼각형 모양으로 숫자를 쌓기로 했다. 위와 같이 경표는 끝도 없이 피라미드를 쌓을 때, N층의 제일 왼쪽, 오른쪽에 쓰게 될 숫자가 무엇일지 예측해보자. 📕입력 첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 층의 번호 N(1≤N≤109)이 주어진다. 📕출력 각 테스트 케이스마다 ‘#x’(x는 테스트 케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 각 테스트 케이스마다 N층의 제일 왼쪽, 오른쪽에 쓰게 될 숫자를 공백으로 구별하여 출력한다 📗입력 예시 3 1 2 3 // 테스트 케이스 개수 // 첫 번째 테스트 케이스, N = 1, K = 1 // 두 번째 테스트 케이스, N = 3, K = 7 // 세 번째 테스트 케이스, N = 9,..
![]()
알고리즘에 도전해보는 방식 2가지 1. 문제를 푸는 더 효율적인 알고리즘을 설계하기 2. 더 효율적인 알고리즘 개발이 불가능함을 증명하기 계산 복잡도는 주어진 문제를 풀 수 있는 가능한 모든 알고리즘에 대한 연구이다. 문제를 푸는 모든 알고리즘의 효율성(복잡도)의 하한을 구하는 것이다. 과연 이 알고리즘이 최선일까? 더 효율적인 알고리즘은 없는가?를 연구하는 것 Finding the Largest Key : Problem : Find the largest key in the arrays of size n, indexed from 1 to n Outputs : variable large, whose value is the largest key in S. void find_largest(int n, vect..
![]()
저번 게시물에서는 외판원 순회 문제를 동적 계획법을 이용해서 풀어보았다. 이번에는 Branch & Bound(분기한정법)을 이용해서 풀 예정이다. 문제의 목표는 동일하게 출발점에서 모든 노드를 각 한 번씩 방문하고 다시 출발점으로 되돌아오는 최소한의 비용을 가지는 경로를 찾는 것이다. 최고 우선 검색을 사용하기 위해서 각 마디의 한계값을 구할 수 있어야 한다. 0-1 배낭 채우기 문제에서는 총무게가 W를 넘지 않도록 하면서 이익을 최대로 하는 게 목표였기 때문에, 주어진 마디에서부터 뻗어나가서 얻을 수 있는 이익의 상한을 계산하였다. 그리고 어떤 마디에서 당시 최대 이익보다 한계값이 큰 경우에 그 마디를 유망하다고 판단했다. 외판원 문제에서는 주어진 마디에서부터 뻗어나가서 얻을 수 있는 여행경로 길이의 ..
![]()
문제 목표 n개의 도시로 판매 출장을 계획하고 있는 외판원이 각 도시를 한 번씩 방문하고, 다시 출발한 도시로 돌아오는 가장 짧은 여행길을 찾는 것. --> 최단 경로 문제 --> 출발한 도시로 다시 돌아오는 부분에서 해밀턴 회로와 동일한 개념. 이 문제는 weighted, directed graph이다. 각 도시에서 도시로 가는 비용이 있고, 방향이 정해져 있다.(여기서 비용은 음이 아닌 정수로 가정한다) 만약 v1을 출발점으로 잡는다면 가능한 경로와 그에 비용은 아래와 같다. [v1->v2->v3->v4->v1] = 22 [v1->v3->v2->v4->v1] = 26 [v1->v3->v4->v2->v1] = 21 v1에서 출발할때의 최적의 경로는 [v1->v3->v4->v2->v1]이고 그 비용은 2..
