welcome!

문제보기https://www.acmicpc.net/problem/2447분할정복 문제 재귀에 대해 능숙하다면 금방 해결 할 수 있는 문제이다. 10~20분 소요. 나는 알고리즘을 처음 시작할 때가 작년 7월 정도였으니, 한 9개월 정도 공부한 것이다. 내가 별찍기 11을 작년 8월- 그러니까 한 알고리즘 시작한지 1개월 도 안되었을 때 도전했다가 실패했을 것이다. 그때 좀 우울했다. 그러니까 이 문제를 해결하고, 포스팅 하는거지만,.. 나에겐 의미가 있는 포스팅이다 ㅋ. 이런류의 또 이런 수준의 문제는 다른사람의 코드를 보고 이해하고 분석하고 왜 틀린 이유를 짚으려면 나에겐 아직 조금 난해하기도 하고, 어렵다 그런만큼 초보 수준에서 별찍기 마스터를 하겠다 해서 괜히 이런문제에 상처받질 않기를 원한다. 왜..

문제 보기https://www.acmicpc.net/problem/11657 벨만포드 알고리즘이다. 알고리즘 분류 기능을 이용해 풀수있는 가장 첫 문제이며, 벨만포드 알고리즘을 그대로 사용하면 된다.기존소스에 반례가 있었다. 출발점에서 도달 할 수 없는 정점 간에 음수 경로가 존재해도 음수사이클 존재를 판단했던 것이다. 그리고 INF 값이 너무 작았다. 500*10,000+1 이상되어야한다. 수정하였음. 등록일이 18년 2월이었으니... 1년 8개월만에 수정한거네요!` 소스보기https://github.com/ingyeoking13/algorithm/blob/master/bj/p1000/11657.cc

백준 5719 거의 최단경로 난이도 꽤 있다고 생각함.https://www.acmicpc.net/problem/5719 다익스트라를 이용하여 최단경로를 저장해나가는데 pred 벡터에 이전 경로를 갱신해준다.그리고 이전경로를 모두 탐색해 그 경로를 재귀적으로 접근하여 -~ 사용할 수 없는 간선으로 만든다.그리고 다시 다익스트라를 활용한다. 그러면 거의 최단경로가 나온다. 개념적으로 와닿지만, pred 를 어떻게 벡터로 만들고, ... 그리고 어떻게 삭제하는가... 에 대해서 생각하는데 시간이 많이 걸린 문제였다. 여기서 아마 구현능력과 논리력이 갈리었을거라 생각한ㄷㅏ 리저널,, 문제였는데 어렵긴 어려운것 같다. 난 제한 시간내에 못풀었다 100% ㅋㅋㅋ. 이 문제로 인해 느낀점은, pred 벡터에 targ..

최단경로 문제와 벨만포드 알고리즘Shortest path Problem && Bellman-ford Algorithm (Label Correcting Algorithm)벨만의 1958년 연구 논문의 서론 부분이다. (RAND corp.) 두 번째 문단에서, " dynamic programming의 (함수 방정식 기법) 사용과 N-1번의 반복후에 수렴하는 반복적 알고리즘이 " 를 보자. 이게 바로 벨만-포드 알고리즘의 큰 핵심이다. Introduction 최단경로를 찾는 문제는 크게 두 종류로 나뉜다. 1 한 점에서 임의의 한 점(다른 모든 점) 까지의 최단경로를 찾는 문제2 모든 점 간의 최단경로를 찾는 문제 이 포스팅은 1번인 한 점에서 임의의 한 점 까지의 최단경로를 찾는 방법(알고리즘)에 대해서 포..

이 자료는Thomas H. Cormen, Charles E. Leiserson의 introduction to algorithms과 Kenneth H. Rosen 의 Handbook of discrete and combinatorial mathematics의 자료 일부를 번역하고 그 외 여러 wikipedia 자료들을 통합해서 작성된 것입니다.개인의 이윤을 위해서 작성한 것이 아니며 스스로의 학습용 및 정보 공유 용으로 작성했습니다. Introduction of Heap sort이번 포스트에서는, heap sort를 소개하고자 한다. heap sort의 수행복잡도는 O(nlog n)이다.머지 소트나 퀵소트는 sorts in place가 아니지만,힙 정렬은 삽입정렬과 마찬가지로 sorts in place이다..

