알고리즘
-
백준 11000, 2457 문제 풀이 (Feat. 그리디 & 파이썬)알고리즘 2024. 3. 8. 14:37
백준 11000번 강의실 배정 문제 설명 N개의 강의 중 i번째 강의가 si시간에 시작해 ti에 끝이난다. 최소의 강의실을 사용하여 모든 강의를 배정하는 방법을 구하는 문제입니다. 문제 풀이 모든 강의를 배정할 수 있는 최소 강의실 개수를 구하는 문제이므로 언제 강의실의 개수가 늘어나는지를 살펴보면됩니다. i번째 강의를 배정할 때 강의실의 개수가 늘어나는 경우는, 현재까지 생겨난 강의실의 마지막 강의가 끝나는 시간이 i 강의의 시작 시간보다 모두 늦은 경우입니다. 기존 강의실에 배정할 수 있는 경우 새로운 강의 C의 시작시간 S3가 두 강의실의 마지막 강의가 끝나는 시간 T1, T2 중 T1보다 크므로 강의실 1에 강의 A가 끝난 뒤 배정하면 됩니다. 새로운 강의실을 배정해야 하는 경우 새로운 강의 C의..
-
백준 7579번 앱 (Feat. Python)알고리즘 2024. 3. 4. 11:20
문제 설명 핸드폰의 앱이 활성화 상태로 놓여있을 때 새로운 앱을 실행하면 필요한 메모리 공간만큼 활성화 상태인 앱들을 종료해야 한다. 활성화 상태인 앱들은 다시 실행할 때 드는 비용이 각각 정해져 있을 때, 새로운 앱이 실행되는데 필요한 공간을 확보하고 이 비용을 최소로 하는 방법을 구하는 문제입니다. 아이디어 냅색 알고리즘을 사용할 수 있는 문제입니다. 냅색 알고리즘 가방 안에 넣을 수 있는 무게가 M이고 가방에 넣을 수 있는 물건들의 무게와 물건을 넣었을 때의 가치가 각각 정해져 있을 때 가방안에 물건을 넣어 만족할 수 있는 최대 가치를 구하는 알고리즘입니다. 냅색 알고리즘을 풀 때 가장 헷깔렸던 것 중 하나는 분해를 어떠한 방식으로 진행해야 하는지 입니다. A, B, C, D 물건을 가방에 넣는다고..
-
백준 알고리즘 풀이 모음 14590, 2469, 1107 (Feat Python)알고리즘 2023. 11. 22. 15:58
백준 14590번 KUBC League (Small) N명의 정회원들이 리그에 참여하여 N(N-1)/2번의 경기를 진행하고, 1번 선수가 자신이 이긴 사람과 해당 사람이 이긴 사람들의 꼬리를 무는 선수 나열을 통해 얻을 수 있는 최대 길이 L을 출력하는 문제입니다. 문제 조건 2 (1번 선수에게 진 선수에게 진 선수)가 이긴 선수 -> ... 방향으로 탐색하여 최대 길이를 구합니다. DFS를 통해 최대 길이를 구합니다. 2. 최적화 방법 각 선수마다 위처럼 자신에게 진 선수를 나열했을 때의 최대 길이를 가지고 있을 것이고 이는 변하지 않습니다. -> 캐싱을 통해 어떤 선수가 이미 자신에게 진 선수들을 나열해 최대 길이를 가지고 있을 경우 이를 바로 활용하여 더 탐색하지 않고도 최대 길이를 반환할 수 있도..
-
백준 23289번 온풍기 안녕! (Python)알고리즘 2023. 10. 14. 12:30
R*C인 격자판에 온풍기를 놓고 바람을 통해 각 칸을 따듯하게 할 때, 조사하려는 모든 칸의 온도가 K 이상이 될 때까지 먹는 초콜릿의 개수를 구하는 문제입니다. 가장 처음 모든 칸의 온도는 0도 입니다. 다음과 같은 순서대로 작업이 시행됩니다. 1. 집에 있는 모든 온풍기에서 바람이 한 번 나옵니다. 2. 온도가 조절됨 3. 온도가 1이상인 가장 바깥쪽 카의 온도가 1 감소 4. 초콜릿을 하나 먹는다 5. 조사하는 모든 칸의 온도가 K 이상이 되었는지 검사. 모든 칸의 온도가 K이상이면 테스트를 중단하고, 아니면 1부터 다시 시작합니다. 1. 바람이 나오는 과정 바람이 나오는 방향이 오른쪽이라면 위의 예시처럼 바람이 나오게 됩니다. (x,y)에 온풍기 바람이 도착해 온도가 k만큼 상승한다면, (x-1,..
-
백준 17825번 주사위 윷놀이 (Python)알고리즘 2023. 10. 13. 10:30
문제에서 주어진 게임판에서 주사위 윷놀이를 하는 게임입니다. 시작 칸에서 말 4개가 출발합니다. 말은 게임판에 그려진 화살표대로 이동할 수 있습니다. 단, 파란색 칸에서 출발하면 파란색 화살표를 타야합니다. 말이 도착 칸에 도달하면 주사위에 나온 수와 관계 없이 이동을 마칩니다. 게임은 10개의 턴으로 진행됩니다. 매 턴마다 1~5가 적혀있는 5면체 주사위를 굴리고, 도착 칸에 있지 않은 말을 하나 골라 주사위에 나온 수만큼 이동시킵니다. 말이 이동을 마치는 칸에 다른 말이 있으면 그 말을 고를 수 없습니다. 단, 이동을 마치는 칸이 도착 칸이면 고를 수 있습니다. 말이 이동을 마칠 때마다 적혀있는 수가 점수에 추가됩니다. 주사위에서 나오는 수 10개를 미리 알고 있을 때, 구할 수 있는 점수의 최대값을..
-
백준 17822번 원판 돌리기 (Python)알고리즘 2023. 10. 12. 12:32
N개의 원판을 돌리면서 조건에 맞는 번호를 지운 뒤 원판에 적혀있는 숫자의 총합을 구하는 문제입니다. 원판은 크기가 작아지는 순서대로 놓여있고, 원판의 중심은 모두 같습니다. 원판의 반지름이 i이면, 그 원판은 i번째 원판이라고 합니다. 각각의 원판에는 M개의 정수가 적혀있고, i 번째 원판에 적힌 j번째 수의 위치를 (i,j)로 표현합니다. 각 위치는 다음을 만족합니다. (i, 1)은 (i, 2), (i, M)과 인접하다. (i, M)은 (i, M-1), (i, 1)과 인접하다. (i, j)는 (i, j-1), (i, j+1)과 인접하다. (2 ≤ j ≤ M-1) (1, j)는 (2, j)와 인접하다. (N, j)는 (N-1, j)와 인접하다. (i, j)는 (i-1, j), (i+1, j)와 인접하다..
-
백준 21611번 마법사 상어와 블리자드 (Python)알고리즘 2023. 10. 11. 13:03
N*N 격자 상에서 마법사가 마법을 부릴 때, 폭파한 구슬의 번호의 개수를 센 뒤, 1*(폭발한 1번 구슬의 개수)+2*(폭발한 2번 구슬의 개수)+3*(폭발한 3번 구슬의 개수)를 구하는 문제입니다. N은 항상 홀수이고 맨 위 왼쪽 칸을 (1,1)이라 할 때, 마법사의 위치는 ((N+1)/2 , (N+1)/2)입니다. 위의 격자에서 점선은 지나갈 수 있는 길을 말하고 실선은 지나갈 수 없는 벽을 뜻합니다. 각 격자에는 1,2,3번 구슬이 한 개씩 들어있습니다. 단계 1. 얼음 파편으로 구슬을 파괴하는 단계입니다. 이 마법은 방향 di와 거리 si로 나타낼 수 있습니다. 방향은 (상, 하, 좌, 우)를 순서대로 1,2,3,4로 나타냅니다. 거리는 1 ≤ si ≤ (N-1)/2 의 크기를 가지고 있습니다...
-
백준 14890 경사로 (Python)알고리즘 2023. 10. 10. 11:36
크기가 N * N 인 지도에서 각 행과 열마다 길을 놓을 수 있을 때 조건에 맞게 만들 수 있는 길의 개수를 구하는 문제입니다. 길이 완성되는 조건은 다음과 같습니다. 길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 같아야 합니다. 높이가 차이나는 길은 경사로를 놓아서 길을 만들 수 있습니다. (경사로의 높이는 항상 1입니다.) 경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야합니다. 낮은 칸과 높은 칸의 높이 차이는 무조건 1이어야 합니다. 경사로를 놓을 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 합니다. 경사로를 놓을 수 없는 조건은 다음과 같습니다. 경사로를 놓은 곳에 또 경사로를 놓는 경우 낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우 낮은 지..