Algorithm

문제https://www.acmicpc.net/problem/12851 문제 분석해당 문제는 BFS 유형이다.  왜 BFS인가?처음에는 DP라고 생각을 했다. 이상하게 유독 BFS문제를 보면 DP라고 생각할 때가 종종 있는 것 같다... 하지만 이 문제가 BFS유형임에 확실한 것은 (물론 DP로도 풀려고하면 풀 수도 있겠지만) "가장 빠른 시간" 과 "가장 빠른 시간으로 찾는 방법" 이라는 키워드가 있기 때문이다. 가장 빠른 방법 중에서도 특히나 가중치가 없는 그래프의 경우에는 BFS임이 자명하다. 만약 가중치가 있을 경우에는 다익스트라 알고리즘을 사용해야한다. 특히나 트리일 경우에는, BFS는 반드시 "최단경로"를 거칠 수 밖에 없다. 왜냐하면, 해당 노드 간의 경로가 단방향, 또한 하나만 존재하기 때..

알고리즘의 정당성 증명 해결해야 할 문제가 간단할 때는 직관적으로 알고리즘을 설계할 수 있지만, 문제가 복잡해지면 알고리즘이 과연 문제를 제대로 해결하는지 파악하는 것이 힘들다. 물론 단위테스트를 통해서 해결할 수도 있겠지만, 이 방법으로는 턱없이 모자라다. 따라서, 알고리즘의 정확한 증명을 위해서는 각종 수학적인 기법이 동원되어야 한다. 알고리즘에 대한 증명은, 알고리즘을 유도하는 데 결정적인 통찰을 담고 있다. 모든 알고리즘은 치열한 고민과 개선 과정을 거쳐 태어나고 이 과정에서 결정적으로 필요한 깨달음이 증명에 담겨있는 경우가 많다. 또한, 증명을 아는 편이 사용하는 입장에서도 큰 공부가 된다. 1. 반복문 불변식 귀납법은 알고리즘의 정당성을 증명할 때 가장 유용하게 사용되는 기법이다. 대부분의 알..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 다음 문제는 dfs와 bfs의 가장 기초적인 문제다. 문제 풀이법은 딱히 중요한건 아닌 것 같고, 이 문제를 사실 9개월 전에 한번 풀었다가 감이 죽은 지금 다시 한번 풀었는데 메모리랑 실행시간이 너무 크게 비교가 돼서...(물론 9개월 전 코드가 더 아름다웠다.) 마음이 아파서 왜 그런지 비교해보도록 하겠다. 9개월 전 똑똑했던 나의 코드 #include #..

대단히 쉬운 문제지만.. C언어 학습을 위해서 여러 방법으로 풀어보았다. => 근데 역시 매우 쉬운..문제임. 그러나 어디든 도움이 되겠지?! ① 단순 반복문으로 풀어가기 #include int main(void){ int N, ans = 1; scanf("%d",&N); for (int i = 1; i

https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 풀이과정 ①문제 바라보기 기본적인 그리디 문제다. 어렵게 낼 수 있다면 굉장히 어렵게 낼 수 있는 문제인데 이 문제의 경우에는 굉장히 기본기본기본적인 문제같다. ②아이디어 펼치기 연산자 %와 //을 활용하면 간단히 풀릴 것이다. 몫을 구해서 만약 1 이상이라면 남는 돈은 %한 값이 되는거고 빠져나간 동전의 개수는 //가 되는 것이다...

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 풀이과정 ①문제 바라보기 간단한 graph이론 문제다. DFS문제고, 이해를 위해서 문제에서 제시한 예제 2개를 간선과 노드로 표현해봤다. 위의 그림을 보면 1,2,5가 연결되어있고 3,4,6이 연결되어있음을 확일할 수 있다. 따라서 출력값이 2가 되는 것이며, 두번째 그림을 보면 1~6이 모두 어떻게든 연결되어있기에 출력값이 1이 됨..