내맘대로 공부일기

비둘기집 원리(Dirichlet's Pigeonhole Principle) 조합론의 기본 원리이다. 간단하게 말한다면 "비둘기가 N마리 있고 M개의 비둘기 집이 있다. 이때, N > M인 경우 하나의 비둘기 집에는 최소한 두 개 이상의 비둘기가 들어간다." 라는 내용이다 생각해보면 정말 당연한 소리다. 하지만 이 당연한 소리가 문제를 푸는데 큰 도움이 된다. 백준 문제 중 20529번이 대표적으로 비둘기집 원리를 사용하는 문제다 https://www.acmicpc.net/problem/20529 20529번: 가장 가까운 세 사람의 심리적 거리 각 테스트 케이스에 대한 답을 정수 형태로 한 줄에 하나씩 출력한다. www.acmicpc.net 조만간 풀고 링크를 첨부하도록 하겠읍니다...

플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm)이란? 그래프 혹은 이차원 배열에서 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용한다. 가중치가 있는 그래프에서 각각의 지점까지의 최소 거리를 구하는 알고리즘 이다. ABCD라는 네 지점이 있고, 각각의 가중치가 아래와 같다고 가정한다. A-B 10 A-C 3 A-D 4 B-C 3 B-D 5 C-D 7 이런 가중치가 있을 경우 A에서 B를 가는 최소 경로를 구해보자. A에서 바로 B로 가는 경우 10의 가중치이지만, A-C-B로 간다면 6이 가중치로 더 적은 거리로 이동할 수 있다. 더 쉽게 말하자면 서울에서 부산을 간다고 생각해보자. 그런데 오후 늦게 출발을 해서 대전 혹은 대구에서 하룻밤을 보내고 가야..

⚠️ 내맘대로 작성한 글이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️ 저번 글에 작성했던 알고리즘인 Grid는 최적의 답을 구할 수는 없다. 그저 근사치를 구할 수 있을 뿐이다. 그렇기 때문에 최적해를 구할 수 있는 방법을 소개하고자 한다. Grid알고리즘의 경우 내 블로그에 적어뒀지만 여기에 한번 더 링크를 남겨둘테니 헷갈린다면 한번 더 보는걸 추천한다. https://naemamdaelo.tistory.com/47 form it -> cool it -> REPEAT 이 것을 적용시킨 알고리즘을 Simulated Annealing이라고 한다. 우리는 어떠한 값을 구할때 Global Optimum을 구하고자 한다. 하지만, 최적해로 가는 과정에는 Local Optimum이 존재한다...

⚠️ 내맘대로 작성한 코드이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️ Traveling Salesperson Problem(TSP) / 외판원 문제 외판원이 여러 지역을 돌아다닌다. 출발지는 존재하고, 모든 도시 한번씩은 반드시 방문해야 한다. 하지만, 한번 간 도시는 재방문할 수 없고, 출발지로 돌아와야한다. => 최적경로 찾기 문제 ex) A B C D A-B : 10 A-C : 35 A-C : 30 B-C : 30 B-D : 15 C-D : 30 A Simple TSP 1단계 : 모든 경로를 List Up 2단계 : 그 중 최소 경로 선택 모든경로 결과값 ABCDA : 100 ABDCA : 90 -> shortest! ACBDA : 110 ACDBA : 90 -> shorte..

⚠️ 내맘대로 작성한 글이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️ 1. 그리디(Greedy)란? 그리디 알고리즘이란 "탐욕법"이라고도 부른다. 이 알고리즘은 "현재 상황에서 최적이라고 생각되는 결과값을 선택"하는 알고리즘이다. 장기적(Global)으로 보면 틀린 선택일지라도 현재(Local) 해당 결과값이 최적이라면 해당 값을 선택한다. 즉, 항상 최적해를 보장하는 것은 아니다. 그러면 최적해를 보장하지 않는데 왜 그리디 알고리즘을 쓸까? 계산속도가 매우 빠르다. 같은 내용의 문제를 DP등 다른 알고리즘을 사용하는 것 보다 빠른 속도로 결과값을 도출한다. 게다가 그리디 알고리즘을 활용할 수 있는 문제가 유형화 되어있다. 해당 유형을 익힌다면 그리디 알고리즘을 사용하지 않을 이유가..

