문제 출처 : https://www.acmicpc.net/problem/1072분류 : 수학, 이분탐색 백준 1072 게임parametric search구현 포인트1) 처음부터 99퍼나 100퍼라면 절대 증가할 수 없다.2) 이분 탐색으로 시간을 줄이자. 문제는 아래와 같다.문제김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시작했다. 의심을 피했다고 생각한 형택이는 다시 게임을 켰다. 그 때 형택이는 잠시 코딩을 하는 사이에 자신의 게임 실력이 눈에 띄게 향상된 것을 알았다.이제 형택이는 모든 게임에서 지지 않는다. 하지만, 형택이는 게임 기록을 삭..
문제 출처 : https://www.acmicpc.net/problem/2011분류 : 다이나믹 프로그래밍 백준 2011 암호코드DP구현 포인트1) DP로 2자리로 끝나는 경우, 1자리로 끝나는 경우를 저장해준다.2) 해석이 안되는 경우에는 0을 찍어야 한다. 이 문제는 다소 쉬우나 정답률이 낮다. 이유는 나처럼 멍청한 사람들이 해석이 안되는 경우에 대해 고려하지 않아서... 일 것이라는 생각이 든다. 한창 그것 때문에 틀렸습니다가 떠서 여기 글을 남겨 놓기로 하였다. 코드는 아래와 같다. 12345678910111213141516171819202122232425#include#include#define MOD 1000000using namespace std; int DP[5000][2];int main..
문제 출처 : https://www.acmicpc.net/problem/11000분류 : 정렬 및 그리디 백준 11000 강의실 배정NlogN 안에 강의실을 모두 배정하여 보자구현 포인트1) 정렬을 하여 문제를 단순화 한다.2) priority queue를 이용하여 빠르게 강의실을 배정하자. 생각보다 문제 풀면서 뻘짓을 많이 해서 남기기로 했다.어처구니 없게도 처음에 강의 정보를 정렬해 놓고 생각을 너무 복잡하게 하였다...(각 종료시간을 set으로 저장한 후 iterator를 통해 현재 강의 정보의 시작시간과 비교하여 가장 차이가 작은 강의실에 해당 강의를 배정하는 그런 방식으로.. 물론 이 생각은 논리적으로 맞다.지금 각 강의실의 종료시간이 4, 5, 6이고, 배정하려는 강의의 시작시간이 7이라면 당..
문제 출처 : https://www.acmicpc.net/problem/1517분류 : 정렬 백준 1517 버블 소트NlogN 안에 swap수를 구하자구현 포인트1) Merge sort를 이용하여 swap을 구한다. (O(NlogN))2) long long으로 답을 기록한다. 일반적인 버블소트나 flagged한 방법을 써도 N이 크므로 시간초과가 난다. 생각보다 방법을 떠올리기 쉽지 않아서 기록을 남기기로 하였다. 핵심은 Merge를 통해 NlogN으로 time을 줄이는데에 있다.절반씩 나누어 정렬을 하는데, 그 안에서 Bubble Sort로 정렬하는 것이 아니라 Merge sort를 하면서비교 인덱스를 이용하여 swap수를 바로 구해준다. (아래 코드의 line 21)이 과정은 O(1) 시간이 걸리고,..
안녕하세요. 오늘은 피보나치 수열에 대해 다루어 보려고 합니다. 출처 : https://www.acmicpc.net/blog/view/28 피보나치 수열은 일반적으로 재귀형태로 구현을 많이 합니다.하지만 이런 방식은 n이 커질수록 시간이 기하급수적으로 오래걸립니다.그래서 좀 더 좋은 방식들에 대해 찾다보니 위의 링크에서 많은 정보를 얻었습니다.위 내용에 추가적으로 살을 붙여서 정리해 보겠습니다. Contents재귀형식재귀 + 저장(메모이제이션)을 이용한 방식for-loop를 이용한 방식피보나치 수의 나머지(피사노 주기)피보나치 관계식의 행렬표현+ 피보나치 수열의 합 재귀형식재귀형식은 모두 다 아시다시피 아래와 같이 구현됩니다.0, 1, 1, 2, 3, 5, 8, ... 이므로 n이 1보다 작으면 n을 아..
알고리즘 공부[6] 그래프 절단점과 SCC
안녕하세요. 오늘은 그래프의 절단점과 SCC(Strongly Connected Component)에 대해 알아보겠습니다. ContentsCut vertex(절단점 찾기)SCC(Strongly Connected Component)Kosaraju algorithmTarjan algorithm Cut Vertex(절단점)그래프의 절단점이란 해당 정점을 삭제했을 때 그래프가 두 개 이상의 그래프로 나누어 지는 점을 말합니다.이 때 그래프는 항상 undirected graph입니다. 1) 직관적으로 절단점을 찾는 방법을 생각해 봅시다.느낌상에는 모든 정점에 대해 그 정점을 삭제한 후의 그래프를 먼저 따로 구합니다.그 다음 DFS 혹은 BFS 로 몇 번만에 전체 그래프를 cover할 수 있는지를 보면 될 것 같습니..
안녕하세요. 오늘은 그래프의 간선에 대한 내용과 싸이클 검출 방법에 대해 알아보겠습니다. Contents 간선의 분류 싸이클 존재 여부의 확인 간선의 분류간선 구분에 대한 정확한 정의를 살펴봅시다. DFS를 수행할 때 방문하는 간선들을 모아 만든 tree를 DFS spanning tree라고 합니다. 아래와 같은 그래프가 있고, DFS를 1번 정점으로 부터 정점 번호가 작은 순으로 선택한다고 합시다. 그렇다면 DFS Spanning tree는 아래 그림에서 실선에 해당하는 트리를 말합니다. (Root는 1번 정점이 되겠죠) 여기서 실선으로 이루어진, DFS spanning tree를 이루는 간선을 tree edge(트리 간선)이라고 합니다. forward edge(순방향 간선)이란 트리간선이 아닌데, 트..
문제 출처 : https://www.acmicpc.net/problem/1086분류 : 수학 백준 1086 피보나치 수의 합큰 범위의 피보나치 수의 합을 구하라구현 포인트1) 피보나치 행렬표현을 이용 (O(logN))2) 피보나치 수의 합을 수식으로 구하기이 문제는 피보나치 수에 대해 공부하면서 2)를 망각하고 있었기에 남기기로 했다.1)과 2)에 대한 내용은 링크에 있다. 코드는 아래와 같다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include#include#define mod 1000000000 using namespace std;typedef vector matrix; matrix ope..