본문 바로가기
728x90

티스토리챌린지21

백준 4-LSB [32685] 파이썬(Python) 코드 + 해설 1. 문제 소개스테가노그래피의 한 기법인 4-LSB를 이용하여, 척이가 은규에게 준 세 개의 십진수에서 화장실 비밀번호를 도출하는 문제다. 각 숫자의 4-LSB를 추출하고, 이를 이진수로 표현하여 순서대로 이어붙인 후, 다시 십진수로 변환하여 네 자리 비밀번호를 얻어야 한다.2. 문제 해결 방법입력받기: 세 개의 십진수를 입력받는다.4-LSB 추출: 각 숫자에 대해 4-LSB를 추출한다. 이는 숫자를 2진수로 변환한 후, 하위 4비트를 가져오는 것과 같다.이진수로 변환 및 이어붙이기: 추출한 4-LSB를 4자리의 이진수 문자열로 변환하고, 이를 순서대로 이어붙인다.십진수로 변환: 이어붙인 이진수 문자열을 십진수로 변환한다.비밀번호 생성: 변환된 십진수가 네 자리가 되도록 앞에 0을 붙여 비밀번호를 만.. 2024. 11. 18.
백준 대동여지도 [32339] 파이썬(Python) 코드 + 해설 1. 문제 소개세종이는 조선 시대의 지도인 대동여지도를 보며, 모든 지역을 연결하는 최소 비용의 도로를 설치하고자 한다. 도로에는 세 가지 종류가 있는데, 각각 도보 전용 도로(0), 말 전용 도로(1), 마차 전용 도로(2)이다. 세종이는 최소한의 비용으로 모든 지역을 연결하고자 하며, 만약 최소 비용의 방법이 여러 가지라면 주어진 우선순위에 따라 더 많은 우선순위의 도로를 포함하는 방법을 선택하려 한다.2. 문제 해결 방법이 문제는 최소 스패닝 트리(MST)를 찾는 문제다. 그러나 단순히 최소 비용의 스패닝 트리를 찾는 것에서 그치지 않고, 우선순위에 따라 도로의 종류를 최대화해야 한다.해결 전략은 다음과 같다:도로 우선순위 설정: 입력으로 주어진 도로 종류의 우선순위를 이용해 각 도로 종류에 대한 .. 2024. 11. 17.
백준 트리 장인 [32340] 파이썬(Python) 코드 + 해설 1.  문제 소개세종이는 정점 N개와 간선 M개로 이루어진 단순 그래프를 가지고 있다. 그는 이 그래프에 0개 이상의 간선을 추가하여 트리로 만들려고 한다. 간선을 추가할 수 있지만 기존의 간선을 제거할 수는 없다. 간선을 추가하는 방법의 가짓수를 구하고, 그 수가 K를 넘으면 −1을 출력하고, 그렇지 않으면 정확한 가짓수를 출력하는 문제다.2.  문제 해결 방법트리의 조건을 고려해보자. 트리는 사이클이 없는 연결 그래프다. 따라서 주어진 그래프를 트리로 만들기 위해서는 다음을 만족해야 한다:사이클이 없어야 한다: 기존 그래프에 사이클이 있으면 간선만 추가해서 트리로 만들 수 없다. 간선을 제거할 수 없기 때문이다.연결 그래프여야 한다: 모든 정점이 서로 연결되어 있어야 한다.따라서 주어진 그래프에서 사.. 2024. 11. 16.
백준 카드 뒤집기 게임 [32622] 파이썬(Python) 코드 + 해설 백준에 새롭게 추가된 한국어 문제 32622 카드 뒤집기 게임 정답 코드 및 해설입니다.  1. 문제 소개N개의 카드가 주어지고, 각 카드는 흰색 앞면(0) 또는 검은색 뒷면(1) 상태로 놓여있다. 우리는 선택적으로 처음 X개의 카드를 뒤집는 동작을 최대 한 번 수행하여, 뒤집은 후 카드 상태에서 연속된 같은 색상의 구간 중 가장 긴 길이를 점수로 삼는다. 카드 뒤집기 게임에서 얻을 수 있는 최대 점수를 구하는 문제다.2. 문제 해결 방법각 카드의 초기 상태(0 또는 1)가 주어진다.카드의 목표 점수는 뒤집기 후 연속으로 같은 색상(0 또는 1)인 가장 긴 카드 구간의 길이이다.최대 한 번, 1부터 X번 카드까지 뒤집을 수 있고, 이 때 X는 1 이상 N 이하인 정수다.뒤집기를 하지 않는 경우도 고려해야.. 2024. 11. 15.
백준 아카라카 2 [32652] 파이썬(Python) 코드 + 해설 문제 소개AKARAKA(아카라카)는 거꾸로 읽어도 같은 팰린드롬이며, 접두사이자 접미사인 "AKA" 또한 팰린드롬이라는 특징을 가진 문자열이다. 여기서 목표는 AKARAKA가 연속 부분 문자열로 정확히 K번 나타나는 가장 짧은 문자열을 찾는 것이다. 연속 부분 문자열은 원래 문자열에서 시작과 끝에서 문자를 임의로 제거하여 얻을 수 있는 부분 문자열을 뜻한다.예를 들어, K=1일 때는 "AKARAKA" 자체가 정답이 되고, K=2일 때는 "AKARAKARAKA"가 조건을 만족한다. 주어진 K값에 맞춰 AKARAKA가 중첩되도록 문자열을 구성해야 한다.문제 해결 방법AKARAKA가 정확히 K번 포함되도록 가장 짧은 문자열을 만들기 위해, 문자열의 중복을 최소화해야 한다. 이를 위해 첫 번째 "AKARAKA".. 2024. 11. 14.
백준 GLCCDM [32649] 파이썬(Python) 코드 + 해설 문제 소개양의 정수 𝐴, 𝐵, 𝐾가 주어질 때, 𝐾개의 서로 다른 양의 정수 수열 𝑑1 , 𝑑2 , ⋯ , 𝑑𝐾가 gcd ⁡ ( 𝑑1 , ⋯ , 𝑑𝐾 ) = 𝐴 와 lcm ⁡ ( 𝑑1 , ⋯ , 𝑑𝐾 ) = 𝐵를 만족해야 한다. 조건을 만족하는 수열을 찾고, 여러 개가 가능하다면 그 중 하나를 출력한다. 조건을 만족하는 수열이 없다면 -1을 출력한다.문제 해결 방법GCD와 LCM의 관계 활용:d1,d2,⋯ ,dK​의 최대공약수 A와 최소공배수 B가 정해져 있기 때문에, 수열의 각 요소는 A의 배수여야 하며, 전체 최소공배수가 정확히 B가 되도록 구성해야 한다.조건 만족 여부 검토:B가 A의 배수가 아니면, 조건을 만족하는 수열이 존재할 수 없으므로 바로 -1을 출력한다.후보군.. 2024. 11. 13.
백준 gcd와 최단 경로 [32632] 파이썬(Python) 코드 + 해설 문제 설명정점이 1번부터 N번까지 있는 그래프가 주어진다. 두 정점 x와 y 사이에 간선이 존재하는 조건은 gcd⁡(x,y)=1일 때이다. 즉, 서로소인 정점들 사이에 간선이 존재한다.정점 x에서 정점 y까지의 최단 경로 길이 dist(x,y)는 경로에 포함된 간선의 개수로 정의된다. 경로가 존재하지 않으면 dist(x, y) = 10^{10^{10}}으로 정의된다.정수 K가 주어질 때, 다음 조건을 만족하는 정수 x의 개수를 구해야 한다.1≤x≤Ndist(x,K)=gcd⁡(x,K)문제 해결 방법이 문제는 각 정수 x에 대해 dist(x,K)와 gcd⁡(x,K)를 비교하여 조건을 만족하는 x의 개수를 구하는 문제이다.그래프의 특성 분석간선의 존재 조건: 두 정점 x와 y 사이에 간선이 존재하려면 gcd⁡.. 2024. 11. 12.
백준 ABB to BA (Hard) [32293] 파이썬(Python) 코드 + 해설 문제 설명'A'와 'B'로만 구성된 문자열 S가 주어진다. 다음 동작을 더 이상 수행할 수 없을 때까지 반복한다:문자열 S에서 첫 번째로 등장하는 부분 문자열 "ABB"를 찾는다.그 위치를 i라고 할 때, 𝑆𝑖와 𝑆𝑖+1를 각각 'B'와 'A'로 바꾸고, 𝑆𝑖+2​를 문자열에서 제거한다.즉, "ABB"를 "BA"로 변환한다.문자열에 "ABB"가 더 이상 존재하지 않을 때까지 이 과정을 반복한다.반복이 끝난 후의 문자열 S를 출력하는 프로그램을 작성해야 한다. 문제 해결 방법이 문제는 문자열에서 특정 패턴("ABB")을 찾아 변환하는 작업을 반복적으로 수행해야 한다. 그러나 문자열의 길이가 최대 5×10^5이므로 단순한 탐색으로는 시간 초과가 발생한다.효율적인 해결을 위해 다음과 같은 방법을 사.. 2024. 11. 11.
백준 토마토 [7576] 파이썬(Python) 코드 + 해설 문제 설명철수의 토마토 농장에서는 M x N 크기의 격자 모양 상자에 토마토를 보관한다. 토마토 중에는 익은 토마토(1)도 있고, 익지 않은 토마토(0)도 있으며, 토마토가 들어있지 않은 칸(-1)도 있다. 익은 토마토는 하루가 지나면 인접한 네 방향(상, 하, 좌, 우)에 있는 익지 않은 토마토를 익게 만든다. 이때, 상자에 있는 모든 토마토가 며칠이 지나면 다 익는지, 그 최소 일수를 구하는 프로그램을 작성한다. 단, 처음부터 모든 토마토가 익어있으면 0을 출력하고, 모두 익지 못하는 상황이면 -1을 출력해야 한다.문제 해결 방법이 문제는 BFS(너비 우선 탐색)를 이용해 해결할 수 있다. BFS는 그래프의 모든 인접 노드를 방문하며 탐색하는 방법으로, 여러 단계에 걸쳐 확산되는 문제를 해결하는 데 .. 2024. 11. 10.
728x90

티스토리툴바