티스토리

잡식성 개발자

검색하기

블로그 홈

잡식성 개발자

risingcurve.tistory.com/m

풀스택 개발자를 향하여

구독자: 1

방명록 방문하기

728x90

주요 글 목록

[알고리즘이론] 오일러 회로(Euler circuit) 파이썬으로 구현하기 오일러 회로(Euler circuit)는 그래프 이론에서 모든 간선을 한 번씩만 지나는 경로가 존재하는 그래프를 말합니다. 이러한 경로를 오일러 경로(Euler path)라고 부르기도 합니다. 오일러 회로를 찾는 알고리즘 중 하나인 Hierholzer 알고리즘을 파이썬으로 구현해보겠습니다. Hierholzer 알고리즘은 다음과 같은 단계를 따릅니다. 임의의 시작점을 선택하여 stack에 넣습니다. stack에서 노드 하나를 꺼내 이 노드에 연결된 간선들 중 아직 방문하지 않은 간선을 찾습니다. 해당 간선을 따라 다음 노드로 이동합니다. 이동한 노드를 stack에 넣습니다. 이동한 간선은 삭제합니다. 2~3번 과정을 반복합니다. 만약 더 이상 이동할 간선이 없다면 해당 노드를 result 리스트에 추가합니.. 공감수 1 댓글수 0 2023. 4. 6.
[알고리즘이론] 이진 트리(Binary Tree) 파이썬으로 구현하기 이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드를 갖는 트리 자료구조입니다. 이진 트리는 컴퓨터 과학 분야에서 널리 사용되며, 예를 들어 검색 트리, 힙(Heap), 트라이(Trie) 등을 구현하는 데 사용됩니다. 이진 트리를 파이썬으로 구현하는 방법은 여러 가지가 있지만, 가장 기본적인 방법은 노드 클래스와 트리 클래스를 따로 정의하는 것입니다. 각 노드는 자신의 값(value)과 왼쪽 자식 노드(left)와 오른쪽 자식 노드(right)를 갖습니다. 트리 클래스는 루트 노드(root)를 갖습니다. 아래는 이진 트리를 파이썬으로 구현하는 예시 코드입니다. class Node: def __init__(self, value): self.value = value self.left = .. 공감수 0 댓글수 0 2023. 4. 4.
[알고리즘이론] 다익스트라(Dijkstra) 파이썬으로 구현하기 파이썬에서 다익스트라(Dijkstra) 알고리즘을 구현하는 방법은 여러 가지가 있지만, 여기서는 우선순위 큐(priority queue)를 이용하여 구현하는 방법을 설명하겠습니다. 다익스트라 알고리즘은 그리디 알고리즘으로, 시작 정점에서부터 가장 짧은 경로를 가지는 정점부터 차례로 선택해가며 최단 경로를 구하는 알고리즘입니다. 이 알고리즘은 최소 힙(min heap)을 사용하는 우선순위 큐를 이용하여 구현할 수 있습니다. 아래는 파이썬으로 우선순위 큐를 이용한 다익스트라 알고리즘의 구현 예시입니다. 예제 1) import heapq def dijkstra(graph, start): pq = [] # 우선순위 큐 dist = {start: 0} # 최단 경로 길이를 저장하는 딕셔너리 heapq.heappu.. 공감수 0 댓글수 0 2023. 4. 1.
[알고리즘이론] 우선순위 큐(Priority Queue) 파이썬으로 구현하기 파이썬에서 우선순위 큐(Priority Queue)는 heapq 모듈을 이용하여 구현할 수 있습니다. heapq 모듈은 이진 힙(binary heap) 자료구조를 제공하며, 우선순위 큐는 이진 힙을 이용하여 구현됩니다. 이진 힙은 완전 이진 트리(complete binary tree)의 일종으로, 최솟값 혹은 최댓값을 빠르게 찾기 위해 구현된 자료구조입니다. 파이썬의 heapq 모듈은 기본적으로 최소힙(min heap)을 제공합니다. 따라서 최소값을 빠르게 찾을 수 있습니다. 최대값을 찾으려면 입력된 값에 대한 음수를 취하여 최소값을 찾은 후, 다시 음수를 취하는 방법으로 최대값을 구할 수 있습니다. 다음은 heapq 모듈을 이용하여 우선순위 큐를 구현한 예제입니다. import heapq pq = [].. 공감수 0 댓글수 0 2023. 3. 30.
[알고리즘이론] 슬라이딩 윈도우(Sliding Window) 파이썬으로 구현하기 슬라이딩 윈도우(Sliding Window)는 데이터 구조를 이용하여 고정된 크기의 윈도우(Window)를 일정 간격으로 이동시키면서 데이터를 처리하는 기법입니다. 이 기법은 배열, 문자열, 연결 리스트 등 다양한 자료형에 적용할 수 있으며, 주로 연속된 데이터의 부분집합을 찾거나, 부분집합을 이용한 최소 혹은 최대값 등을 찾을 때 사용됩니다. 파이썬에서는 리스트나 문자열 등의 자료형에서 슬라이싱(Slicing)을 이용하여 슬라이딩 윈도우를 구현할 수 있습니다. 슬라이싱은 연속된 일정 구간의 원소를 선택할 때 사용하는 파이썬의 기능으로, 다음과 같이 구현됩니다. lst = [1, 2, 3, 4, 5] window = lst[start:end] # start 이상 end 미만 구간 선택 위 코드에서 sta.. 공감수 0 댓글수 0 2023. 3. 29.
[알고리즘이론] 해밀턴 경로(Hamiltonian path) 파이썬으로 구현하기 해밀턴 경로(Hamiltonian path)는 그래프에서 모든 정점을 한 번씩만 방문하면서 이동하는 경로입니다. 파이썬으로 해밀턴 경로를 구하는 알고리즘은 다음과 같습니다. 그래프의 모든 정점에 대해, 해당 정점을 시작점으로 해서 DFS 탐색을 시작합니다. DFS 탐색에서, 이미 방문한 정점은 다시 방문하지 않도록 체크합니다. DFS 탐색에서, 모든 정점을 방문한 경우에는 해당 경로를 반환합니다. DFS 탐색에서, 방문하지 않은 정점을 선택해서 다음 DFS 탐색을 수행합니다. 파이썬 코드로 구현하면 다음과 같습니다. def find_hamiltonian_path(graph): def dfs(current, visited, path): visited[current] = True path.append(cur.. 공감수 0 댓글수 0 2023. 3. 28.
[알고리즘이론] 오일러 경로(Eulerian path) 파이썬으로 구현하기 오일러 경로(Eulerian path)는 그래프의 모든 간선을 한 번씩만 방문하면서 출발점과 도착점이 다른 경로입니다. 파이썬으로 오일러 경로를 구하는 알고리즘은 다음과 같습니다. 그래프가 오일러 경로가 되는지 확인합니다. 이를 위해서는 그래프가 무방향 그래프이고 모든 정점의 차수가 짝수이거나, 정확히 두 개의 정점의 차수가 홀수이어야 합니다. 오일러 경로가 있다면 시작 정점을 선택합니다. 시작 정점은 차수가 홀수인 정점 중 임의의 하나를 선택하거나, 그렇지 않으면 아무 정점이나 선택할 수 있습니다. 시작 정점에서 출발하여 갈 수 있는 경로가 있는 동안 이동합니다. 이동한 경로는 스택에 저장합니다. 이동한 경로의 마지막 노드에서 출발하여 갈 수 있는 경로가 있는 동안 이동합니다. 이동한 경로도 스택에 저.. 공감수 1 댓글수 2 2023. 3. 24.
[알고리즘이론] 그래프 파이썬으로 구현하기 파이썬에서 그래프를 구현하는 방법은 여러 가지가 있습니다. 이 중에서 대표적인 방법은 인접 리스트와 인접 행렬입니다. 인접 리스트 인접 리스트(Adjacency List)는 그래프를 연결 리스트로 표현하는 방식입니다. 파이썬에서는 딕셔너리를 이용하여 각 노드에 연결된 노드들을 리스트로 저장합니다. 예를 들어, 다음과 같은 인접리스트가 있다고 합시다. graph = { 'A': ['B', 'C'], 'B': ['A', 'C', 'D'], 'C': ['A', 'B', 'D', 'E'], 'D': ['B', 'C', 'E', 'F'], 'E': ['C', 'D'], 'F': ['D'] } 위 코드에서 graph 딕셔너리는 각 노드와 그에 대한 연결 리스트를 저장합니다. 예를 들어, 'A' 노드와 연결된 노드들.. 공감수 0 댓글수 2 2023. 3. 22.
[알고리즘이론] 백트래킹(Backtracking) 파이썬으로 구현하기 백트래킹(Backtracking)은 해를 찾는 도중에 가능성이 없는 부분을 차단하여 불필요한 탐색을 줄이는 알고리즘입니다. 파이썬에서는 다음과 같이 백트래킹 알고리즘을 구현할 수 있습니다. 예제: N-Queen 문제 N x N 크기의 체스판 위에 N개의 퀸을 놓는 문제입니다. 퀸은 가로, 세로, 대각선 방향으로 모두 공격할 수 있으므로, 서로 공격할 수 없도록 N개의 퀸을 놓는 문제입니다. 백트래킹 알고리즘을 사용하여 퀸을 놓을 수 있는 모든 경우의 수를 구합니다. def is_available(candidate, current_col): current_row = len(candidate) for queen_row in range(current_row): if candidate[queen_row] == .. 공감수 0 댓글수 0 2023. 3. 14.
[알고리즘이론] 분할정복(Divide and Conquer) 파이썬으로 구현하기 분할정복(Divide and Conquer) 알고리즘은 큰 문제를 작은 문제로 분할한 후, 각 작은 문제를 해결하고, 이를 합쳐서 큰 문제를 해결하는 알고리즘입니다. 파이썬에서는 다음과 같이 분할정복 알고리즘을 구현할 수 있습니다. 예제: 이진 탐색 주어진 정렬된 리스트에서 특정한 값의 위치를 찾는 문제입니다. 이진 탐색은 리스트의 중간 위치의 값을 검사하여 찾고자 하는 값이 리스트의 중간 위치보다 큰지 작은지를 비교하여 검색 범위를 절반으로 줄여가면서 값을 찾아갑니다. def binary_search(lst, x): start = 0 end = len(lst) - 1 while start x: end = mid - 1 else: start = mid + 1 return -1 # 정렬된 리스트에서 5의 .. 공감수 0 댓글수 0 2023. 3. 14.
[알고리즘이론] 그리디(Greedy) 파이썬으로 구현하기 그리디(Greedy) 알고리즘은 현재 상황에서 가장 좋은 선택을 하는 것을 반복하여 최적해를 구하는 알고리즘 기법입니다. 파이썬에서는 다음과 같이 그리디 알고리즘을 구현할 수 있습니다. 예제1: 동전 거스름돈 문제 n원의 동전을 거슬러 주어야 할 때, 거슬러 줄 동전의 개수가 최소가 되도록 하려면 어떻게 거슬러 줘야 할까요? 예를 들어, 1260원을 거슬러 주어야 할 때, 500원, 100원, 50원, 10원 동전이 각각 몇 개씩 필요한지 구하는 문제입니다. def change(n): coins = [500, 100, 50, 10] # 동전 종류 count = 0 # 거슬러 준 동전 개수 for coin in coins: count += n // coin # 동전 개수 누적 n %= coin # 거슬러 .. 공감수 0 댓글수 0 2023. 3. 11.
[알고리즘이론] 완전탐색(Brute-force) 파이썬으로 구현하기 완전탐색(Brute-force)은 가능한 모든 경우를 검사하여 답을 찾는 알고리즘 기법입니다. 파이썬에서는 다음과 같이 완전탐색을 구현할 수 있습니다. 예제1: 주어진 리스트에서 최대값 찾기 def find_max(lst): max_value = lst[0] for i in range(1, len(lst)): if lst[i] > max_value: max_value = lst[i] return max_value # 주어진 리스트에서 최대값 찾기 lst = [3, 1, 5, 2, 4] print(find_max(lst)) 위 코드에서 find_max() 함수는 주어진 리스트에서 최대값을 찾아 리턴합니다. max_value 변수에 리스트의 첫번째 값을 할당하고, 반복문을 통해 리스트의 각 요소를 검사하면서.. 공감수 0 댓글수 0 2023. 3. 11.
[알고리즘이론] DP(Dynamic Programming : 동적 프로그래밍) 파이썬으로 구현하기 DP(Dynamic Programming)는 이전에 계산한 값을 저장해 놓고 재활용하여 중복 계산을 줄이는 알고리즘 기법입니다. 파이썬에서는 DP를 구현하는 방법은 여러가지가 있습니다. 여기서는 Memoization 방식과 Bottom-up 방식을 예제 코드로 설명하겠습니다. Memoization 방식 Memoization은 이전에 계산한 값을 저장하고 재활용하는 방식입니다. 이전에 계산한 값이 필요할 때마다 값을 조회하여 사용합니다. Memoization 방식은 보통 재귀 함수와 함께 사용됩니다. 아래는 Memoization 방식을 사용하여 피보나치 수열을 구하는 예제 코드입니다. # Memoization 방식으로 구현한 피보나치 수열 예제 memo = [0] * 100 # 메모이제이션을 위한 리스트 .. 공감수 0 댓글수 0 2023. 3. 10.
[알고리즘이론] 파이썬 자료구조 파이썬에서는 다양한 자료구조를 제공합니다. 각 자료구조의 특징과 사용 방법을 살펴보겠습니다. 리스트(List) 리스트는 순서가 있는 데이터의 집합으로, 대괄호([])로 표현합니다. 원소들은 쉼표로 구분합니다. 리스트는 수정이 가능하며, 인덱싱과 슬라이싱을 통해 데이터를 접근할 수 있습니다. 예시: a = [1, 2, 3, 4, 5] # 리스트 생성 print(a) # [1, 2, 3, 4, 5] print(a[0]) # 1 print(a[2:4]) # [3, 4] a[1] = 10 # 리스트 값 수정 print(a) # [1, 10, 3, 4, 5] 튜플(Tuple) 튜플은 리스트와 유사하지만, 수정이 불가능합니다. 소괄호(())로 표현합니다. 예시: a = (1, 2, 3) # 튜플 생성 print(a.. 공감수 0 댓글수 0 2023. 3. 10.
[알고리즘이론] 파이썬으로 BFS 구현 BFS(Breadth-First Search)는 큐(Queue)를 이용하여 구현할 수 있습니다. 큐는 선입선출(FIFO) 구조이므로, BFS에서는 현재 노드와 인접한 노드 중 방문하지 않은 노드가 있으면 해당 노드를 큐에 삽입하고 방문 처리합니다. 그리고 큐에서 꺼낸 노드를 다시 시작점으로 하여 인접한 노드 중 방문하지 않은 노드가 있으면 큐에 삽입하고 방문 처리합니다. 이 과정을 큐가 빌 때까지 반복하면 됩니다. 아래는 큐를 사용하여 BFS를 구현한 예제 코드입니다. # 큐를 사용한 BFS 구현 예제 from collections import deque def bfs(start, adj_list): visited = [False] * len(adj_list) # 각 노드의 방문 여부를 저장할 리스트 q.. 공감수 0 댓글수 0 2023. 3. 7.
[알고리즘이론] 파이썬으로 DFS 구현 1. 재귀함수 DFS(깊이 우선 탐색)를 파이썬으로 구현하려면, 일반적으로 재귀 함수를 사용하여 구현할 수 있습니다. 아래는 간단한 예제 코드입니다. # 인접 리스트를 사용한 DFS 구현 예제 def dfs(v, visited, adj_list): visited[v] = True # 현재 노드를 방문 처리 print(v, end=' ') # 현재 노드 출력 for i in adj_list[v]: # 현재 노드와 인접한 노드 중 if not visited[i]: # 방문하지 않은 노드가 있다면 dfs(i, visited, adj_list) # 해당 노드를 방문 # 예제 그래프 adj_list = { 1: [2, 3, 4], 2: [1, 4, 5], 3: [1, 6, 7], 4: [1, 2, 5], 5: [.. 공감수 0 댓글수 0 2023. 3. 7.
[Python]알고리즘 기본 유형 - 유효한 팰린드롬 팰린드롬(회문)이란 앞뒤가 똑같은 문장으로 , 뒤집어도 같은 말이 되는 단어 또는 문장을 팰린드롬(Palindrome)이라고 한다. 우리말로는 '회문'이라 부르며, 문장 중에서는 대표적으로 '소주 만 병만 주소'를 예로 들 수 있다. 기본적인 palindrome 유형의 문제는 어떻게 해결하는지 다음의 예제를 통해 알아보자. 주어진 문자열이 팰린드롬인지 확인하여 맞다면 True, 아니라면 False를 출력하라. 단 대소문자를 구분하지 않으며, 영문자와 숫자만을 대상으로 한다. // 입력 1 : "A man, a plan, a canal: Panama" // 입력 2 : "race a car" 풀이 1 : 리스트로 변환 여기서는 직접 문자열을 입력받아 팰린드롬 여부를 판별해 본다.. 공감수 0 댓글수 0 2022. 12. 9.

728x90

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.