본문 바로가기
728x90
반응형

전체 글510

[백준] 11286번 : 절댓값 힙 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 1. 문제 설명 2. 풀이과정 N의 최대 범위가 100,000이므로 O(nlogn) 시간 복잡도 알고리즘으로 해결할 수 있다. 데이터가 새로 삽입될 때마다 절댓값과 관련된 정렬이 필요하므로 우선순위 큐를 활용해 문제를 해결한다. 하지만 해당 문제는 절댓값에 대한 정렬이 필요하므로 우선순위 큐의 정렬 기준을 직접 정의해야 한다. X = 0일 때, 큐가 비어 있으면 0을 출력한다. X = 0일 때, 큐가 비어 있지 않으면 큐에서 절댓값이 최소인 .. 2024. 1. 12.
[백준] 17298번 : 오큰수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1. 문제 설명 2. 풀이과정 N의 최대 크기가 1,000,000이므로 반복문을 사용해 오큰수를 찾으면 제한 시간을 초과하게 된다. 하여 스택을 활용해 문제를 해결하고자 한다. 오큰수가 존재하지 않는 수는 -1을 출력하므로 오큰수를 저장할 리스트를 -1로 초기화한다. 오큰수는 해당 수 다음 수들에서 찾아야 하므로 숫자들의 인덱스를 저장할 스택을 생성한다. 스택에 원소가 있고 스택의 제일 마지막 인덱스 위치의 값이 현재 인덱스 위치의 값보다 작으면(오른쪽에 있으면서 해당 값보다 큰 수 중 가장 왼쪽에 있는 수) 오큰수를 저장하는 리스트에서 스택의 제일 마지막 원소인 인덱스 위치에 해당 값을 저장한다. 현재 인덱스를 스택의 제일 마지막 원소로 추가한다. 해당 과정을 제일 마지막 인덱스까지 반복하며 오큰수를 .. 2024. 1. 11.
[백준] 11003번 : 최솟값 찾기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 일정 범위 안에서 최솟값을 구하는 문제로 슬라이딩 윈도우와 정렬을 사용하면 된다. 윈도우의 크기는 문제에서 최솟값을 구하는 범위가 i - L + 1부터 i까지이므로 L로 생각하면 된다. 최솟값을 찾기 위한 정렬을 O(nlogn)의 시간 복잡도를 가지므로 N과 L의 최대 범위가 5,000,000인 해당 문제에서는 정렬을 사용할 수 없다. O(n)의 시간 복잡도로 해결하기 위해 덱(deque).. 2024. 1. 10.
[백준] 12891번 : DNA 비밀번호 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 1. 문제 설명 2. 풀이과정 P와 S의 길이가 1,000,000으로 매우 크기 때문에 O(n)의 시간 복잡도 알고리즘으로 문제를 해결해야 한다. 부분 문자열의 길이가 P이므로 슬라이딩 원도우의 개념을 이용해 문제를 쉽게 해결할 수 있다. 슬라이딩 윈도우 알고리즘은 2개의 포인터로 범위를 지정한 다음 범위를 유지한 채로 이동하며 문제를 해결하는 알고리즘이다. 먼저 문자열의 시작 위치에 포인터를 하나 두고, 부분 문자열의 길이만큼 뒤에 포인터.. 2024. 1. 10.
[백준] 1253번 : 좋다 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 1. 문제 설명 2. 풀이과정 N의 개수가 2,000이라고 가정하면 좋은 수 하나를 찾는 알고리즘의 시간 복잡도는 N^2보다 작아야 한다. 좋은 수 하나를 찾는 알고리즘의 시간 복잡도는 최소 O(nlogn)이어야 한다. 하여 정렬, 투 포인터 알고리즘을 사용하여 문제를 해결할 수 있다. 단 정렬된 데이터에서 자기 자신을 좋은 수 만들기에서 제외해야 한다. 수를 입력받아 리스트 A에 저장한 후, 오름차순으로 정렬한다. 투 포인터 s, e를 배열 A 양쪽 끝에 위치시키고 A[s] + A[e]가.. 2024. 1. 9.
[백준] 1940번 : 주몽 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제의 시간 제한은 2초인데 N의 최대 범위가 15,000이므로 O(nlogn) 시간 복잡도 알고리즘을 사용할 수 있다. O(nlogn) 시간 복잡도 알고리즘을 사용할 수 있기 때문에 정렬을 사용할 수 있다. 하여 재료들의 번호를 입력받은 뒤, 오름차순으로 정렬하여 양쪽 끝의 위치를 투 포인터로 지정해 문제를 해결한다. 투 포인터 start, end를 정렬한 재료들의 번호 양쪽 끝에 위치시킨 후 포인터.. 2024. 1. 8.
[백준] 2018번 : 수들의 합 5 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 1. 문제 설명 2. 풀이과정 문제에서 주어진 시간 제한은 2초인데 N의 최댓값은 10,000,000으로 매우 크게 잡혀있다. 이러한 상황에서는 O(n)의 시간 복잡도 알고리즘을 사용해야 한다. 연속된 자연수의 합을 구하는 것이 문제이므로, 시작 값과 끝 값을 지정하여 연속된 수를 표현한다. (투 포인터) 시작 값과 끝 값을 모두 1로 두고 연속된 자연수의 합도 1로 저장한다. 두 위치를 끝까지 이동하면서 합이 N이 되는 경우의 수를 구한다.. 2024. 1. 8.
[백준] 10986번 : 나머지 합 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 1. 문제 설명 2. 풀이과정 N의 최댓값이 106이라 연산량이 작게 느껴질 수 있겠지만 106개의 수에 대하여 모든 구간 합을 구해야 하므로 1초 안에 연산하기는 어렵다. 나머지 합 문제 풀이의 핵심 아이디어는 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과 이 구산 합의 나머지 연산을 한 값은 동일해야 한다는 것이다. (A + B) % C = ((A % C) + (B % C)) % C S[i] % M.. 2024. 1. 7.
[깃 & 깃허브] 2. 깃으로 버전 관리하기 - 우당탕탕 개발자 되기 프로젝트 버전 : 깃에서 문서를 수정할 때마다 간단한 메모와 함께 수정 내용을 스냅숏으로 찍어서 저장하는 것 깃에서 가장 기본이자 중요한 기능이 버전들을 관리하는 것이다. 1. 깃 저장소 만들기 저장소(repository) : 깃으로 버전 관리를 하기 위해 폴더 안에 버전이 저장되는 공간이 필요 mkdir 명령으로 hello-git 디렉터리 생성 cd 명령으로 hello-git 디렉터리로 이동 ls -la 명령으로 디렉터리 안의 내용 살펴보기 마침표가 하나인 항목(.) : 현재 디렉터리 마침표가 두 개인 항목(..) : 상위 디렉터리 git init 명령 : 현재 디렉터리에서 깃을 사용할 수 있도록 초기화하는 것 해당 메시지가 나타나면 이제부터 hello-git에서 깃을 사용할 수 있다. 파일 경로 끝에 (mas.. 2024. 1. 7.
[백준] 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.
728x90
반응형

티스토리툴바