728x90 반응형 개발공부 #알고리즘 공부 #BOJ #파이썬39 [BOJ] 1927번 최소 힙 / 사용언어 : 파이썬(python) ※ 문제링크 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net ※ 관련개념 및 참고사이트 [Python]우선순위 큐, heapq 큐나 스택과 비슷한 자료형이지만, 각 원소들은 우선순위를 가지고 있다. 우선순위 큐에서, 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다. 같은 우선순위를 가진 velog.io 해당문제는 우선순위 큐라는 자료구조의 개념을 알아야 풀 수 있는 문제였다. 파이썬에서는 해당 자료 구조를 구현하기 위해 heapq 패키지를 지원하고 있다. 자료구조의.. 2021. 12. 27. [BOJ] 11279번 최대 힙 / 사용언어 : 파이썬(python) ※ 문제링크 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net ※ 관련개념 및 참고사이트 [Python]우선순위 큐, heapq 큐나 스택과 비슷한 자료형이지만, 각 원소들은 우선순위를 가지고 있다. 우선순위 큐에서, 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다. 같은 우선순위를 가진 velog.io 해당문제는 우선순위 큐라는 자료구조의 개념을 알아야 풀 수 있는 문제였다. 우선순위 큐라는 개념부터 확실히 하기위해서 구글링을통해 우선순위 큐에 대한 조사를 하였고, .. 2021. 12. 27. [BOJ] 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 ※ 관련개념 및 참고사이트 Dynamic Programming: 배낭 채우기 문제 (Knapsack Problem) 도둑이 보석가게에 배낭을 메고 침입했다. 배낭의 최대 용량은 W이며, 이를 초과해서 보석을 담으면 배낭이 찢어질 것이다. 각 보석들의 무게와 가격은 알고 있다. 배낭이 찢어지지 않는 선에서 gsmesie692.tistory.com 해당 문제는 Knapsack 알고리즘과 D.. 2021. 12. 26. [BOJ] 5430번 AC / 사용언어 : 파이썬(python) ※ 문제링크 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net ※ 관련개념 [자료구조] 덱(Deque) 자료구조 덱 velog.io 해당 문제는 자료구조의 하나인 덱과 문자열 파싱을 활용하여 해결해야하는 문제였다. 덱을 간단하게 설명하면 앞과 뒤에 요소를 삽입하고 제거할 수 있는 형태의 자료구조이다. 단순하게 R명령(순서를 반대로 뒤집는 명령)을 수행할 함수를 만들어 popleft만으로 작성해도 코드는 정상적으로 작동하나 시간초과가 나왔다. 그래서 R명령의 상태를 기록할 변수를 만들고 마지막 출력 전까지는pop과 popleft를 번갈아 사용하고 R명령의 상태에 따라 .. 2021. 12. 26. [BOJ] 1966번 프린터 큐 / 사용언어 : 파이썬(python) ※ 문제링크 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net ※ 관련개념 큐 (자료 구조) - 위키백과, 우리 모두의 백과사전 ko.wikipedia.org 해당문제는 큐를 활용해서 풀어야하는 문제였다. 큐에 대해서 간단하게 설명하면, 선입선출(First In First Out)방식으로 변수들을 삽입하고 추출하는 방식의 자료구조이다. 파이썬에서는 collections의 deque라는 양방향 큐를 사용할 수 있는 함수가 있어 해당 함수를 사용하여 결과를 도출하였다. 해당 라이브러리가 없어도 리스트로 구현을 할 수는.. 2021. 12. 25. [BOJ] 1541번 잃어버린 괄호 / 사용언어 : 파이썬(python) ※ 문제링크 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 해당 문제는 그리디 알고리즘의 개념을 활용하면 풀 수 있는 문제였다. 최솟값을 만들기 위해서는 '-'뒤에 '+'가 존재하면, '+'연산을 우선적으로 처리하여 빼야할 값을 최대화 시켜주면 조건 달성이 가능했다. 풀이방법과 코드는 아래와 같다. 1. 입력값을 받은 후 replace함수를 활용하여 '-'부호를 '-('로 변환한 후 '-'로 분할하여 새로운 리스트를 만든다. 2. 새로운 리스트에 변수들 중 '('를 가지고 있는 요소들을 더한 값(mi).. 2021. 12. 24. [BOJ] 11399번 ATM / 사용언어 : 파이썬(python) ※ 문제링크 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 해당 문제는 그리디 알고리즘을 사용할 수 있는 문제로, 사실 그리디 알고리즘을 잘 몰라도 풀 수 있는 문제였다. 조건을 간단히 말하면, 인출시간이 짧은 사람부터 오름차순으로 정렬한 후 인출시간을 구하면 되는 문제였다. 풀이방법과 코드는 아래와 같다. 1. 입력값으로 받은 사람들의 인출시간으로 리스트를 만들고, 해당 사람들의 인덱스 리스트를 추가로 만든다. 2. 2개의 리스트를 합쳐 2차원 리스트를 만들고, 인출시간을 기준으로 리스트를 정렬해준다. 3. 해당 순서대로 인출시간 총합을.. 2021. 12. 24. [BOJ] 1931번 회의실 배정 / 사용언어 : 파이썬(python) ※ 문제링크 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 해당 문제는 그리디 알고리즘과 접목하여 풀어야하는 문제였다. 가능한 회의 수의 최댓값을 구해야하는 문제로, 정렬과 반복문을 통해 문제를 해결하였다. 처음에는 끝나는 시간만 오름차순으로 정렬하여 문제를 풀었는데, (0, 1) (1, 1)을 입력받았을 때, 정렬 후 (1,1) (0,1)로 정렬되어 잘못된 결과를 출력하는 문제가 있었다. 해당 문제를 해결할 방법을 고민하다 파이썬 정렬 함수의 기능 중 정렬기준을 2개이상으로 선정하여 정렬하는 방법이 있어 해당 방법을 사용하였다. 자세한 풀이방법과 코드는 아래와 같다. 1. 입력값을 받고, 해당 값으로 리스트를 생성한다. .. 2021. 12. 24. [BOJ] 11047번 동전0 / 사용언어 : 파이썬(python) ※ 문제링크 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net ※ 관련개념 탐욕법(그리디) 알고리즘 탐욕법(이하 '그리디') 알고리즘이란 현재 상황에서 가장 좋은 것(최선의 선택)을 고르는 알고리즘을 말합니다. 그리디 알고리즘은 동적 프로그래밍을 간단한 문제 해결에 사용하면 지나치게 많 velog.io 해당 문제는 그리디 알고리즘을 활용하여 푸는 문제였다. 사실 그리디 알고리즘이 정확히 무엇인지 몰라도 문제를 풀 수 있었으나, 그리디 알고리즘의 개념.. 2021. 12. 24. 이전 1 2 3 4 5 다음 728x90 반응형
