Algorithm
-
백준 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 접근 실제 가상화폐든, 그리디 알고리즘의 가상화폐든 이득을 얻는 방법은 간단하다. 저점에서 사고 고점에서 파는 것이다. 만고불변의 진리. 그렇다면 이 문제는 어떻게 해결해야 할까? 저점에서 사고 고점에서 팔면 되지!! 우선 현재 주어진 값들 중에서 높은 값이 어디 있는지 확인한다. 그 고점이 나오기 전까지는 무조건 매입한다. 왜냐? 해당 고점..
-
백준 1930번: 정사면체 (Python/Java)Algorithm/Algorithm Problem 2022. 2. 7. 23:15
https://www.acmicpc.net/problem/1930 1930번: 정사면체 첫째 줄에 데이터의 개수 K(1 ≤ K ≤ 1,000)가 주어진다. 다음 K개의 줄에는 8개의 정수로 정사면체의 각 면의 색깔이 주어진다. 첫 수는 밑면의 색깔이고, 다음 수들은 옆면의 색이 시계방향으로 www.acmicpc.net 접근 두 정사면체가 같은지 확인하는 법을 구현하면 되는 문제. 간단하게 생각해보자. 정사면체는 이름 그대로 면이 네 개밖에 되지 않기 때문에 면 하나를 고정하고 그냥 순서대로 돌리면서 확인하면 된다. 예를 들어 각 면의 숫자가 1, 2, 3, 4라고 해보자. 여기서 1번 면을 바닥 면이라고 생각하면 나머지 나머지 면을 2, 3, 4라고 하든 3, 4, 2라고 하든 4, 2, 3이라고 하든 ..
-
백준 19952번: 인성 문제 있어?? (Python/Java)Algorithm/Algorithm Problem 2022. 2. 5. 17:17
https://www.acmicpc.net/problem/19952 19952번: 인성 문제 있어?? 인성이는 인싸가 되기 위해서 인싸트 특별과정에 참가했다. 훈련 첫날 인성이는 험난한 미로에서 목적지에 도달해야 하는 훈련을 받고 있다. 제한 시간 안에 미로를 통과하지 못하면 명기 교관 www.acmicpc.net 접근 전형적인 너비 우선 탐색 문제에 약간의 구현을 더한 문제다. 때문에 너비 우선 탐색 부분은 기본 개념을 찾아보는 걸로 하고, '약간의 구현' 부분을 살펴보도록 하자. 일반적으로 너비 우선 탐색을 할 경우, 시작 점에서 도착 점까지의 거리를 물어보는 경우가 많다. 그런데 여기서 물어보는 것은 내 남은 체력으로 목표 위치까지 갈 수 있는지 없는 지다. 때문에 체력을 매번 체크해줘야 한다. 만..
-
백준 14442번: 벽 부수고 이동하기 2 (Python/Java)Algorithm/Algorithm Problem 2022. 2. 2. 00:39
https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 접근 조건을 빼고 생각해보자면 간단한 너비 우선 탐색 문제다. 좌측 상단에서 우측 하단까지 경로를 찾아내는 것. 문제는 해당 경로까지 벽을 만났을 때 일정 횟수 부술 수 있다는 것이다. 이 부분을 구현해내는 것이 이 문제의 핵심 포인트다. 우리가 정확하게 알아야 할 것은 벽을 아예 부순 적이 없을 때, 한번 부수었을 때, 두 번 부수었을 때... N번 부수었을 ..
-
깊이 우선 탐색 (Depth-First Search, DFS)Algorithm/Algorithm Categories 2022. 1. 30. 16:34
기본 개념 '깊이 우선 탐색'은 '너비 우선 탐색'과 마찬가지로 그래프(혹은 트리와 같은 자료구조)를 탐색하는 방법 중 하나다. 루트 노드에서부터 접근할 수 있는 최대한 깊은 노드까지 탐색을 한 뒤, 전으로 돌아와 다른 노드의 끝까지 다시 탐색하는 방식을 반복해 탐색을 수행하는 알고리즘이다. 갈 수 있는 최대 깊이까지 탐색을 수행한 뒤, 다음 탐색으로 넘어간다는 알고리즘 수행 방식으로 인해 너비 우선 탐색에 보다 탐색 속도가 느리다. 하지만 특정 목표 노드가 있을 경우 해당 노드까지의 경로 혹은 도달 가능 여부를 빠르게 파악할 수 있다는 장점이 존재한다. 예시 위와 같은 총 7개의 노드를 가진 그래프를 예시로 생각해보자. 루트 노드는 A로 설정해보자. 이제 좌에서 우 순서로 깊이 우선 탐색을 진행하겠다...
-
백준 16432번: 떡장수와 호랑이 (Python/Java)Algorithm/Algorithm Problem 2022. 1. 30. 15:33
https://www.acmicpc.net/problem/16432 16432번: 떡장수와 호랑이 동희가 N일동안 호랑이에게 떡을 줄 방법이 있다면 i (1 ≤ i ≤ N) 번째 줄에 동희가 호랑이에게 주어야 할 떡을 출력합니다. 이 떡은 동희가 i번째 날에 만든 떡이어야 합니다. 만약 동희가 떡을 www.acmicpc.net 접근 구현 방법만 잘 파악하고 있다면 어렵지 않게 풀 수 있는 문제. 우선 오늘 받은 떡의 종류를 차례로 배열에 넣어준다. 이렇게 모은 각 날짜의 떡 종류 배열을 토대로 깊이 우선 탐색을 해준다. 이때, 체크해야 할 두 가지 조건이 있다. 첫 번째는 당연하게도 현재 날짜의 현재 떡에 접근한 적 있는지 탐색 여부다. 탐색 여부를 체크하지 않고 중복 방문을 허용한다면 연산이 기하급수적..
-
백준 11509번: 풍선 맞추기 (Python/Java)Algorithm/Algorithm Problem 2022. 1. 28. 12:02
https://www.acmicpc.net/problem/11509 11509번: 풍선 맞추기 첫 번째 예제 에서 [5,4,3] 을 터트리고 [2,1]을 터트리면 모든 풍선을 터트릴 수 있으므로 최소한 2개의 화살을 필요로 한다. www.acmicpc.net 접근 이 문제의 키포인트는 현재 높이의 화살과 이 화살이 풍선을 만날 수 있도록 체크하는 방법이다. 이 부분만 구현한다면 문제는 굉장히 쉽다. 우선 문제 조건을 확인해보자. 문제 조건에서 높이는 1에서 1000000까지다. 우리는 배열을 통해서 높이에 있는 화살 개수를 체크할 것이다. 이 경우에는 설정을 어떻게 해야 할까? 높이를 인덱스 번호로 두고 해당 인덱스에 들어있는 값을 화살의 개수로 두면 될 것이다. 물론 배열의 인덱스는 0부터 시작하니 정..