728x90 반응형 Baekjoon243 [백준] 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. [백준] 1753번 : 최단경로 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 시작점과 다른 노드와 관련된 최단 경로의 경로값을 구하는 문제이다. 다익스트라 알고리즘의 가장 기본적인 형태를 구현할 수 있는지 물어보는 문제라고 할 수 있다. 다익스트라 알고리즘의 핵심 이론 인접 리스트로 그래프 구현하기 인접 리스트에 연결한 데이터 자료형은 [노드, 가중치] 같은 형태로 선언하여 연결한 점도 잘 봐야 한다. 최단 거리 리스트 초기화하기 출발 노드는 0, 이외의 노.. 2024. 3. 10. [백준] 1948번 : 임계경로 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제에서는 출발 도시와 도착 도시가 주어지기 때문에 일반적인 위상 정렬이 아닌 시작점을 출발 도시로 지정하고 위상 정렬을 수행하면서 출발 도시에서 도착 도시까지 거치는 모든 도시와 관련된 임계 경로값을 구할 수 있다. 단, 해당 문제의 핵심은 1분도 쉬지 않고 달려야 하는 도로의 수를 구하는 것인데, 이를 해결하려면 에지 뒤집기라는 아이디어가 필요하다. (에지 뒤집기 아이디어는 그래프 문제에서 종종 .. 2024. 3. 9. [백준] 1516번 : 게임 개발 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제를 해결하기 위해선 어떤 건물을 짓기 위해 먼저 지어야 하는 건물이 있을 수 있다는 문장에 주목해야 한다. 각 건물을 노드라고 할 때, 그래프 형태에서 노드 순서를 정렬하는 위상 정렬 알고리즘을 사용하는 문제라는 것을 알아야 한다. 건물의 수가 최대 500, 시간 복잡도가 2초이므로 시간 제한 부담은 거의 없다. 입력 데이터를 바탕으로 필요한 자료구조를 초기화한다. 인접 리스트로 그래프를 표현하고 건물의 생산 시.. 2024. 3. 2. [백준] 2252번 : 줄 세우기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 학생들을 노드로 생각하고, 키 순서 비교 데이터로 에지를 만든다고 생각했을 때 노드의 순서를 도출하는 가장 기본적인 문제이다. 답이 여러 개일 때 아무것이나 출력해도 된다는 전제는 위상 정렬의 결괏값이 항상 유일하지 않다는 알고리즘의 전제와 동일하다는 것을 알 수 있다. 위상 정렬(topology sort) : 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘 위상 정렬.. 2024. 2. 24. 이전 1 2 3 4 5 6 ··· 25 다음 728x90 반응형
