Algorithm/Algorithm Problem
-
백준 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배로 만드는 ..
-
백준 23031번: 으어어... 에이쁠 주세요..(Python/Java)Algorithm/Algorithm Problem 2022. 2. 12. 18:21
https://www.acmicpc.net/problem/23031 23031번: 으어어… 에이쁠 주세요.. 밤이 되면 어두워지는 다솔관에는 좀비가 나온다는 괴담이 있다. 그 좀비들의 정체는 바로 시험 기간에 공부하느라 지친 학생들이었다. 지친 학생들은 멀리서 보면 흡사 좀비이므로 학생 좀비 www.acmicpc.net 접근 다른 알고리즘을 활용할 필요도 없이 조건에 맞춰 구현만 해주면 되기 때문에 특별히 어려운 부분은 없다. 다만 주의할 점이 있다면 대학원 생을 만났을 때와 스위치에 접근했을 때, 동시에 사건이 일어난다면 무조건 스위치 키는 행위가 먼저 일어난다는 부분. 이 부분을 간과하고 순서를 다르게 풀이한다면 한동안 오류에서 헤맬 수 있다. 한 가지 더 체크해야 하는 부분. 내가 현재 위치를 탐색..
-
백준 17939번: Gazzzua(Python/Java)Algorithm/Algorithm Problem 2022. 2. 11. 10:32
https://www.acmicpc.net/problem/17939 17939번: Gazzzua 최대의 수익을 얻으려면, 일단 가격이 1, 5일 때 1개씩 사서 10일 때 샀던 코인 2개를 다 팔고, 이어서 가격이 2일 때 1개를 사고 4일 때 판다. 이 경우, 총 (10-1) + (10-5) + (4-2) = 16의 수익을 얻을 수 있 www.acmicpc.net 접근 실제 가상화폐든, 그리디 알고리즘의 가상화폐든 이득을 얻는 방법은 간단하다. 저점에서 사고 고점에서 파는 것이다. 만고불변의 진리. 그렇다면 이 문제는 어떻게 해결해야 할까? 저점에서 사고 고점에서 팔면 되지!! 우선 현재 주어진 값들 중에서 높은 값이 어디 있는지 확인한다. 그 고점이 나오기 전까지는 무조건 매입한다. 왜냐? 해당 고점..