완전 검색 (Exhaustive Search ) Brute-force = generate-and-test 모든 경우의 수를 나열해보고 확인하는 기법 조합 / 순열 / 부분 집합 조합과 순열, 중복 조합과 중복 순열 import java.util.Arrays; import java.util.Scanner; // 210204 public class Comb_Per_DiceTest { static int[] numbers; static int N, totalCnt; static boolean[] isSelected; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); // 주사위 던진 횟수 ..
시간복잡도
List 배열의 크기가 증가하거나 index 값이 작은 부분의 삽입, 삭제가 비효율적 append() : O(1) pop last : O(1) insert : O(n) delete : O(n) collections.deque append(), appendleft() : O(1) popleft(), pop() : O(1) from collections import deque dq = deque([1, 2, 3]) dq.append(n) dq.popleft()
알고리즘/자료구조 05 - BFS
BFS 루트 (시작점)에서 방문점까지의 거리를 알 수 있다. 루트의 거리는 0이다. import sys from collections import deque sys.stdin = open("input.txt", 'r') # 1 2 1 3 1 4 1 5 2 6 2 7 5 6 6 7 6 8 Data = list(map(int, input().split())) lenData = int(len(Data)/2) MyMap = [[0] * (lenData+1) for _ in range(lenData+1)] for i in range(lenData): row = Data[i*2] col = Data[i*2+1] MyMap[row][col] = 1 MyMap[col][row] = 1 visited = [0] * (l..
Queue https://jhk0307.tistory.com/137 import queue # 한쪽 방향에서 FIFO q = queue.Queue() q.put(x) # n = q.get() ## 리스트를 queue로 사용할 수도 있다. q = list() q.append(x) n = q.pop(0) # 맨 앞의 원소가 반환되나 시간 효율적으로 좋지 x https://jhk0307.tistory.com/139 from collections import deque dq = deque([1, 2, 3]) dq.append(n) dq.popleft()
알고리즘/자료구조 03 - DFS, 스택 DFS, 재귀 DFS
DFS 시작 정점에서 한 방향으로 가능한 정점까지 탐색해 나가다가, 더 이상 방문할 정점이 없다면 이전 정점으로 되돌아와서, 방문하지 않은 다른 방향의 정점으로 탐색한다. 바로 이전의 정점으로 되돌아가 탐색을 하기 때문에 LIFO의 스택을 이용한다. 즉, 스택에는 나중에 돌아올 곳을 기록하게 된다. 스택으로 DFS list.append(x)는 리스트 끝에 x 1개를 넣는다. list.extend(iterable)는 리스트 끝에 iterable의 모든 항목을 넣는다. # 입력 # 7 8 # 1 2 # 1 3 # 1 4 # 1 5 # 2 6 # 2 7 # 5 6 # 6 7 NodeNum, EdgeNum = map(int, input().split()) MyMap = [[] for _ in range(Node..
알고리즘/자료구조 02 - 재귀 함수, 팩토리얼, 하노이 타워
재귀함수 팩토리얼 https://www.acmicpc.net/problem/10872 n = int(input()) def factorial(num): if num Sparse # 2) 2번 (n번) : From -> To # 3) 1번 (1~n-1번) : Sparse -> To n = int(input()) move = [] def hanoi(num, F, S, T): if num == 1: move.append([F, T]) else: hanoi(num-1, F, T, S) move.append([F, T]) hanoi(num-1, S, F, T) # hanoi(n, 'From', 'Sparse', 'To') hanoi(n, 1, 2, 3) print(len(move)) # 총 횟수 for m in ..
Stack Stack은 LIFO (Last In First Out)의 선형 자료 구조 push, pop python에서는 list를 통해 list.append(x), list.pop()으로 사용한다. push, overflow ## push stack = [] for now in range(1, 6): stack.append(now) print(stack) # [1, 2, 3, 4, 5] ## overflow, push stack = [0]*3 top = -1 for now in range(1, 6): top += 1 if top >= len(stack): print("overflow") break stack[top] = now print(stack) # overflow # [1, 2, 3] pop, u..