본문 바로가기
728x90

Computer Science

[알고리즘] 백트래킹 (BackTracking)
Computer Science/Algorithms 2023. 1. 12. [알고리즘] 백트래킹 (BackTracking) 백트래킹이란? 재귀적으로 문제를 풀어나가는 알고리즘 특정 조건에 위배되면 가지치기를 함 ( 특정 노드를 제외하는 것 ) DFS를 사용하는 알고리즘 중에 백트래킹이 있다. ( DFS는 최적의 경로를 반환한다.) 백트래킹과 DFS의 차이점 DFS는 가능한 모든 경로를 탐색하므로, 가지치기를 하지 않는다. 백트래킹은 현재의 경로가 불필요하다면 다시 되돌아간다. DFS에서 조건문과 재귀를 통해 코드를 구현하면 백트래킹을 구현할 수 있다. 백트래킹의 구현, 예제 결론적으로 백트래킹은 DFS를 수행하고, 유망한 노드인지를 판단한 뒤 하위 노드로 이동하는 형식이다. 백트래킹을 이용한 문제 백준 - N과 M (1) https://walk-cat-dev.tistory.com/57
[자료구조] 큐(Queue)
Computer Science/DataStructure 2023. 1. 10. [자료구조] 큐(Queue) 큐(Queue)란? 양 쪽이 뚫린 통에서 한 쪽은 자료를 삽입, 다른 한 쪽으로 자료를 삭제하는 구조 스택과 반대로 FIFO ( First In Frist Out ) 의 구조 데이터는 Back ( Rear라고 부른다) 으로 들어와서 Front로 나간다. 예시) 키오스크 음식 주문 큐의 연산 Enqueue: 데이터를 삽입하는 과정 Dequeue: 데이터를 삭제하는 과정 ( 이 때 큐가 비어있는지 확인한 후 실행 ) peek: Front 위치에 있는 데이터가 어떤 값인지 return함 ( 이 때 데이터를 꺼내지는 않음 ) isEmpty: 현재 큐가 비어있는지 확인 큐의 구현 list를 사용한 구현 queue = [1, 2, 3] queue.append(4) print(queue) queue.pop(0) pr..
[자료구조] 스택 (Stack)
Computer Science/DataStructure 2023. 1. 8. [자료구조] 스택 (Stack) 스택이란? 한 쪽 끝으로만 자료를 넣고 뺼 수 있는 구조 LIFO ( Last In First Out ) 스택의 연산 push(item) : item 하나를 스택의 맨 윗 부분에 추가한다. pop() : 스택에서 맨 위에 있는 item을 제거한다. peek() : 스택의 맨 위에 있는 항목을 반환한다. isEmpty() : 스택이 비어 있다면 true를 반환한다. 스택의 구현 파이썬에서의 스택 이미 list[]로 구현되어있다. push(item) -> append(item) lst = [1, 2, 3] lst.append(4) print(lst) [1, 2, 3, 4] pop() -> pop() lst = [1, 2, 3] lst.pop() print(lst) [1, 2] peek() -> list[-..
Computer Science/DataStructure 2023. 1. 7. [자료구조] 선형 리스트 (Linear List) 선형 리스트란? 데이터를 일정한 순서로 나열한 구조 순차 리스트(Ordered List)라고도 한다. 입력순으로 저장하는 데이터에 적당한 구조다. 선형 리스트의 연산 선형 리스트 생성(데이터 추가) 함수 데이터 삽입 함수 데이터 삭제 함수 선형리스트의 구현 선형리스트를 쇼핑 장바구니에 비유하여 코드로 구현해보았다. 1. 데이터 추가 함수 basket = [] # 빈 리스트 생성 def add_data(grocery): # 데이터 추가를 위한 함수 basket.append(None) blen = len(basket) basket[blen - 1] = grocery add_data("사과") add_data("당근") add_data("감자") add_data("딸기") add_data("양파") print..
728x90

티스토리툴바