분류 전체보기

https://www.acmicpc.net/problem/1700✔ 유형 : 그리디✔ 문제 풀이: 멀티탭에서 콘센트를 뽑을 때 어떤 우선순위로 뽑을지 기준을 올바르게 정해야함⬇️코드import sysinput = sys.stdin.readlineN, K = map(int, input().split())# N : 멀티탭 구멍의 개수, K = 전기 용품 총 사용 횟수schedule = list(map(int, input().split()))# 전기용품의 이름이 k이하의 자연수로 사용 순서대로 주어진다.multi_tab = [] # always len(multi_tab) == Nresult = 0#Schedule 순회for i in range(0, len(schedule)): # O(n) if sched..

지금까지는 인스트럭션들이 하나씩 순차적으로 실행되는 직선적인 코드 동작만을 다루어왔다. C의 일부 구문인 반복문, 스위치문들은 데이터에 적용된 실험 결과에 따라 일련의 연산이 실행되는 조건부 실행이 요구된다. 기계어 코드에서는 조건부 동작을 구현하기 위해 두 개의 기본적인 낮은 수준의 방법을 제공한다. 데이터 값을 실험해서 이 시험 결과에 따라 데이터흐름이나 제어흐름을 변경한다. C와 기계여 코드의 인스트럭션들은 모두 프로그램에 나타나는 순서대로 순차적으로 실행된다.하지만 기계어 인스트럭션들의 실행 순서는 점프Jump 인스트럭션으로 변경할 수 있다. 조건형 연산을 구현하는 두가지 방법3.6.1 조건 코드CPU = 정수 레지스터 + 단일비트 조건 코드로 구성된 레지스터 운영 조건부 분기를 수행하기 위해서 ..

1.5 캐시가 중요하다시스템은 정보를 한 곳에서 다른 한 곳으로 이동시키는 일에 많은 시간을 보낸다.1. hello 프로그램의 기계어 인스트럭션들( 하드디스크 저장 ) → 로딩 시 메인 메모리로 복사2. 프로세스가 프로그램을 실행할 때 인스트럭션들: 메인 메모리 →  프로세서로 복사여러 복사과정들이 프로그램의  "실제 작업"을 느리게 하는 Over Head   - 시스템의 디스크 드라이브는 메인 메모리보다 1000배 더 크기가 크지만, 프로세서가 디스크에서 1워드의 데이터를 읽을 때 걸리는 시간은 메모리에서보다 천만 배 더 오래 걸릴 수 있다.- 레지스터 파일은 수백 바이트의 정보를 저장하는 반면, 메인 메모리는 십억 개의 바이트를 저장한다.- 그러나 프로세서는 레지스터 파일의 데이터를 읽는데 메모리보다..

Knapsack Problem배낭의 최대 용량이 W일 떄, 배낭이 찢어지지 않는 선에서 가격 합이 최대가 되도록 보석을 담는 방법. - i 번째 보석이 배낭의 한도보다 무거우면 안되므로, i번째 보석을 뺀 i-1개의 보석들을 가지고 구한 전단계의 최적값을 그대로 가지고 온다.- 그렇지 않은 경우 , i번째 보석을 위해 i번째 보석 만큼의 무게를 비웠을 때, 최적 값에 i번째 보석의 가격을 더한 값 or i-1개의 보석들을 가지고 구한 전단계의 최적값 중 큰걸 선택한다.  12865. 평범한 배낭https://www.acmicpc.net/problem/12865import sysinput = sys.stdin.readline# 물품의 수, 배낭의 최대 무게N, K = map(int, input().spli..

Dynamic Programming(DP)동적 프로그래밍정의 : 여러개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘. ex) 피보나치 수열1️⃣ 재귀로 풀 때💡 재귀로 푼 다면 메모리 사용이 많이 커지고 같은 값을 중복으로 구하는 연산이 포함되어 있을 수 있어서 비효율적이다.def fibo(n): if n 2️⃣ DP를 사용했을 때    -1- Top Down 방식( Memorization) : 재귀재귀를 사용하지만 배열에 값을 저장해두기때문에 한번 구한 값은 다시 구하지 않아도 된다.def fibo(n, memo): if n     -2- Bottom Up  방식: for문O(1) 의 시간복잡도로 최종 값을 구할 수 있다.def fibo(N): if n  이 처..

https://www.acmicpc.net/problem/3055✔ 유형 : BFS✔ 문제 풀이: 시간당 고슴도치의 위치와, 시간당 물의 위치를 매 주기마다 업데이트 하고, 물도착시간이 고슴도치의 도착시간보다 느릴 때 고슴도치가 이동 가능함을 이용해 문제를 해결한다. 최소한으로 도착했을 때의 시간을 알아야 하기 떄문에 BFS를 사용한다. 코드import sysfrom collections import dequeinput=sys.stdin.readline # input함수 바꾸기# 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'# 비버의 굴 = D# 귀여운 고슴도치 = S# 매 분기 도치는 4방향중 한칸 이동가능. 물은 매분마다 비어있는 곳으로 확장. 한변을 공유하는 곳이면..

