알고리즘 풀이/그래프
-
백준 9663번 N-Queen :: 마이구미알고리즘 풀이/그래프 2017. 8. 17. 19:24
이번 글은 백준 알고리즘 문제 9663번 "N-Queen" 을 다뤄본다.백트래킹하면 바로 이 문제라고 알려져있을 정도로 유명하다고 한다.그렇다. 백트래킹을 통해 문제를 풀이해보자.DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 체스의 룰을 알아야겠지만, 크게 문제가 되지 않는다.퀸은 배치된 칸을 기준으로 오와 열, 그리고 대각선 이동이 가능한 가장 가치있는 기물이다.퀸을 배치할 수 있는 경우를 보면 확실히 이해를 할 ..
-
백준 2026번 소풍 :: 마이구미알고리즘 풀이/그래프 2017. 8. 15. 00:24
이번 글은 백준 알고리즘 문제 2026번 "소풍" 을 다뤄본다.종만북이라 불리는 책에서도 나오는 문제이긴 하나, 응용된 문제이다.문제 풀이는 DFS를 통한 백트래킹을 이용한다.DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 원장선생님께서는 K(1≤K≤62)명에게 소풍을 보내려 한다. 원장선생님께서는 1부터 N까지 번호가 붙은 N(K≤N≤900)명의 학생들 중에서 K명의 학생들을 소풍에 보내려고 한다. 그런데 원장선생님께서는 중간에 싸움이 일어나면 안되므로 소풍을 갈 학생들이 모두 서로 친구 사이이기를 원한다. 원장선생님께서는 이러한 일을 이번에 조교로 참가한 고은이에게 친구 관계에 대한 ..
-
백준 1062번 가르침 :: 마이구미알고리즘 풀이/그래프 2017. 8. 13. 15:50
이번 글은 백준 알고리즘 문제 1062번 "가르침" 을 다뤄본다. 백트래킹을 활용하는 문제로써, 20% 대의 정답 비율을 가졌다. 이전에 다룬 6603번 로또와 유사한 문제지만 문제를 잘 이해하지 않는다면, 시간 초과를 경험하게 된다. 백트래킹 관련은 6603번 로또 문제 풀이를 통해 참고하길 바란다. 참고 링크 DFS, BFS - http://mygumi.tistory.com/102 Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 2019.06.11 재채점 결과 메모리 초과 발생으로 코드 추가 남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민..
-
백준 14431번 소수마을 :: 마이구미알고리즘 풀이/그래프 2017. 8. 8. 00:41
이번 글은 백준 알고리즘 14431번 "소수마을" 을 다뤄본다.최근 선린고에서 주최된 머그컵이라는 대회에서 출제된 문제이다.이전에 다뤘던 9205번 "맥주 마시면서 걸어가기" 와 흡사한 문제가 된다.9205번 문제는 BFS도 좋은 접근이지만, 플로이드 알고리즘을 통해 문제 풀이를 했다. (9205번 풀이)이번 문제에서는 플로이드가 아닌 BFS를 통해 문제를 해결해본다.DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 소수 마을들의 주민들은 매우 특이한 규칙을 준수한다. 규칙은 바로 “가고 싶은 위치까지의 거리가 소수일 경우에만 간다”라는 것이다. 소수 마을의 주민 승욱이는 소수 마을에서 멀..
-
백준 9205번 맥주 마시면서 걸어가기 :: 마이구미알고리즘 풀이/그래프 2017. 8. 6. 00:08
이번 글은 백준 알고리즘 문제 9205번 "맥주 마시면서 걸어가기" 를 다뤄본다.문제 풀이는 플로이드 와샬 알고리즘으로 해결했다.플로이드 와샬 알고리즘은 다음 링크를 참고하면 되겠다. (플로이드 와샬 알고리즘)* BFS를 통한 방법은 14431번 소수마을 풀이 참고Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다.상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라..
-
백준 2573번 빙산 :: 마이구미알고리즘 풀이/그래프 2017. 8. 4. 00:23
이번 글은 백준 알고리즘 2573번 "빙산" 을 다뤄본다.정답 비율이 20%대로 어렵게 보이지만 비율 대비 쉬운 문제가 된다.본인은 DFS를 통해 문제를 풀이하겠다.DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 문제를 보다시피, 1년이 지날 수록, 빙산의 높이가 상하좌우에 있는 0의 횟수만큼 줄어드는 것을 볼 수 있다.그리고 그림3과 같이 2개 이상으로 분리되는 시점을 찾는 문제이다.분리된 빙산은 {3, 2}, {3}, {4} 가 된다.그래프에서 이러한 빙산의 영역을 "연결 요소"라고 표현한다.즉, 이 문제는 연결 요소의 개수를 2개 이상이 되는 시점을 찾는 문제가 된다. 코드 흐름은 ..
-
백준 6603번 로또 :: 마이구미알고리즘 풀이/그래프 2017. 8. 1. 21:24
이번 글은 백준 알고리즘 문제 6603번 "로또" 를 다뤄본다.문제를 보다시피, 모든 경우의 수를 찾아야한다.DFS에서 백트래킹을 응용하여 문제를 해결할 수 있다.이 문제의 코드를 이해한다면, 재귀 함수와 친해질 수 있을 것이다.DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 독일 로또는 {1, 2, ..., 49}에서 숫자 6개를 고른다.로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 숫자 중 k(k>6)개의 숫자를 골라 집합 S를 만든 다음 그 숫자만 가지고 번호를 선택하는 것이다.예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 숫자를..
-
백준 5014번 스타트링크 :: 마이구미알고리즘 풀이/그래프 2017. 7. 23. 17:29
이번 글은 백준 알고리즘 문제 5014번 "스타트링크" 를 다뤄본다. 이전 글에서 다룬 1697번 숨바꼭질과 흡사하다. 조금 더 자세한 내용은 1697번 풀이를 보길 바란다. 1697번 풀이DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다.스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트링크가 있는 곳의 위치는 G층이다. 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다.보통 엘리베이..