알고리즘 풀이
-
백준 2479번 경로 찾기 :: 마이구미알고리즘 풀이/그래프 2018. 1. 29. 21:15
이 글은 백준 알고리즘 문제 11403번 "경로 찾기" 를 풀이한다.정올 출제 문제로써, 풀이 방법은 DFS 를 통해 해결한다.문제 링크 - https://www.acmicpc.net/problem/2479DFS - https://mygumi.tistory.com/102 길이가 같은 두 개의 이진수 코드 A와 B가 있다고 하자. 이 두 코드 사이의 해밍 거리는 A와 B의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 수이다. 예를 들어, A=010010, B=011011 이라고 하면, 세 번째 비트와 여섯 번째 비트만 서로 다르므로 이 두 코드 사이의 해밍 거리는 2이다.우리는 총 N개의 이진 코드를 가지고 있고, 각 코드의 길이는 K로 같다.예를 들어, 다음과 같이 길이..
-
백준 1799번 비숍 :: 마이구미알고리즘 풀이/그래프 2018. 1. 29. 20:16
이 글은 백준 알고리즘 문제 1799번 "비숍" 을 풀이한다.정올 문제로써, 풀이 방법은 DFS 를 통해 해결한다.문제 링크 - https://www.acmicpc.net/problem/1799DFS - http://mygumi.tistory.com/102 서양 장기인 체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다. 과 같은 정사각형 체스판 위에 B라고 표시된 곳에 비숍이 있을 때 비숍은 대각선 방향으로 움직여 O로 표시된 칸에 있는 다른 말을 잡을 수 있다.그런데 체스판 위에는 비숍이 놓일 수 없는 곳이 있다. 에서 체스판에 색칠된 부분은 비숍이 놓일 수 없다고 하자. 이와 같은 체스판에 서로가 서로를 잡을 수 없도록 하면서 비숍을 놓는다면 과 같이 최대 7개의 비숍을 놓을 수 있..
-
백준 2564번 경비원 :: 마이구미알고리즘 풀이/수학 2018. 1. 29. 14:09
이 글은 백준 알고리즘 문제 2564번 "경비원" 을 풀이한다.정올 출제 문제로써, 풀이 방법은 문제 이해를 통한 단순한 구현이다.문제 링크 - https://www.acmicpc.net/problem/2564 동근이는 무인 경비 회사 경비원으로 항상 대기하고 있다가 호출이 들어오면 경비차를 몰고 그 곳으로 달려가야 한다. 동근이가 담당하고 있는 곳은 직사각형 모양의 블록으로 블록 중간을 가로질러 차가 통과할만한 길이 없다. 이 블록 경계에 무인 경비를 의뢰한 상점들이 있다.예를 들어 가로의 길이가 10, 세로의 길이가 5인 블록의 경계에 무인 경비를 의뢰한 3개의 상점이 있다고 하자. 과 같이 이들은 1, 2, 3으로 표시되어 있고, 동근이는 X로 표시한 위치에 있다.1번 상점에서 호출이 들어 왔을 때..
-
백준 2589번 보물섬 :: 마이구미알고리즘 풀이/그래프 2018. 1. 28. 18:05
이 글은 백준 알고리즘 문제 2589번 "보물섬" 을 풀이한다.풀이 방법으로는 BFS(너비 우선 탐색) 을 이용한다.문제 링크 - https://www.acmicpc.net/problem/2589BFS - http://mygumi.tistory.com/102 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이..
-
백준 11332번 시간초과 :: 마이구미알고리즘 풀이/수학 2018. 1. 28. 16:40
이 글은 백준 알고리즘 문제 11332번 "시간 초과" 를 풀이한다.정답 비율이 낮지만, 어려운 알고리즘을 요구하진 않는다.제목처럼 항상 시간초과를 고려했다면, 쉽게 문제를 해결할 수 있다.문제 링크 - https://www.acmicpc.net/problem/11332 유빈이는 코딩을 하다가 시간 초과가 났다. 그래서 시간 복잡도를 계산하기로 했다.채점 시스템은 1초에 100000000(108)가지 동작을 할 수 있다.여러분들은 유빈이를 도와 시간초과가 나는지 확인하는 프로그램을 작성하라. 입력의 첫 번째 줄에는 테스트 케이스들의 수 C가 주어진다.그 다음 C개의 줄에는 시간 복잡도를 나타내는 문자열 S, 각 테스트 케이스마다 입력의 최대 범위 N, 테스트 케이스의 수를 나타내는 T랑 제한시간(초 단위..
-
백준 1074번 Z :: 마이구미알고리즘 풀이/분할 정복 2018. 1. 26. 21:15
이 글은 백준 알고리즘 문제 1074번 "Z" 을 풀이한다.풀이 방법으 말하자면, 분할 정복 알고리즘이다.분할 정복이란, 문제를 작은 부분으로 쪼개어 해결하는 방식이다.문제 링크 - https://www.acmicpc.net/problem/1074 한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다.다음 예는 2^2 * 2^2 크기의 배열을 방문한 순서이다.N이 주어졌을 때, (r, c)를 몇..
-
백준 2529번 부등호 :: 마이구미알고리즘 풀이/그래프 2017. 12. 30. 15:58
이 글은 백준 알고리즘 문제 2529번 "부등호" 를 풀이한다.정올 초등부에서 출제된 문제이다.본인은 백트래킹을 활용해서 문제를 해결했다.문제 링크 - https://www.acmicpc.net/problem/2529 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자. A => 부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다. 3 1 7 0이 상황에..
-
백준 2477번 참외밭 :: 마이구미알고리즘 풀이/수학 2017. 12. 28. 00:44
이 글은 백준 알고리즘 문제 2744번 "참외밭" 풀이한다.정올 초등부, 중등부 문제에 출제된 문제이다.풀이는 수학적 사고를 요구하는 문제가 된다.문제 링크 - https://www.acmicpc.net/problem/2477 1m^2의 넓이에 자라는 참외의 개수는 헤아렸고, 이제 참외밭의 넓이만 구하면 된다. 참외밭은 ㄱ-자 모양이거나 ㄱ-자를 90도, 180도, 270도 회전한 모양(┏, ┗, ┛ 모양)의 육각형이다. 다행히도 밭의 경계(육각형의 변)는 모두 동서 방향이거나 남북 방향이었다. 밭의 한 모퉁이에서 출발하여 밭의 둘레를 돌면서 밭경계 길이를 모두 측정하였다.예를 들어 참외밭이 위 그림과 같은 모양이라고 하자. 그림에서 오른쪽은 동쪽, 왼쪽은 서쪽, 아래쪽은 남쪽, 위쪽은 북쪽이다. 이 그..