본문 바로가기

알고리즘

 (368)
[Python] 8286번 Road Network 2 https://www.acmicpc.net/problem/8286 8286번: Road Network 2 If no road network plan satisfying the conditions from the input exists, the first and only line of output should contain a single word BRAK - i.e., none in Polish. In the opposite case each of the lines in the output should contain a description of one bi www.acmicpc.net 23/09/23 차수열(Degree Sequence)의 개념을 익힐 수 있는 문제다. 여담으로 대회 개최를 준비하던 중..
[Python] 4563번 리벤지 오브 피타고라스 https://www.acmicpc.net/problem/4563 4563번: 리벤지 오브 피타고라스 피타고라스의 정리는 직각삼각형의 세 변의 관계를 나타내는 정리이다. 빗변의 길이를 C, 다른 두 변의 길이를 A, B라고 한다면 다음과 같은 식으로 쓸 수 있다. A2 + B2 = C2 세 변의 길이가 모두 자 www.acmicpc.net 23/09/07 정수론적 지식을 요구하는 문제로, 주어진 수의 범위에 대해서 어떻게 효율적인 시간으로 판별할 수 있을지 생각해야되는 문제이다. 문제 접근 방식: 당연히 문제에서 요구하는 바를 나이브하게 접근하면 주어지는 수의 범위가 매우 크기 때문에 시간초과를 받을 가능성이 매우 크다. 문제에서 요구하는 바를 다시 상기시켜보자. $A < B$이고, $A$의 값이 최대 ..
[Python] 23352번 방탈출 https://www.acmicpc.net/problem/23352 23352번: 방탈출 첫줄에 지도의 세로 크기 $N$($1 \le N \le 50$), 가로 크기 $M$($1 \le M \le 50$)이 공백을 두고 주어진다. 둘째 줄부터 $N$줄에 걸쳐 각 방들의 정보 $A$($0 \le A \le 9$)가 공백을 두고 주어진다. www.acmicpc.net 23/09/08 BFS와 브루트포스를 합친 문제로, 처음에 비효율적인 접근 방식으로 접근해서 삽질한 문제다. 문제 접근 방식: 기본적인 접근 방식은 BFS이다. 처음에는 시작점과 끝점의 모든 조합마다 BFS를 돌리는 방식을 택했다. 시간초과가 나서 보니, 경로에는 같은 점을 포함할 수도 있다는 말에 코드를 고치고 파이파이로 제출했더니 또 시간초..
[Python] 23843번 콘센트 https://www.acmicpc.net/problem/23843 23843번: 콘센트 광재는 전자기기 대여사업을 시작했다. 퇴근하기 전에 다음날 손님들에게 빌려줄 N개의 전자기기를 충전하려 한다. 사용 가능한 콘센트는 M개가 있고, 성능은 모두 동일하다. 전자기기들은 한 www.acmicpc.net 23/09/09 그리디적으로 생각하면 쉽게 풀 수 있는 문제다. 문제 접근 방식: 먼저 첫 번째 예제부터 살펴보자. 첫번째 예제는 $N = 5, M = 2$로 주어져 있고, $1 \ 4 \ 4 \ 8 \ 1$로 각 기기 별 충전 시간이 주어져 있다. 최소 시간은 $9$이다. 가장 오래 걸리는 $8$시간 짜리 기기를 첫 번째 콘센트에 꽂아 놓은 상태에서 $4$시간 짜리 기기 2개를 두 번째 콘센트를 통해 충..
[구름톤 챌린지] 4주차 20일차 연결 요소 제거하기 문제 $N \times N$ 크기의 2차원 배열이 있다. 2차원 배열의 $i$행 $j$열에 해당하는 칸은 $(i, j)$로 나타낸다. 처음에 이 배열의 각 칸에는 알파벳 대문자 또는 . 문자가 하나 적혀 있다. 상하좌우로 인접한 두 칸에 같은 문자가 적혀있는 경우, 두 칸은 연결되어 있다고 한다. 서로 연결된 칸들의 집합을 연결 요소라고 하고, 연결 요소의 크기는 그 연결 요소에 포함된 칸들의 개수와 같다. 구름이는 아래 작업을 $Q$번 수행하려고 한다. $(y_i, x_i)$ 칸을 고른 뒤, 그 칸에 알파벳 대문자 $d_i$를 쓴다. 구름이가 고른 칸은 . 문자가 적힌 칸임이 보장된다. 배열에 존재하는 모든 연결 요소의 크기를 계산한다. 만약 크기가 $K$ 이상인 연결 요소가 존재한다면, 그 연결 요소..
[Python] 16891번 탄성 충돌 / 22295번 twOBoOgEr https://www.acmicpc.net/problem/16891 16891번: 탄성 충돌 탄성 충돌은 운동 에너지가 보존되는 충돌이다. 일차원 상에서 질량이 m1, m2인 두 물체가 각각 속도(여기서 속도는 방향을 포함하는 양이다) u1, u2로 운동하다가 탄성 충돌하면 충돌 후 두 물체 www.acmicpc.net https://www.acmicpc.net/problem/22295 22295번: twOBoOgEr 채점 및 기타 정보 예제는 채점하지 않는다. www.acmicpc.net 23/09/01 두 문제는 코드가 완벽하게 같은 것은 아니지만, 거의 비슷한 코드로 해결할 수 있는 문제로, 해결 방법을 올려보고자 한다. 첫 번째 접근 방식: 첫 번째 접근 방식은 다음 영상을 참조했다. https:..
[구름톤 챌린지] 4주차 19일차 대체 경로 문제 플레이어는 $1$번부터 $N$번까지의 번호가 붙은 $N$개의 도시와 $M$개의 도로가 있는 나라에 살고 있다. 각 도로는 서로 다른 두 도시를 양방향으로 연결하고 있고, 주어진 도로만을 이용해 임의의 두 도시 사이를 이동하는 것이 가능하다. 플레이어는 차를 타고 $S$번 도시에서 $E$번 도시로 이동하려고 한다. 플레이어가 두 도시 사이를 이동할 때는 항상 가장 작은 수의 도시를 거치는 경로를 따라 이동한다. 예를 들어 아래 그림과 같이 도시와 도로가 주어지고, 플레이어가 1번 도시에서 4번 도시로 이동하려고 할 때는 항상 1 → 3 → 4의 경로를 따라 이동한다. 이 경우에는 출발 도시와 도착 도시를 포함해 총 세 개의 도시를 거쳐 이동할 수 있다. 1 → 5 → 2 → 4의 경로로 이동하는 것은..
[구름톤 챌린지] 4주차 18일차 중첩 점 문제 한 변의 길이가 $N$인 정사각형이 있다. 플레이어는 이 정사각형 위에 $M$개의 반직선을 그린 뒤, 두 반직선이 교차하는 점의 수를 세려고 한다. 플레이어가 반직선을 그리는 과정은 아래와 같다. 반직선을 그리기 시작할 칸 $(y, x)$를 정한다. $(y, x)$는 주어진 정사각형을 $1 \times 1$ 크기의 정사각형으로 나눴을 때, $y$번째 행의 $x$번째 열에 해당하는 칸이다. 반직선을 그릴 방향 $d$를 정한다. 방향은 상하좌우 중 하나이며, 항상 정사각형 테두리의 가로 혹은 세로와 평행하다. 반직선을 그린다. 반직선은 항상 시작 칸의 테두리에서부터 시작하며, 같은 칸을 지나는 평행한 직선이 서로 만나지 않도록 그린다. 아래 그림은 길이가 $4$인 정사각형 위에 다음 세 개의 직선을 그..

티스토리툴바