본문 바로가기
728x90
반응형

코딩

알고리즘 - Python / 백준 - 1931번 : 회의실 배정 1931번: 회의실 배정 (acmicpc.net) 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이 그리디 알고리즘로 풀어야 하는 문제인 것 같아 그리디 알고리즘에 사용될 수 있는 기준점이 뭐가 있나 살펴보았다. 회의 시간 , 회의 시작시간 , 회의 끝나는 시간 정도로 추려졌고 3가지 경우에 대해서 생각해본 결과 끝나는 시간으로 그리디 알고리즘을 진행하니 풀리는 문제였다. 회의가 끝나는 시간이 같은 경우들에서도 따로 정렬이 필요해 회의가 끝나는 시간으로 정렬하고 이후 회의가 시작하는 시간으로 한번더 정렬을 해 그리디 알고리즘을 진행하였다. import sys n = int(sys.stdin.readline()) stack.. 더보기
알고리즘 - Python / 백준 - 1541번 : 잃어버린 괄호 1541번: 잃어버린 괄호 (acmicpc.net) 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 풀이 숫자 , + , - 로만 이루어진 식에 적절히 괄호를 추가해 식의 값이 최소가 되도록 하는 문제이다. 떠오른 아이디어는 -가 나오면 다음 -가 나올때 까지의 +와 숫자로 이루어진 식을 묶어 모두 -에 속하도록 처리하는 것이었고 , 이를 통해 문제를 해결하였다. 다 풀고나서 코드를 보니 +와 숫자로만 이루어진 식을 계산할 때 , eval() 함수를 사용할 걸 그랬다. 문제의 태그를 보니 그리디 알고리즘.. 더보기
알고리즘 - Python / 백준 - 11286번 : 절댓값 힙 11286번: 절댓값 힙 (acmicpc.net) 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 최소힙 , 최대힙 문제와 비슷한 절댓값 힙 문제이다. 파이썬에서 힙은 heapq 모듈을 통해 쉽게 구현할 수 있다. 음수와 양수를 모두 입력받고 절댓값이 작은 값을 내보내므로 힙에 (입력값의 절댓값 , 정수 값) 으로 저장한다. 이후 입력값이 절댓값 기준으로 pop을 진행하면 정답 import sys import heapq heap = [] n = int(sys.stdin.readline.. 더보기
알고리즘 - Python / 백준 - 11279번 : 최대 힙 11279번: 최대 힙 (acmicpc.net) 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 풀이 최대힙을 구현만 하면 되는 문제이다. 최대힙은 최소힙 구현에서 입력되는 수들에 -1 만 곱해주는 방식으로 간단하게 구현할 수 있다. 전 문제에서 만든 최소힙을 활용해 입력되는 수들에 push , pop 단계에 -1 만 곱해주도록 하면 된다. import sys import heapq heap = [] n = int(sys.stdin.readline()) for _ in range(n): m .. 더보기
알고리즘 - Python / 백준 - 1927번 : 최소 힙 1927번: 최소 힙 (acmicpc.net) 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 최소힙을 구현만 하면 되는 문제다. 파이썬에서 최소힙은 heapq 모듈을 통해 쉽게 구현할 수 있다. 구현만 하고 입력에 따라 push , pop 을 진행하면 된다. import sys import heapq heap = [] n = int(sys.stdin.readline()) for _ in range(n): m = int(sys.stdin.readline()) if m == 0: if .. 더보기
알고리즘 - Python / 백준 - 11724번 : 연결 요소의 개수 11724번: 연결 요소의 개수 (acmicpc.net) 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 풀이 연결 요소의 개수를 구하는 문제이기에 BFS나 DFS로 풀면 된다고 생각하고 접근 DFS 해결하였고 , 연결된 노드들의 묶음을 찾는다고 생각해 그래프 - VISTIED 노드 를 반복해서 체크해 모든 노드를 돌았을 때 종료하도록 하였음 이렇게 구현한 후 예제를 확인하고 제출 하였는데 틀렸다고 나옴 , 반례를 찾아보니 연결이 되어있지 않는 노드.. 더보기
알고리즘 - Python / 백준 - 1260번 : DFS와 BFS 1260번: DFS와 BFS (acmicpc.net) 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 양방향 DFS와 BFS를 구현하기만 하면 되는 문제이다 DFS는 스택으로 , BFS는 큐로 구현하면 된다. 노드는 딕셔너리 안에 리스트 형태로 저장하고 , 양방향 이기 떄문에 2번 저장해준다. import sys n , m , k = map(int , sys.stdin.readline().split()) dic = {} def dfs(dic, root): visite.. 더보기
알고리즘 - Python / 백준 - 11047번 : 동전 0 11047번: 동전 0 (acmicpc.net) 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 풀이 문제를 읽어보고 동전의 합을 표현할 수 있는 가장 큰 단위부터 표현하면 풀 수 있다는 것을 발견했다. 이후 문제의 범위를 보니 최대 10개를 확인하는 범위가 크지 않은 그리디 알고리즘 문제이다. 모든 범위를 돌면서 넣을 수 있는 만큼의 동전을 그리디 알고리즘 방식으로 넣고 넣은 횟수를 더해 출력하면 된다. import sys n , k = map(.. 더보기
반응형

티스토리툴바