본문 바로가기

자료구조

 (9)
백준 7579 앱 - 파이썬 문제. 풀이. 냅색 알고리즘을 이용하는 문제이다. 우선dp 배열을 행은 켜진 app의 개수, 열은 cost들을 다 더한 값 만큼 생성해준다. 그리고 반복문으로 dp배열을 돌면서 다음과 같은 조건을 체크한다. 1) 현재 앱의 i번째 앱의 코스트가 j보다 크다면 끄지 못하므로 이전 행의 값을 가져온다. dp[i][j] = dp[i-1][j] 2) 현재 앱의 cost가 j보다 작거나 같을 경우 현재 앱을 껏을때의 메모리와 그렇지 않을 경우의 메모리 중 큰 값을 dp에 입력한다 dp[i][j] = max(memory+dp[i-1][j-cost] 3) 현재 dp[i][j[의 값이 M 이상이라면 현재 cost와 이전의 result 값을 비교해 더 작은 값을 저장한다. dp[i][j[ = min(result, j) ..
백준 14889 스타트와 링크 - 파이썬 풀이. 파이썬의 내장 라이브러리 itertools의 combinaition으로 조합을 구하여서 쉽게 해결할 수 있다. 또한 주의 하여야할 점이 팀에 구성멤버가 3명이상 넘어가면 각각의 멤버들의 조합에 대한 능력치들을 모두 구하여서 더해주어야한다. 소스코드. import sys import itertools def calc(comb, stats): # start팀과 link 팀 나누기 start = comb[0:len(comb)//2] link = comb[len(comb)//2:] link.reverse() result = 10000 for s, l in zip(start, link): sc = itertools.combinations(s, 2) lc = itertools.combinations(l, 2..
백준 11399 ATM - 파이썬 문제. 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된..
백준 1931 회의실 배정 - 파이썬 문제. 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력. 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 ..
1 자료구조 스택 스택(stack): 데이터의 삽입과 삭제가 한쪽 방향에서만 일어나는 구조. 가장 최근에 삽입된 데이터가 가장 먼저 삭제 되기때문에 후입 선출(LIFO: Last-In First Out)구조라고도 함. 스택은 배열을 이용하거나 연결리스트를 이용하여 구현가능 다음 그림은 스택의 동작 원리를 보여주는 그림이다. 스택의 초기상태가 다음과 같이 있다. 저 스택에서 데이터 4를 push 한다면 다음 그림과 같다. 스택은 후입 선출 구조이기 때문에 스택의 가장 윗 부분에 데이터가 쌓인다고 생각하면 편하다. 저 상태에서 pop 을 한다면 다음 그림과 같은 상태가 된다. 데이터의 삭제또한 한 방향에서 일어나기 때문에 가장 최근에 들어온 데이터 4가 삭제된다. 스택의 연산의 종류는 다음과 같다. 연산 설명 pop 데이터 ..
2. 파이썬 자료구조 튜플 튜플은 몇 가지를 제외하고는 리스트와 거의 비슷하다. 다른점은 아래와 같다. ● 리스트는 []으로 둘러싸지만 튜플은 ()으로 둘러싼다. ● 리스트는 그 값의 생성, 삭제, 수정이 가능하지만 튜플은 그 값을 바꿀 수 없다. 튜플의 예제는 다음과 같다. >>> a = () >>> a = (1, ) >>> a = (1, 2, 3) >>> a = 1, 2, 3 >>> a = ('a', 'b', ('ab', 'cd')) -인덱싱 >>> a = (1, 2, 3) >>> a[0] 1 >>> a[2] 3 -슬라이싱 >>> a = (1, 2, 3) >>> a[1:] (2, 3) -튜플 더하기 >>> a = (1, 2, 3) >>> b = (4, 5) >>> a + b (1, 2, 3, 4, 5) -튜플 곱하기 >>> a..
2.2 자료구조 큐(queue) - 원형 큐 원형 큐(Circle queue): 기존의 큐는 프론트 값이 계속 증가되면서 공간을 잡아먹는 문제가 있음, 원형큐는 연결리스트를이용하여 공간의 낭비 없이 큐를 구현한 것이다. 원형큐의 동작과정은 다음 그림과 같다. 원형 큐의 연산은 다음 표와 같다. 연산 설명 enQueue 큐에 데이터 삽입 deQueue 큐에 데이터 삭제 peek front 가르키는 데이터 확인 isEmpty 큐가 비어있는지 확인 isFull 큐가 꽉 차있는지 확인 다음은 파이썬을 이용한 원형큐 구현 소스코드이다. class CircleQueue: def __init__(self, size): self.data = [None] * size self.size = size self.count = self.rear = self.front =..
2.1 자료구조 큐(queue) - 선형 큐 큐(queue): 한쪽 방향으로 데이터가 삽입되고 반대 방향으로는 데이터가 삭제되는 구조. 큐는 가장 먼저 삽입된 데이터가 가장 먼저 삭제되므로 선입 선출(FIFO(First-in First-Out) 구조라고도 함. 1. 선형 큐(Linear Queue) 선형 큐는 가장 기본적인 큐로 선입 선출 구조를 가진다. 다음 그림은 선형 큐의 동작 과정이다. 큐는 위의 그림과 같이 동작을 한다. 다음 표는 큐의 연산이다. 연산 설명 enQueue 큐의 rear에 원소 삽입 deQueue 큐의 front에 원소 삭제 peek 큐의 front에 원소 확인 isEmpty 큐가 비어있는지 확인 파이썬으로 구현한 큐의 소스코드는 다음과 같다. class Queue: def __init__(self): self.data =..

티스토리툴바