Algorithm
-
백준 17267번: 상남자 (Python/Java)Algorithm/Algorithm Problem 2022. 3. 12. 19:32
https://www.acmicpc.net/problem/17267 17267번: 상남자 CTP의 대표 상남자 영조는 자유롭게 이동하는 것을 좋아한다. 그렇지만 영조는 상남자이기 때문에 위아래로만 간다. 따라서 위, 아래로는 얼마든지 이동할 수 있지만 왼쪽, 오른쪽으로는 이동하 www.acmicpc.net 접근 간단한 너비 우선 탐색 알고리즘처럼 보이지만, 좌우 이동 횟수 제한 조건에 의해 굉장히 까다로워진 문제. 구현 자체는 어렵지 않으니, 우선 평소와 같이 현재 좌표에서 상하좌우 이동해 Queue에 넣고, 다시 Queue에서 값 하나 꺼내 또 상하좌우 이동하고... 이런 방식으로 구현한다고 생각해보자. 물론 좌우 이동 횟수도 꼭 체크를 해줘야겠지? 이렇게 풀면 너무 간단하게 예제 답을 구할 수 있다...
-
백준 9019번: DSLR(Python/Java)Algorithm/Algorithm Problem 2022. 3. 11. 00:39
https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 접근 구현만 차근히 잘 해낸다면 어렵지 않게 풀 수 있는 너비 우선 탐색 문제. 때문에 굳이 풀이 방법을 포스팅할 필요가 있나 싶지만, 구현 방식에서 재밌는 아이디어가 있어 기록해놓기 위해 풀이를 작성한다. 문제에서 주어진 네 가지 명령 중, D와 S는 굉장히 쉽게 구현할 수 있다. D는 그냥 현재 값을 두배 한 다음에 10000으로 나눈 나머지를 가져가면 된다. '결과 값이 9999..
-
백준 12886번: 돌 그룹(Python/Java)Algorithm/Algorithm Problem 2022. 3. 9. 17:27
https://www.acmicpc.net/problem/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려 www.acmicpc.net 접근 이 문제가 너비 우선 탐색이라는 것을 생각만 해낸다면 어렵지 않게 풀 수 있는 쉬운 문제. 하지만 이를 구현해내는 부분에서 재미있는 아이디어가 두 가지 정도 있어 그 부분을 짚고 넘어가야겠다 생각했다. 우선 첫 번째로 세 개의 그룹에서 두 개의 그룹을 골라 확인하는 방법이었다. 물론 첫 번째와 두 번째, 첫 번째와 세 번째, 두 번째와 세 번째, 이렇게 세 개의 그룹을 각각 골라 직접 ..
-
백준 24513번: 좀비바이러스(Python/Java)Algorithm/Algorithm Problem 2022. 3. 6. 19:07
https://www.acmicpc.net/problem/24513 24513번: 좀비 바이러스 여기 $N$ x $M$ 격자 모양의 마을이 있다. 어느 날 세상에 좀비 바이러스가 창궐하여 바이러스가 빠르게 퍼져나가버린다. 바이러스에 대해 조사한 결과 세 종류의 바이러스가 존재했으며 각각 $1$ www.acmicpc.net 접근 간단한 너비 우선 탐색에 조건이 몇 가지 추가된 문제다. 그래프를 탐색하며 1번 바이러스, 2번 바이러스가 접근한 곳인지 체크하는 것은 어렵지 않은 부분이라 대부분의 사람들이 쉽게 구현할 수 있었을 것이라 생각한다. 중요한 것은 1번 바이러스와 2번 바이러스가 만나 3번 바이러스가 되는 경우를 구현하는 것이다. 이 부분은 방문 확인하는 배열을 3차원 배열로 만들어주어 구현했다. 문..
-
백준 3101번: 토끼의 이동(Python/Java)Algorithm/Algorithm Problem 2022. 2. 27. 00:45
https://www.acmicpc.net/problem/3101 3101번: 토끼의 이동 첫째 줄에 N, K가 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K ≤ 300,000) N은 행렬의 크기, K는 토끼가 점프한 횟수이다. 둘째 줄에는 'U','D','L','R'로 이루어진 문자열이 주어진다. 이 문자열의 길이는 K이며, 토 www.acmicpc.net 접근 이 문제의 중요 포인트는 '현재 토끼가 서있는 칸의 숫자'를 어떻게 찾아내냐는 것이다. 다들 알고리즘 문제를 풀며 생긴 소위 '짬바'가 있으니 벌써 감이 잡혔겠지만, 직접 표의 모든 부분을 구현하려고 하면 당연하게도 시간(혹은 메모리) 초과가 뜰 것이다. 최대 길이가 100,000이니 최대 길이로 문제가 나온다면 이에 따른 칸 수는 10..
-
백준 2931번: 가스관(Python/Java)Algorithm/Algorithm Problem 2022. 2. 21. 21:51
https://www.acmicpc.net/problem/2931 2931번: 가스관 www.acmicpc.net 접근 가장 간단하게 생각해보면, 각 칸마다 접근해서 인접 좌표의 블록 유형을 하나하나 확인해 끊겨있는지 확인하고 끊겨있다면 이를 이어 줄 수 있는 블록을 찾아 넣으면 된다. 단순 구현 문제기 때문에 이렇게 풀면 당연하게도 정답이 나온다! 나는 이 원리를 기본으로 코드 길이를 줄이고 더 효율적으로 작성할 수 있는 방법을 찾아보았다. 구현하면서 가장 신경 썼던 점은 해당 구간마다 블록 유형을 체크하지 않도록 하는 것이었다. 다시 말해 현재 탐색하는 구간의 블록이 "|"인지, "+"인지 체크하지 않아야 한다고 생각했다. 그렇다면 어떻게 해야 상하좌우와 연결되는 블록을 찾을 수 있을까? 내가 생각 ..
-
백준 9204번: 체스(Python/Java)Algorithm/Algorithm Problem 2022. 2. 17. 09:07
https://www.acmicpc.net/problem/9204 9204번: 체스 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 시작 위치 X와 도착 위치 Y가 주어진다. 각 위치는 두 글자가 공백으로 구분되어져 있다. 글자는 열, www.acmicpc.net 접근 우선 알아둬야 할 두 가지 전제조건이 있다. 체스에 관해 잘 모르더라도 문제를 풀다 보면 자연스럽게 눈치챘을 부분이다. 우선 비숍은 본인이 있는 지점의 색상과 같은 지점만 갈 수 있다는 것을 알아둬야 한다. 즉, 현재 비숍이 있는 발판이 검은색이라면 흰색 발판 지점은 어떤 경우의 수를 생각하더라도 절대 도착할 수 없다. 다음으로 알아둘 것은 비숍의 이동 횟수다. 문제 조건에서 '최대 4번 움직일..
-
백준 12931번: 두 배 더하기(Python/Java)Algorithm/Algorithm Problem 2022. 2. 13. 14:00
https://www.acmicpc.net/problem/12931 12931번: 두 배 더하기 모든 값이 0으로 채워져 있는 길이가 N인 배열 A가 있다. 영선이는 다음과 같은 두 연산을 수행할 수 있다. 배열에 있는 값 하나를 1 증가시킨다. 배열에 있는 모든 값을 두 배 시킨다. 배열 B가 주 www.acmicpc.net 접근 이런 형식의 문제는 여러 문제들을 통해서 몸소 확인했듯이, 0이 나열된 배열에서 목표 배열까지 만드는 것이 아니라, 목표 배열에서 역으로 연산해 0이 나열된 배열을 만드는 것이 훨씬 좋은 풀이 방법이다. 그렇다면 목표 배열을 기준으로 0으로 이루어진 배열을 만들어보자. 우선 주어진 연산을 반대로 생각해야 한다. 1을 더하는 것은 1을 빼는 것으로, 배열 전체를 2배로 만드는 ..