yunaaa's yunaaa's

Algorithm

• 백트래킹(BackTracking)

  Algorithm/Algorithm_Theory 2023. 1. 24. 19:21

  백트래킹(DFS) - 깊이 우선 탐색(DFS) 을 진행하면서 조건을 확인, 해당 노드가 유망하지 않으면 더 이상 탐색하지 않는 것을 말한다 1. 재귀를 진행하는 동안 사용될 깊이(depth)를 매개변수로 넣기 2. 재귀가 종료되는 시점에서 수행해야할 내용 3. 재귀가 진행중이면 가지치기(백트래킹)할 내용 출처 https://sojeong-lululala.tistory.com/184?category=1015520

  Read More
• 정렬(Sorting)

  Algorithm/Algorithm_Theory 2023. 1. 15. 10:54

  Insertion, 삽입 정렬(Insertion Sort) 힙 정렬(Heapsort) 선택 정렬(Selection Sort) 합병 정렬(Merge Sort)

  Read More
• 선형탐색(LinearSearch) & 이진탐색(BinarySearch)

  Algorithm/Algorithm_Theory 2023. 1. 12. 23:14

  선형탐색(LinearSearch) 리스트의 처음부터 끝까지 순서대로 하나씩 탐색을 진행하는 알고리즘 def linear_search(element, some_list): # 여기에 코드를 작성하세요 for e in some_list: if e == element: return some_list.index(e) return None print(linear_search(2, [2, 3, 5, 7, 11])) print(linear_search(0, [2, 3, 5, 7, 11])) print(linear_search(5, [2, 3, 5, 7, 11])) print(linear_search(3, [2, 3, 5, 7, 11])) print(linear_search(11, [2, 3, 5, 7, 11])) 이..

  Read More
• 재귀(Recursive)

  Algorithm/Algorithm_Theory 2022. 12. 11. 20:40

  # 재귀적으로 문제를 푼다는 것은 같은 형태의 더 작은 문제로 본 문제를 푼다는 것! ex) 5! = 1 x 2 x 3 x 4 x 5 , 5 factorial을 풀기 위해선 4factorial을 풀어야 한다 4! = 1 x 2 x 3 x 4, 4 factorial을 풀기 위해선 3 factorial을 풀어야 한다 3! = 1 x 2 x 3, 3 facotiral을 풀기 위해선 2factorial을 풀어야 한다 0! = 1 ============= 재귀적으로 문제를 풀때는 base case와 recursive case를 풀어야 한다

  Read More
• 배열(Array) - 배열고차함수

  Algorithm/Problems_Solving 2022. 12. 9. 08:18

  Array.prototype.sort Array.prototype.forEach arr.forEach(func(value, index, array)) value : 현재 순회 중인 요소 index : 현재 순회 중인 요소의 index array : 배열 객체

  Read More
• 백준(BeakJoon) - 1260_DFS와 BFS

  Algorithm/Problems_Solving 2022. 12. 3. 12:43

  from collections import deque def DFS(graph, visited, start_node): stack = deque() visited[start_node] = 1 # 스택에 넣는다는 표시 stack.append(start_node) while stack: current_node = stack.pop() print(current_node) visited[current_node] = True # 현재 노드를 방문 처리 for n in graphs[current_node]: if not visited[n]: DFS(graph, visited, n) def BFS(graph, visited, start_node): queue = deque() queue.append(start_nod..

  Read More
• 그래프(Graph)

  Algorithm/Algorithm_Theory 2022. 11. 30. 23:24

  용어정리 - 노드(Node) : 그래프에서 하나의 데이터 단위를 나타내는 객체. 원이 노드를 나타낸다 - 엣지(Edge) : 그래프에서 두 노드의 직접적인 연결 관계 데이터. 화살표가 엣지를 칭한다. 두 노드 사이에 엣지가 있을 때 " 두 노드는 인접해 있다 " 라고 표현한다 - 차수(Dimension) : 하나의 노드에 연결된 엣지들의 수. 노드를 떠나는 엣지의 수=> 출력 차수, 노드에 들어오는 엣지의 수 =>입력 차수 - 경로(route): 한 노드에서 다른 노드까지 가는 길 그래프 노드를 구현해보기 class StationNode: """지하철 역 노드를 나타내는 클래스""" def __init__(self, name, num_exits): self.name= name self.num_exits ..

  Read More
• 백준(BaekJoon) 2606 - 바이러스

  Algorithm/Problems_Solving 2022. 11. 27. 12:04

  # DFS로 문제풀기 computer = int(input()) line = int(input()) # 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수 # [[], [], []] graph = [[] for _ in range(computer+1)] visited = [False] * (computer + 1) # [[], [2,5], [1,3,5], [2], [7], [1,2,6], [5], [4]] for i in range(computer): if i !=0: node, num = map(int, input().split()) graph[node].append(num) graph[num].append(node) def dfs(graph, node, visited): visited[node..

  Read More