백준 1766 문제집원문보기https://www.acmicpc.net/problem/1766 방법론 : 위상정렬 + 우선순위 큐 이 문제는 위상정렬 문제이지만, 스페셜 저지가 아니였다. 즉 정답이 하나라는 이야기인데, 어떻게 이런 조건을 가지게 되었는지 살펴보자. 문제를 보면 n개의 문제와 m개의 간선 정보가 나온다. "문제" (실제 문제와 문제의 예제에 나오는 문제와 헷갈리지 않게 쌍따옴표로 강조했다.) 의 난이도가 낮는 것부터 우선순위를 두고싶다고 한다.그러면서도, 동일한 난이도가 없기 때문에 스페설 져지 문제가 아닌 답이 하나로 결정될수 있었다. 큐에서 꺼낼땐 난이도 낮은것부터 꺼내었다.C++의 STL priority_queue 자료구조를 이용했다. 소스보기 https://github.com/ing..

백준 2252 줄세우기원문보기https://www.acmicpc.net/problem/2252 방법 : topological sort n명의 학생과 m 개의 2-순서쌍이 주어진다. 이 때 전체적인 키비교 수열, 즉 n-순서쌍을 생성하시오. 라는 문제이다. 이 문제는 스페셜 저지 문제인데, 정답이 여러개 존재할 수 있다는 이야기이다. 위상정렬 문제는 주어진 방향간선으로 여러 개의 정렬된 n-순서쌍이 나올수 있는 것이다.한번 살펴보면, 2번 예제는4 24 23 1 은 그래프 그룹이 두 개이므로, (4, 2, 3, 1), (4, 3, 2, 1), (4, 3, 1, 2), (3, 1, 4, 2) 등등...몇 종류가 된다. 여기까지는 약간 응용없는 위상정렬인것 같다.아직은 방법론을 배우자는 입장이니까, 포스팅 된..

백준 1005 acmcrafthttps://www.acmicpc.net/problem/1005 startcraft 게임처럼, 빌드 순서가 주어진다. n개의 건물이 있고, 빌드 순서 간선은 k개가 있다고 하자.그 n개의 건물들 중 순서도에 따라 지어가는 도중에 어떤 w 건물을 이기는게 확정된다고 한다.이때 이길 수 있는 w 건물을 짓게되는 최소시간이 몇인가? 방법론 : 위상정렬 (topological sort) + 간단한 수학 위상정렬을 할 때 입차수가 0인 임의의 u노드를 현재 그래프에서 빼주는데,이 때 남아있는 그래프에서 그 노드 u를 포함하고 있는 간선E가 연결된 나머지 노드 v에 대해 indegree를 뺴주는 것을 확실히 한다. 여기 까지는 naive한 위상정렬 알고리즘으로 구현할 수 있다. 그런데..

백준 2623 음악프로그램문제보기https://www.acmicpc.net/problem/2623 n 명의 가수와 m명의 pd가 주어진다.m 명의 각각 pd는 자신만의 방법으로 음악방송 프로그램을 짜려고한다.각 pd는 선호하는 가수들의 방송 순서를 정해놓는데, 각 pd간의 가수 방송 순서를 준수하면서 음악 방송 스케쥴을 짤 수 있는지 체크해야한다.만약 그런 스케쥴이 존재할 수 없다면, 즉 존재하지 않는다면 0을 출력하고존재할 수 있다면 그 중 하나의 방송 스케쥴을 출력하라. 방법론 : 위상정렬 (topological sort graph algorithm)위상정렬 알고리즘 보기(* 추가 예정) 소스보기https://github.com/ingyeoking13/algorithm/blob/master/bj/p1..

topcoder SRM494 Div2 Level1 interesting party원 문제 주소 (로그인하고 하고 난뒤에 보임... 그냥 interesting party 로 검색하는게 더빠름)https://arena.topcoder.com/index.html#/u/practiceCode/14480/15196/11312/2/307028 공통된 단어를 찾는것이다.brute force 방식으로 전체탐색하면된다.n^2의 시간복잡도로 수행할 수 있다.n이 50까지였기에 망정이지만, 100만인경우 O(n)의 접근법으로 구현해야한다.그럴땐 맵 또는 딕셔너리 자료구조를 이용하면된다. C/C++ 소스보기https://github.com/ingyeoking13/algorithm/blob/master/topcoder/inte..