본문 바로가기
728x90
반응형

백준205

[백준] 1927번 : 최소 힙 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/1927 1. 문제 설명2. 풀이과정해당 문제는 백준 11279번 : 최대 힙 문제와 유사하다.이전 11279번 문제는 우선순위 큐에서 최댓값을 반환하도록 구현했다면 이번 문제는 최솟값을 반환하도록 구현해야 한다.기본적으로 우선순위 큐 자료구조를 구현하면 값들이 오름차순으로 정렬되어 저장되므로 그냥 값을 추가하고 저장된 큐 자료구조에서 값을 가져오면 최솟값이 반환된다. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys우선순위 큐 자료구조를 구현하기 위해 queue 모듈에서 PriorityQueue 함수를 불러온다. from queue import PriorityQueue입력할 연산의 개수를 입력.. 2024. 7. 27.
[백준] 11279번 : 최대 힙 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/11279 1. 문제 설명2. 풀이과정해당 문제는 자료구조 중 최대 힙을 이용하여 자연수를 배열에 넣거나 배열에서 가장 큰 값을 출력하고 값을 배열에서 제거하는 문제이다.문제는 최대 힙 자료구조를 구현해서 해결해야 하는데, 최대 힙 자료구조는 우선순위 큐 자료구조를 활용해 구현한다.우선순위 큐 자료구조를 활용해 값을 넣고 제거하는데, 기본 우선순위 큐는 오름차순으로 값이 정렬되어 값을 가져오면 저장되어 있는 값들 중 가장 작은 값을 가져오게 된다.하지만 해당 문제에서는 값을 가져올 때 가장 큰 값을 가져와야 하므로 우선순위 큐가 내림차순으로 정렬되어야 한다.하여 우선순위 큐에 값을 추가할 때 (기준, 값)과 같이 튜플 형태로 값을 추가한다.이때 기.. 2024. 7. 26.
[백준] 12015번 : 가장 긴 증가하는 부분 수열 2 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/12015 1. 문제 설명2. 풀이과정해당 문제는 주어진 수열을 순서대로 봤을 때 가장 긴 증가하는 부분 수열을 찾아 그 길이를 구하는 문제이다.수열의 값을 하나씩 불러오며 바로 이전 값보다 크면 바로 추가하고 이전 값보다 크지 않으면 해당 값이 들어갈 자리를 찾아 새로 저장한다.값이 들어갈 자리를 찾는 방법은 결과 수열을 저장한 리스트의 양쪽 끝을 기준으로 잡고 중간 지점을 찾아 해당 위치의 값과 비교한다.만약 넣을 값이 중간 위치의 값보다 크면 더 뒤쪽에 값을 넣어야 하므로 앞쪽 기준을 중간 지점 다음으로 옮긴다.반면에 넣을 값이 중간 위치의 값보다 크지 않으면 더 앞쪽에 값을 넣어야 하므로 뒤쪽 기준을 중간 지점으로 옮긴다.계속 반복하다가 앞.. 2024. 7. 25.
[백준] 2110번 : 공유기 설치 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/2110 1. 문제 설명2. 풀이과정해당 문제는 집에 정해진 개수만큼 공유기를 설치할 때 가장 인접한 두 공유기 사이의 최대 거리를 구하는 문제이다.가장 인접한 두 공유기 사이의 최대 거리를 구하려면 공유기가 설치된 집의 위치를 알아야 한다.공유기를 설치할 때 그 거리의 최소 거리인 1과 최대 거리인 가장 양끝에 위치한 두 집의 거리를 시작으로 하여 공유기를 설치하면서 최소 거리와 최대 거리를 계속적으로 수정해 나간다.공유기를 설치할 때는 최소 거리와 최대 거리를 통해 그 중간 거리를 구하고 공유기가 설치된 바로 이전 집에서 중간 거리보다 같거나 더 멀리에 있는 집에 공유기를 설치한다.이후 공유기가 설치된 집의 수가 공유기의 수보다 적으면 더 좁은.. 2024. 7. 24.
[백준] 1654번 : 랜선 자르기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/1654 1. 문제 설명2. 풀이과정해당 문제는 처음 가지고 있는 랜선의 개수에서 필요한 랜선의 개수만큼 생기도록 랜선을 자를 때, 만들 수 있는 랜선의 최대 길이를 구하는 문제이다.처음 가지고 있는 랜선의 길이에서 만들 수 있는 랜선의 최소 길이와 최대 길이를 정한 후, 그 중간 길이를 구하여 각 랜선을 중간 길이로 잘라 개수를 세어준다.만약 랜선의 개수가 필요한 랜선의 개수보다 적으면, 기준이 되는 중간 길이가 더 짧아야 하므로 최대 길이를 중간 길이 이전으로 변경한다.반면에 랜선의 개수가 필요한 랜선의 개수보다 많거나 같으면, 기준이 되는 중간 길이가 더 길어도 되므로 최소 길이를 중간 길이 다음으로 변경한다.최소 길이가 최대 길이를 넘기 전.. 2024. 7. 23.
[백준] 6549번 : 히스토그램에서 가장 큰 직사각형 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/6549 1. 문제 설명2. 풀이과정해당 문제는 히스토그램에서 가장 면적이 넓은 직사각형의 넓이를 구하는 문제이다.문제를 해결하기 위해서는 스택 자료구조를 활용하여 히스토그램의 막대를 하나씩 가져와 2가지 과정을 수행한다.우선 첫 번째 과정은 히스토그램의 막대를 하나씩 가져오며 이전 막대의 길이보다 작은 막대가 나올 경우 현재까지 막대의 중에서 가장 큰 직사각형의 넓이를 구한다.두 번째 과정은 이전 막대보다 크거나 같은 길이의 막대가 나올 경우 해당 막대를 스택에 추가한다.첫 번째 과정에서 가장 큰 직사각형의 넓이를 구할 때는 현재 막대의 길이보다 큰 막대들만 가지고 가장 큰 직사각형의 넓이를 구해야 한다. sys.stdin.readline() 함.. 2024. 7. 22.
[백준] 11444번 : 피보나치 수 6 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/11444 1. 문제 설명2. 풀이과정해당 문제는 선형대수 지식이 요구되는 문제이다.피보나치 수를 행렬로 나타내면 아래와 같은 식으로 나타낼 수 있다.해당 행렬을 활용하여 피보나치 수를 10830번 : 행렬 제곱 문제와 동일하게 분할 정복 알고리즘으로 해결한다.피보나치 수를 행렬로 나타내는 선형대수 지식만 알고 있었다면 쉽게 해결할 수 있는 문제지만, 해당 선형대수 지식이 쉽게 떠오르지 않는다.해당 문제를 해결하면서 선형대수 지식을 다시 한번 상기시켜 봤다. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys구하고자 하는 피보나치 수의 번호를 입력받는다. N = int(sys.stdin.readl.. 2024. 7. 20.
[백준] 10830번 : 행렬 제곱 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/10830 1. 문제 설명2. 풀이과정해당 문제는 이전에 해결했던 2740번 : 행렬 곱셈 문제와 1629번 : 곱셈 문제를 함께 고려하면 문제를 해결할 수 있다.두 행렬을 곱하는 연산과 거듭제곱 연산을 분할 정복으로 해결하는 과정을 합치면 해결할 수 있다.각 행렬의 원소를 1,000으로 나눈 나머지를 구하는 문제이므로 두 행렬을 곱하는 연산에서 결과를 1,000으로 나눈 나머지로 저장한다.거듭제곱 연산에서는 1이면 기본 행렬을 반환하고, 1이 아닐 경우 짝수이면 두 행렬의 곱을 반환하고 홀수이면 두 행렬의 곱에 기본 행렬을 한 번 더 곱한 결과를 반환한다. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. imp.. 2024. 7. 19.
[백준] 2740번 : 행렬 곱셈 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/2740 1. 문제 설명2. 풀이과정해당 문제는 간단히 행렬 곱셈을 구현해 보는 문제이다.행렬의 곱셈은 앞 행렬의 행을 차례대로 가져오고, 뒷 행렬의 열을 차례대로 가져와 각 위치에 있는 숫자를 서로 곱하여 더하면 결과 행렬의 값이 된다.앞 행렬의 첫 번째 행 1, 2를 뒷 행렬 첫 번째 열 -1, 0을 각각 곱하여 더하면 1 x -1 + 2 x 0 = -1 이 되는 것이다.이런 방식으로 행렬을 곱하면 위 그림과 같은 결과가 나오게 된다.행렬의 곱셈 연산을 수행하는 함수를 구현하며 문제를 해결한다. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys첫 번째 행렬 A의 크기를 입력받는다. N, M .. 2024. 7. 11.
[백준] 11401번 : 이항 계수 3 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/11401 1. 문제 설명2. 풀이과정해당 문제는 이항 계수를 구하는 식 N! / (N - K)! * K! 을 1,000,000,007로 나눈 나머지를 구하는 문제이다.문제를 해결하기 위해서는 나머지 연산의 분배 법칙과 페르마의 소정리를 활용한다.분배 법칙은 (A x B) % p = ((A % p) X (B % p)) % p이다.페르마의 소정리는 p가 소수일 때 a^p = a % p를 의미하며, 양 변을 a^2로 나눠주면 a^(p - 2) = 1/a % p 가 된다.이를 활용하기 위해 N! / (N - K)! * K! 식을 곱셈으로 정리하면, N! * (N - K)! ^ -1 * K! ^ -1로 변환할 수 있고 이를 1,000,000,007로 나눈.. 2024. 7. 10.
728x90
반응형

티스토리툴바