welcome!

최대유량 기초문제백준 6086 최대유량최대유량 기초문제이다. USACO Silver 문제이긴한데, 유량 알고리즘이 하나도 응용되지 않은 문제이다. 따라서 배열과 dfs 탐색만 있으면 가능하다. 소스보기 (dfs) : https://github.com/ingyeoking13/algorithm/blob/master/bj/p1000/6086.cc 소스보기 (bfs):https://github.com/ingyeoking13/algorithm/blob/master/bj/p1000/6086bfs.cc

백준 12784인하니카 공화국 문제는 흥미로운 문제였다. 인하니카는 섬으로 이루어진 나라인데, 각 섬은 다리들이 연결하고 있다. (그래프 ,,, ?)다리는 모든 섬을 연결할 수 있는 최소한의 개수로 사용되고 있다. (트리 .. !)다리가 한 개인 마을에 살인마가 존재하기 때문에 내가 사는 곳(1번 노드) 과 끊어야한다.이때 각 각의 다리를 끊는 비용은 주어질 때, 살인마가 존재 할 가능성이 있는 모든 마을에 대해 다리를 끊을 때 최소비용 을 구하라. 라는 문제이다. 이 문제는 난해할 수 있는데, 생각대로 깊이 우선탐색을 구현하면 쉽게 해결 할 수 있다.그러나 나는, 이 문제를 통해 좀 더 확장할 수 있는 재귀탐색 기법을 보여주고 싶었는데이 문제는 조금만 뉘앙스를 바꾸면, 트리에서 루트노드에서부터 모든 리..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV_6pTXqsXUDFAWS 홍준이의 사전놀이 난이도 : D5 (하지만 기본적인 Trie data structure implemetation이었다) 트라이 자료구조를 통해 수행했다. 만약 트라이가 뭔지 모른다면 제가 정리한 포스팅이 있습니다 클릭 클릭 온라인 커뮤니티에서 들었는데, 가장 현명했던 방법은 단어를 insert 하면서 각 노드를 cnt++ 해주는것이 나중에 임의의 문자열 S에 해당하는 단어가 몇개있는지 체크해주는 것이였다. 나는 재귀를 통해 word 를 체크하였고, 그 방법은 최악의 경우의 연산수는 26^10 ( S

문제보기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..

백준 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..