Algorithm
-
깊이우선탐색(DFS, Depth-First Search)Algorithm/Algorithm_Theory 2022. 11. 23. 23:55
DFS(Depth-First Search) - '깊이'를 우선적으로 탐색하는 알고리즘 - DFS를 구현하는 방식은 재귀(recursive) 방식과 스택(stack) 방식이 있다 # 재귀 dfs는 해당 노드의 주변 노드를 탐색할때 첫번째 노드부터 탐색 # stack dfs는 해당 노드의 주변 노드를 탐색할때 맨 뒤 부터 노드부터 탐색 (1) 시작 노드인 노드 1을 스택에 삽입하고 방문 처리 (2) 스택 내 최상단 노드인 노드 1에 인접한 노드는 2, 3이 있습니다. 번호가 낮은 노드 2를 스택에 삽입하고 방문 처리 (3) 스택 내 최상단 노드인 노드 2에 인접한 노드 8을 스택에 삽입하고 방문 처리 (4) 스택 내 최상단 노드인 노드 8에 인접한 노드는 6과 7이 있으며, 번호가 낮은 노드 6을 스택에 삽..
-
너비우선탐색(BFS, Breadh-Frist Search)Algorithm/Algorithm_Theory 2022. 11. 23. 23:37
BFS(Breadth-First Search) - 너비 우선 탐색이라고도 불리며 그래프에서 시작 노드에 인접한 노드부터 탐색하는 알고리즘 - 선입선출(First-in First-out) 방식의 큐(Queue) 자료를 이용 (1) 시작 노드인 노드 1을 큐에 삽입하고 1를 방문 처리 (2) 큐에서 노드 1을 꺼내고 노드 1과 인접한 노드 2, 3을 큐에 삽입하고 2,3 방문 처리 (3) 큐에서 노드 2를 꺼내고 노드 2와 인접한 노드 8을 큐에 삽입하고 8를 방문 처리 (4) 큐에서 노드 3을 꺼내고 노드 3과 인접한 노드 4, 5를 큐에 삽입하고 4,5을 방문 처리 (5) 큐에서 노드 8을 꺼내고 노드 8과 인접한 노드 6, 7을 큐에 삽입하고 6,7를 방문 처리 (6) 그래프 내 노드에서 방문하지 않은..
-
프로그래머스(Programmers) LEVEL1 - 같은숫자는싫어Algorithm/Problems_Solving 2022. 11. 15. 16:58
def solution(arr): idx = 0 result = [] while len(arr) != 0: if len(result) == 0: result.append(arr[idx]) arr.pop(idx) else: if result[-1] == arr[idx]: arr.pop(idx) else: result.append(arr[idx]) arr.pop(idx) return arr # 결과 채점 결과 정확성: 71.9 효율성: 0.0 합계: 71.9 / 100.0
-
스택(Stack)Algorithm/Algorithm_Theory 2022. 11. 14. 08:43
후입선출(Last In First Out, LIFO) 구조 => 늦게 들어온 데이터가 먼저 나간다 스택 연산 - 데이터간 순서 관계를 유지해야 한다 - 맨 뒤 데이터 추가 - 맨 뒤 데이터 삭제 - 맨 뒤 데이터 접근 스택 동작 과정 보기 코드로 스택 구현해보기 # deque는 python collections 모듈에서 가지고 온다 from collections import deque stack = deque() # 의 맨 끝에 데이터 삽입 stack.append("연아1") stack.append("연아2") stack.append("연아3") # 스택 출력 print(stack) # deque(['연아1', '연아2', '연아3']) # 맨 끝 데이터 출력 print(stack[-1]) # 연아3 #..
-
큐(Queue)Algorithm/Algorithm_Theory 2022. 11. 13. 23:57
선인섭출(First In First Out, FIFO) 구조 => 먼저 들어온 데이터가 먼저 나간다 큐 연산 - 데이터간 순서 관계를 유지해야 한다 - 맨 뒤 데이터 추가 - 맨 앞 데이터 삭제 - 맨 앞 데이터 접근 큐 동작 과정 보기 큐 구현은 2가지로 가능하다 1. 동적배열 2. 링크드 리스트 코드로 큐 구현해보기 # deque는 python collections 모듈에서 가지고 온다 from collections import deque queue = deque() # 큐의 맨 끝에 데이터 삽입 queue.append("연아1") queue.append("연아2") queue.append("연아3") print(queue) # deque(['연아1', '연아2', '연아3']) # 큐의 가장 앞 데..
-
백준(BaekJoon)_11052_카드구매하기Algorithm/Problems_Solving 2022. 11. 11. 09:24
cardNum = int(input()) profit_table = [0]*(cardNum+1) cardPrice = [0]+list(map(int, input().split())) # print(cardPrice) def solution(): # profit 0개는 항상 0... 1개는 price의 1개와 같기 떄문에 아래처럼 # 2개부터 경우의 수가 생긴다 profit_table[0], profit_table[1] = 0, cardPrice[1] for i in range(2, cardNum+1): for j in range(1, i+1): # j는 항상 i보다 작거나 같다. 따라서 i-j보다 작거나 같다. # profit_table보다 card_price으 값이 먼저 있어야 profit이 계산이 되..
-
백준(BaekJoon) 11407 - 동전Algorithm/Problems_Solving 2022. 10. 22. 12:39
def solution(number, money): result = [] for i in range(number): result.append(int(input())) cnt = 0 for coin in sorted(result, reverse=True): cnt += money // coin money = money % coin return cnt a, b = map(int, input().split()) print(solution(a,b))