본문 바로가기
728x90
반응형

백준205

[백준] 1629번 : 곱셈 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/1629 1. 문제 설명2. 풀이과정해당 문제는 큰 수의 거듭제곱을 어떤 수로 나눈 나머지를 구하는 문제이다.거듭제곱의 최종 결과를 가지고 나머지 연산을 하면 큰 숫자일 경우 그 계산이 쉽지 않다.하여 거듭제곱을 전부 계산하기 전 작은 수일 때의 나머지 연산을 활용하여 최종 나머지 값을 구한다.A * B % C의 연산을 나눠보면 ((A % C) * (B % C)) % C의 연산과 동일한 결과가 나오게 된다.이를 활용해 거듭제곱의 나머지 연산을 구한다.문제에 나와있는 예시를 활용해 보면, 10^11 % 12 연산은 ( (10^5 % 12) * (10^5 % 12) * (10 % 12) ) % 12의 연산으로도 볼 수 있다.이를 더 작은 연산으로 나누.. 2024. 7. 9.
[백준] 1780번 : 종이의 개수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/1780 1. 문제 설명2. 풀이과정해당 문제는 -1, 0, 1로 이루어진 종이를 가로로 3등분, 세로로 3등분 총 9개의 조각으로 나누며 총 -1, 0, 1로만 이루어진 종이의 개수를 구하는 문제이다.해당 종이가 -1, 0, 1의 숫자 중에서 어떻게 구성되어 있는지 판단하고 만약 각각 -1, 0, 1로만 이루어진 종이라면 각 -1, 0, 1의 종이의 개수를 세어준다.반면에 해당 종이가 -1, 0, 1의 숫자 중 두 가지 이상의 숫자로 이루어진 종이라면 다시 9개의 조각으로 나누어 다시 판별하고 해당 종이의 개수를 세어준다.해당 문제는 분할의 연장선으로 볼 수 있기 때문에 분할 정복 알고리즘으로 해결할 수 있다.종이가 어떤 숫자로 구성되어 있는지 .. 2024. 7. 8.
[백준] 1992번 : 쿼드트리 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/1992 1. 문제 설명2. 풀이과정해당 문제는 이전 "2630번 : 색종이 만들기" 문제와 매우 유사한 문제이다.0과 1로만 이루어진 영상을 각 4개의 영역으로 나누어 해당 구역을 쿼드 트리 구조를 이용하여 압축하는 문제이다.4개의 영역을 압축하여 그 결과를 차례대로 괄호 안에 묶어서 표시한다.2630번 문제와 유사하므로 동일하게 분할 정복 알고리즘으로 해결할 수 있다.해당 문제도 마찬가지로 나눈 4개의 영역이 하나의 값으로 압축되지 않는다면 다시 4개의 영역으로 나누어 압축 해야 하므로 분할 정복 알고리즘을 재귀적으로 사용하여 해결하였다. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys영상.. 2024. 7. 5.
[백준] 2630번 : 색종이 만들기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/2630 1. 문제 설명2. 풀이과정해당 문제는 색종이를 반으로 계속 자르면서 흰색 색종이와 파란색 색종이로 나누고 그 개수를 구하는 문제이다.색종이를 반으로만 계속 잘라 새로운 정사각형 모양의 색종이를 계속 판단하며 완전한 흰색 색종이, 파란색 색종이를 구분한다.이는 분할의 연장선으로 볼 수 있기 때문에 해당 문제를 분할 정복 알고리즘으로 해결할 수 있다.해당 문제에서 중요한 점은 매번 색종이를 반으로 나누어 새로운 정사각형 모양의 색종이를 만드는 것과 새롭게 만들어진 색종이가 완전한 흰색 색종이인지, 파란색 색종이인지, 섞여 있는 색종이인지 판별하는 것이다.하여 해당 중요한 2가지 부분을 각각 함수로 만들어 문제를 재귀적으로 해결하였다.  sy.. 2024. 6. 24.
[백준] 13305번 : 주유소 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/13305 1. 문제 설명2. 풀이과정해당 문제는 전형적인 그리디 알고리즘 문제라고 볼 수 있다.제일 왼쪽 도시에서 제일 오른쪽 도시로 가는데 최소 비용을 구하면 되는 문제이다.제일 왼쪽 도시에서 출발하여 주유를 하며 오른쪽 도시로 이동하면 되는데, 이때 2가지 경우가 존재한다.만약 해당 도시의 기름값이 제일 오른쪽 도착 도시를 제외한 나머지 도시의 기름값 중 최솟값이면 해당 도시에서 이동하려는 거리만큼 기름을 전부 넣으면 된다.반면에 해당 도시의 기름값이 최솟값이 아니라면 현재 도시 이후의 도시들 중 현재 도시의 기름값보다 낮은 기름값을 갖는 도시까지만 이동하고 또 기름을 넣어야 최소 비용으로 이동할 수 있다.이를 활용하면 최소 비용으로 제일 오.. 2024. 6. 8.
[백준] 25682번 : 체스판 다시 칠하기 2 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 http://https://www.acmicpc.net/problem/2568 1. 문제 설명2. 풀이과정해당 문제가 누적합 문제로 분류되어 있길래 어떻게 누적합으로 해결할 수 있을지 고민을 해보았지만 쉽게 해결방법이 떠오르지 않았다.이전 체스판 다시 칠하기 문제를 기억해 보면 기본적으로 체스판은 제일 위쪽 첫 번째 칸이 검은색인지, 흰색인지에 따라 2가지 경우를 고려해야 한다는 것을 알 수 있다.그리고 각 체스판의 칸에 대해 살펴보면 행 인덱스와 열 인덱스의 합이 짝수이면 시작 칸의 색과 동일해야 하고, 홀수이면 시작 칸의 색과 다른 색이어야 한다.이를 통해 각 2가지 체스판과 주어진 보드를 비교하여 색을 다시 칠해야 하는 부분과 칠하지 않아도 되는 부분을 구별한다. (구별은 칠해야 하면 1, 칠하지 .. 2024. 6. 2.
[백준] 16139번 : 인간-컴퓨터 상호작용 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제를 처음 풀었을 때는 그저 입력을 받고 문자열에서 해당 범위를 추출해 그 범위에서 문자의 개수를 구하는 방식으로 해결하였다. 해당 방법으로 문제를 해결하니 50점이 나왔다. 하여 어떻게 100점으로 문제를 해결할 수 있을까 고민하던 중 누적 합으로 해결하면 시간이 더 단축될 것 같았다. a~z를 0~25번 인덱스로 생각하여 한 행이 26칸이 되도록 2차원 리스트를 생성해 주어.. 2024. 1. 20.
[백준] 2559번 : 수열 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 1. 문제 설명 2. 풀이과정 문제에서 주어진 시간 제한은 1초이고 N의 최댓값은 100,000이다. 연속적인 날짜의 수가 따로 주어져 해당 날짜의 온도 합이 최대가 되는 값을 구해야 하는 문제이므로 매번 날짜의 온도 합을 구하려면 많은 시간이 소요될 것이다. 하여 투 포인터를 활용해 날짜의 온도 합을 단순 사칙연산으로 빠르게 구할 것이다. 연속적인 날짜의 시작과 끝 위치를 각각 지정하여 구간을 지정한 뒤, 첫 번째 구간의 온도 합을 저장한다. 이후.. 2024. 1. 13.
[백준] 12865번 : 평범한 배낭 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 구하는 문제이다. 먼저 첫 번째 물건까지만 고려하여 배낭에 넣었을 때, 무게가 6이므로 6일 때 가치가 13이다. 무게가 7인 경우에는 더 이상 넣을 물건이 없으므로 그대로 최대 가치가 13이다. 두 번째 물건까지 고려하여 배낭에 넣었을 때, 두 번째 물건의 무게가 4이므로 무게가 4일 때 최대 가치는 8이다.. 2024. 1. 7.
[백준] 9251번 : LCS - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 두 문자열의 부분 수열 중 가장 긴 부분 수열의 길이를 구하는 문제이다. 각 문자열을 2차원 리스트로 고려하여 해당 문자열까지 가장 긴 부분 수열의 길이를 저장해 나간다. 2차원 리스트는 각 문자열의 길이보다 1씩 크게 만들어 제일 앞에는 문자열을 빼는 경우를 생각한다. 초기 2차원 리스트는 위 배열처럼 나타낼 수 있다. [1][1] 위치에서부터 시작하여 마지막 칸까지 가장 .. 2023. 12. 29.
728x90
반응형

티스토리툴바