알고리즘 풀이
-
백준 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층으로 이동하려고 한다.보통 엘리베이..
-
백준 1697번 숨바꼭질 :: 마이구미알고리즘 풀이/그래프 2017. 7. 23. 17:15
이번 글은 백준 알고리즘 문제 1697번 "숨바꼭질" 을 다뤄본다.문제 접근 방법은 BFS를 통해 해결했다.DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇..
-
백준 1987번 알파벳 :: 마이구미알고리즘 풀이/그래프 2017. 7. 22. 22:36
이번 글은 백준 알고리즘 문제 1987번 "알파벳" 을 다뤄본다.문제 풀이는 DFS를 응용하여 해결할 수 있다.DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있..
-
백준 1935번 후위표기식2 :: 마이구미알고리즘 풀이/스택, 큐 2017. 7. 16. 21:36
이번 글은 백준 알고리즘 문제 1935번 "후위표기식2" 를 다뤄본다.1918번 "후위표기식" 문제는 중위표기식에서 후위표기식으로 변환하는 문제였다. - 관련 링크이번 문제는 후위표기식을 계산하는 문제로써, 1918번 문제를 푼 후, 풀어보면 좋은 문제가 된다. 중위표기식에서 후위표기식 변환 문제도 사실상 방법만 알면 간단했다.후위표기식의 계산 또한, 단순하다. 피연산자는 스택에 push 한다.연산자가 나오면 스택에 있는 수를 2번 pop 한다.pop한 두 수를 연산자에 맞게 계산한 후, 다시 push 한다.모든 계산이 끝나면, 스택의 top이 최종 계산 값이 된다. for (int i = 0; i < len; i++) { char ch = s[i]; switch(ch) { case '+': case '..