본문 바로가기

알고리즘/백준 문제 풀이

 (338)
[Python] 30506번 가위 가위 가위 https://www.acmicpc.net/problem/30506 30506번: 가위 가위 가위 예제는 한 대결이 5번의 게임으로 이루어진 경우를 가정하며, 실제 문제와는 다름에 유의하라. 또한 예제는 입출력 작동 방식의 이해를 돕기 위해 의도적으로 줄 간격을 조정했으며, 실제 입 www.acmicpc.net 23/11/16 난생 처음 보는 알고리즘 태그로, 차분 공격이라는 알고리즘 기법을 사용하는 문제다. 차분 공격에 대한 내용은 별거 없고, 입력값에 따라 출력값이 미묘하게 변하는 것을 이용한 암호학에서의 기법이다. 자세한 내용은 아래 링크를 참조하자. https://en.wikipedia.org/wiki/Differential_cryptanalysis Differential cryptanalysis..
[Python] 30519번 짜고 치는 가위바위보 (Large) https://www.acmicpc.net/problem/30519 30519번: 짜고 치는 가위바위보 (Large) 가위바위보 챔피언십이 열렸다. 수많은 관중이 지켜보고 있다. 이 상황에서 lighter와 smallant는 가위바위보 챔피언십 결승에 도달했다. 하지만 둘은 어릴 적부터 너무 친한 친구라, 누가 이기든 별 www.acmicpc.net 23/11/05 내가 제작한 문제다. Small버전에 대한 해설은 아래 링크에 있으니 궁금하다면 확인해 보자. 2023.11.25 - [알고리즘/백준 문제 풀이] - [Python] 30518번 짜고 치는 가위바위보 (Small) 문제 접근 방식: 문제 제한을 주목해 보자. 이전 문제는 제한이 $N = 20$이었던 반면, 이 문제의 경우 $N = 1,000,..
[Python] 30518번 짜고 치는 가위바위보 (Small) https://www.acmicpc.net/problem/30518 30518번: 짜고 치는 가위바위보 (Small) 이 경우는 smallant가 기존에 주어진 PP를 그대로 사용하거나, 첫 번째 P만 취하거나, 두 번째 P만 취하여 결승을 진행한다면 관중들이 분노하지 않는다. www.acmicpc.net 23/11/05 내가 만든 문제다. 문제 접근 방식: 먼저 문제부터 읽어보자. 문제는 Large버전과 동일하다. 다만 제한이 조금 다르다. 제한에 주목해 보자. 제한은 $N = 20$까지인 것을 확인할 수 있다. 관객들이 분노하지 않는 경우는 오직 smallant가 내고자 하는 가위바위보 정보에 달려 있음을 알고 있고, 이를 부분적으로 취하는 경우의 수는 $2^N$개라는 것을 알고 있다. (부분집합의 ..
[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개를 두 번째 콘센트를 통해 충..
[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:..

티스토리툴바