마이구미의 HelloWorld 마이구미의 HelloWorld

알고리즘 풀이/그래프

• 백준 2251번 물통 :: 마이구미

  알고리즘 풀이/그래프 2017. 10. 3. 23:04

  이 글은 백준 알고리즘 문제 2251번 "물통" 을 풀이한다.BFS 또는 DFS를 통해 문제를 해결할 수 있다.본인은 DFS로 풀이하겠다. (BFS가 좀 더 효율적이다)2251번 - https://www.acmicpc.net/problem/2251 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이 때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번..

  Read More

• 백준 14502번 연구소 :: 마이구미

  알고리즘 풀이/그래프 2017. 10. 3. 21:43

  이 글은 백준 알고리즘 14502번 "연구소" 를 풀이한다.삼성 SW 역량 테스트의 기출 문제이다.DFS를 통해 문제를 해결할 수 있지만, 다소 복잡한 문제이다.14502번 - https://www.acmicpc.net/problem/14502DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로..

  Read More

• 백준 1967번 트리의 지름 :: 마이구미

  알고리즘 풀이/그래프 2017. 10. 3. 21:24

  이 글은 백준 알고리즘 1967번 "트리의 지름" 를 풀이한다.DFS를 통해 문제를 해결할 수 있다.1967번 - https://www.acmicpc.net/problem/1967기본 지식이 부족하다면 관련 글을 참고 바란다.DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 트리(tree)는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된..

  Read More

• 백준 1941번 소문난 칠공주 :: 마이구미

  알고리즘 풀이/그래프 2017. 9. 15. 23:52

  이 글은 백준 알고리즘 문제 1941번 "소문난 칠공주" 를 풀이한다.기본적인 DFS를 통한 백트래킹을 활용해서는 이 문제를 해결할 수 없다.문제 접근에 있어, 아이디어가 필요한 문제이다.1941번 - https://www.acmicpc.net/problem/1941DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작했다. 곧 모든 여학생이 ‘이다솜파’와 ‘임도연파’의 두 파로 갈라지게 되었으며, 얼마 지나지..

  Read More

• 백준 2023번 신기한 소수 :: 마이구미

  알고리즘 풀이/그래프 2017. 9. 15. 22:54

  이 글은 백준 알고리즘 2023번 문제 "신기한 소수" 를 풀이한다.백트래킹을 통한 문제 풀이가 된다.백트래킹에 대한 기본적인 이해가 필요하다면, 다음 글을 참고바란다.http://mygumi.tistory.com/1912023번 신기한 소수 - https://www.acmicpc.net/problem/2023DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수 7331이다.7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터..

  Read More

• 백준 2661번 좋은수열 :: 마이구미

  알고리즘 풀이/그래프 2017. 9. 9. 21:49

  이 글은 백준 알고리즘 문제 2661번 "좋은수열"을 풀이한다.접근 방식은 백트래킹을 활용해 문제를 해결한다.문제 링크는 다음과 같다.https://www.acmicpc.net/problem/2661DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다.다음은 나쁜 수열의 예이다.3332121323123123213다음은 좋은 수열의 예이다.232321231232123길이가 N인 좋은 수열들을 N자리의 정수로 보아 ..

  Read More

• 백준 1759번 암호 만들기 :: 마이구미

  알고리즘 풀이/그래프 2017. 9. 9. 15:04

  이 글은 백준 알고리즘 문제 1759번 "암호 만들기" 를 풀이한다.접근 방법은 백트래킹을 활용해 문제를 풀이한다.6603번 로또 문제와 흡사하다.조금 응용된 문제로써, 백트래킹을 잘 모른다면 먼저 참고하길 바란다.6603번 로또 - http://mygumi.tistory.com/191문제 링크는 다음과 같다.https://www.acmicpc.net/problem/1759DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보..

  Read More

• 백준 2580번 스도쿠 :: 마이구미

  알고리즘 풀이/그래프 2017. 9. 2. 23:47

  이 글은 백준 알고리즘 문제 2580번 "스도쿠" 를 풀이한다.일반적으로 알고 있는 스도쿠 문제를 해결하는 과정을 그대로 구현하는 것이다.본인은 스도쿠 문제를 풀어본 적이 없다.그렇기에 스도쿠 관련 알고리즘을 사용한 것이 아닌, 단순히 규칙만을 가지고 접근했다.문제 풀이의 핵심은 백트래킹을 활용한다.참고 링크 - http://www.geeksforgeeks.org/backtracking-set-7-suduku/DFS, BFS - http://mygumi.tistory.com/102백준 문제 - https://www.acmicpc.net/problem/2239 스도쿠 문제를 풀기 위한 일반적인 규칙은 다음과 같다.스도쿠에 대해 굳이 자세히 다루지는 않겠다. 일반적으로 빈칸에 해당하는 가로줄 또는 세로줄 또..

  Read More