⚠️ 내맘대로 작성한 글이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️ 1. 백트래킹(Backtracking)이란? 완전 탐색 알고리즘에 조건을 추가하여 가능성이 없는 부분을 탐색하지 않도록 하는 알고리즘이다. 즉, 완전탐색 알고리즘은 "모든 부분을 전부 탐색한다"이고 백트래킹을 적용시키게 되면 "가능한 모든 부분을 전부 탐색한다"가 된다. 모든 경우의 수를 탐색하는 것이 아니라 가능한 부분만 탐색을 하도록 하여 반복 횟수를 줄임으로써 속도를 향상시키는 알고리즘이다. 핵심 키워드는 "배제"와 "풀이시간 단축"이다. 이렇게 배제시키는 것을 가지치기 라고 부른다. 해당 방향으로 진행했을 경우 답이 나올 수 있는지 확인하고 나올수 없다면 진행하지 않도록 가지치기를 진행한다. 예를 들어 1~..

⚠️ 내맘대로 작성한 글이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️ 1. 브루트포스(Brute-Force)란? Brute : 짐승같은 Force : 힘 짐승같은 즉, 무식한 방법으로 확인한다는 뜻이다. 완전 탐색 알고리즘으로 가능한 모든 경우의 수를 전 부 다 탐색하면서 조건에 충족되는 값을 도출해내는 알고리즘이다. 예를 들어 1부터 100사이의 짝수의 갯수를 구하는 문제라고 가정해보자. 하나의 변수를 1부터 시작하여 해당 숫자가 짝수인지 파악하고, 짝수라면 카운트를 올려준다. 그 후 숫자에 1을 더하고 위 과정을 반복한다. 그러다가 숫자가 101이 되면 종료하는 방식이다. 간단한 코드로 나타내면 for(i = 1; i < 101; i++){ if(i % 2 == 0) coumt+..

⚠️ 내맘대로 작성한 글이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️ 1-1. 깊이우선탐색(DFS)란? 그래프의 탐색 방법중 하나. Depth-First Search 연결된 것들을 최대한 깊게 내려가고 더이상 못내려가면 옆으로 이동하는 탐색방식. 이게 뭔소리냐. A가 BCD랑 연결되어있다고 생각하자. A에서 B와 연결되어있다는것이 확인되는 순간 바로 B로 이동한다. 그 후 B와 연결되어있는것을 파악하고 계속 이동하다가 더이상 연결된게 없다고 판단되면 C로 이동한다. Ex) 시작점 -> 연결된 값들 기본 설정 A -> BCD B -> EF C -> K D -> Q 진행 순서 A - B - E - F - C - K - D - Q 좀더 자세히 나타내면 A - B - C - 더이상 C에서 ..

⚠️ 내맘대로 작성한 글이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️ 1. LCS란? Longest Common Subsequence의 약자로 최장 공통 부분 문자열이다. Substring 말고 Subsequence맞다. Substring은 연속된 것만 가능하고 Subsequence는 연속되지 않은 것도 가능하다. Ex) 1번 : ABCDE 2번 : BCNKE 제일 긴 Substring : BC (BCNKE) 제일 긴 Subsequence : BCE (BCNDE) 2. 그럼 어떤 상황에서 LCS를 사용하나? 염기서열 유사성 분석, 음파 단어 검색 및 교정 등에 사용된다. 3. 어떻게 사용하나? 0 A B C D E 0 0 0 0 0 0 0 B 0 C 0 N 0 D 0 E 0 위와 같..

⚠️ 내맘대로 작성한 글이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️ 1. Dynamic Programming이란? 큰 문제를 작은 문제로 나누어 푸는 방식이다. 이러한 방법을 통해 한번 푼 문제를 여러번 푸는 비효율적인 방식을 개선시켜 하나의 문제는 단 한번만 풀도록 하는 알고리즘이다. 2. 그럼 어떤 상황에서 Dynamic Programming을 사용하나? 첫번째 조건 : 작은 문제를 여러번 반복한다. 두번째 조건 : 같은 문제는 구할때마다 정답이 반드시 같다. 3. 어떻게 사용하나? 첫번째 방법 : Bottom-up : 작은 문제부터 차근차근 구하는 방법 두번째 방법 : Top-down : 큰 문제부터 해결하다 작은문제가 아직 해결이 안됐을 경우 그때 작은 문제를 해결하는 방법..