https://www.acmicpc.net/problem/2665✔ 유형 : 다익스트라✔ 문제 풀이: 문제에서 구하고자 하는 것은 최단 거리가 아니라 검은 방을 최대한 적게 지나야 하는 것이다.시작방에서 출발하여 길을 찾아서 끝방으로 가는 것이 목적인데,/ 아래 그림의 경우에는 시작방에서 끝 방으로 갈 수가 없다. 부득이 검은 방 몇 개를 흰 방으로 바꾸어야 하는데 되도록 적은 수의 방의 색을 바꾸고 싶다.문제에 흰 방에 대한 최소 기준이 없다. 이 문제의 목표는 1. 처음에서 끝으로 도달2. 검은 방을 적게 거침 다익스트라 : 하나의 시작점으로부터 다른 모든 정점까지의 최단거리를 구하는 알고리즘. 다익스트라 알고리즘을 이용하여 최단거리 = 검은방으로 바꾼 횟수로 문제를 해결하면 된다. 코드import ..

https://www.acmicpc.net/problem/2294 ✔ 유형 : DP✔ 문제 풀이: 여러개의 하위 문제를 먼저 푼후 그 결과를 쌓아올려 주어진 문제를 해결한다. 메모- 처음에 DFS로 풀었는데, 메모리 초과나서 방법을 찾다가 DP를 공부하고 DP로 풀었다. 근데 이게 정답인듯!!! DP 풀이1. 테이블 정의    D[i] = K 로 만들기 위해 필요한 연산 횟수의 최소값 2. 점화식    D[15] = D[14] + 1  ( 1을 더한 이유는 D[15-1]에 1을 더하는 연산 한번을 더하면 D[15]이기 때문)    D[15] = D[9] + 1  ( 1을 더한 이유는 D[15-6]에 5를 더하는 연산 한번을 더하면 D[15]이기 때문)    D[15] = D[3] + 1  ( 1을 더한 ..

https://www.acmicpc.net/problem/2637✔ 유형 : 위상 정렬✔ 문제 풀이:  위상 정렬을 이용한 최단거리느낌? 뭐라고해야하지ㅜㅜ 백준 Test Case를 분석해봤을 떄, ⬇️코드import sysfrom collections import deque input = sys.stdin.readlineN = int(input())M = int(input())Graph = { i : {} for i in range(1, N+1)} # 이중 딕셔너리!need = [0 for _ in range(N+1)] # indegree 개수를 센 리스트indegree = [0 for _ in range(N+1)]for i in range(M): X, Y, K = map(int, input().s..

https://www.acmicpc.net/problem/1707 ✔ 유형 : DFS✔ 문제 풀이: 이분 그래프의 특징을 이용해 DFS로 탐색해 나가며 조건에 위배 될 경우 탐색을 종료시킨다.- 방문하지 않은 노드를 탐색하려고 할 때 현재 노드와 다른 색으로 visited 배열에 저장을하고- 방문 했던 노드를 탐색하려고 할 때는, 자신과 같고 이어져 있다면 이분 그래프가 아니므로 탐색을 종료한다.  ✨ 주의 할 점1. 재귀를 쓰면 시간 초과가 날 수 있다.2. 모든 그래프가 연결 되어 있다는 보장이 없기 때문에, 전체 노드를 for문으로 탐색해야한다.  import sysfrom collections import defaultdictinput=sys.stdin.readline # input함수 바꾸기sy..

https://www.acmicpc.net/problem/11725 ✔ 유형 : DFS✔ 문제 풀이: 해당 노드와 연결된 노드들의 부모는 해당 노드라는 점을 이용해 배열에 자신의 부모 노드 번호를 저장한다. 백준의 테스트 케이스를 예시로 들어 설명하자면, 위와 같은 방법으로 계속 DFS를 돌리면 아래와 같이 부모 리스트가 채워진다.  ⬇️문제import sysinput=sys.stdin.readline # input함수 바꾸기sys.setrecursionlimit(10**5)# input N = int(input())Graph = {i: [] for i in range(1, N+1)}for i in range(N-1): u, v = map(int, input().split()) Grap..

https://www.acmicpc.net/problem/1197✔ 유형 : 최소 신장 트리, 크루스칼 알고리즘, union find✔ 문제 풀이: union find 알고리즘을 이용하여 거리가 최소인 간선과 정점을 선택하여 V-1개의 간선을 가진 부분 그래프를 만든다.  ⬇️코드 import sysinput=sys.stdin.readline # input함수 바꾸기# union find algorithmdef find_parent(parent,x): if parent[x] != x: parent[x] = find_parent(parent,parent[x]) return parent[x]def union(parent,a,b): a = find_parent(par..