Algorithm/Algorithm Problem
-
백준 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번 부수었을 ..
-
백준 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부터 시작하니 정..
-
백준 4179번: 불! (Python/Java)Algorithm/Algorithm Problem 2022. 1. 25. 23:23
https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 접근 조금의 디테일만 다를 뿐 백준 5427번 불(https://www.acmicpc.net/problem/5427)과 완전 같은 문제. 해당 문제 풀이(https://codestation.tistory.com/14)를 참고하면 문제없이 풀 수 있을 것이다. 풀이 Python from collections import deque upDown = [-1, 1, 0, 0] leftRig..
-
백준 1541번: 잃어버린 괄호 (Python/Java)Algorithm/Algorithm Problem 2022. 1. 24. 23:34
https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 접근 괄호를 묶는다는 의미만 알면 쉽게 풀 수 있는 문제다. 다들 알다시피 수학에서 괄호는 '먼저 계산한다'는 뜻이다. 그렇다면 덧셈이 있는 곳에 괄호를 쳐 숫자들을 더해준다면 나중에 뺄 때는 숫자 한 개를 뺄 때보다 훨씬 더 큰 수를 뺄 수 있게 된다. 즉, 가장 작은 수를 만들 수 있다. 구현 또한 간단하다. '-'를 기준으로 나눠준다. 그리고 그 나눠진 문자열을 다시 '+'를 기준으로 ..
-
백준 2343번: 기타 레슨 (Python/Java)Algorithm/Algorithm Problem 2022. 1. 23. 20:52
https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 접근 이분 탐색 문제에서 가장 먼저 찾아야 할 것은 이분 탐색의 범위다. 최솟값과 최댓값을 알아야 둘로 나누어 탐색할 수 있기 때문이다. 이 문제에서 최솟값은 레슨 목록 중 가장 길이가 긴 레슨의 시간이다. 레슨은 나누어 저장할 수 없고 블루레이 하나에 무조건 저장이 되어야 한다. 어떤 레슨을 넣더라도 하나의 블루레이 디스크에 다 저장할 수 있으려면 블루레이 디스크가 레슨 중 가장 길이가 긴 레슨을 저장..