잡식성 개발자

그리디(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 # 거슬러 ..

완전탐색(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 변수에 리스트의 첫번째 값을 할당하고, 반복문을 통해 리스트의 각 요소를 검사하면서..

DP(Dynamic Programming)는 이전에 계산한 값을 저장해 놓고 재활용하여 중복 계산을 줄이는 알고리즘 기법입니다. 파이썬에서는 DP를 구현하는 방법은 여러가지가 있습니다. 여기서는 Memoization 방식과 Bottom-up 방식을 예제 코드로 설명하겠습니다. Memoization 방식 Memoization은 이전에 계산한 값을 저장하고 재활용하는 방식입니다. 이전에 계산한 값이 필요할 때마다 값을 조회하여 사용합니다. Memoization 방식은 보통 재귀 함수와 함께 사용됩니다. 아래는 Memoization 방식을 사용하여 피보나치 수열을 구하는 예제 코드입니다. # Memoization 방식으로 구현한 피보나치 수열 예제 memo = [0] * 100 # 메모이제이션을 위한 리스트 ..

파이썬에서는 다양한 자료구조를 제공합니다. 각 자료구조의 특징과 사용 방법을 살펴보겠습니다. 리스트(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..

BFS(Breadth-First Search)는 큐(Queue)를 이용하여 구현할 수 있습니다. 큐는 선입선출(FIFO) 구조이므로, BFS에서는 현재 노드와 인접한 노드 중 방문하지 않은 노드가 있으면 해당 노드를 큐에 삽입하고 방문 처리합니다. 그리고 큐에서 꺼낸 노드를 다시 시작점으로 하여 인접한 노드 중 방문하지 않은 노드가 있으면 큐에 삽입하고 방문 처리합니다. 이 과정을 큐가 빌 때까지 반복하면 됩니다. 아래는 큐를 사용하여 BFS를 구현한 예제 코드입니다. # 큐를 사용한 BFS 구현 예제 from collections import deque def bfs(start, adj_list): visited = [False] * len(adj_list) # 각 노드의 방문 여부를 저장할 리스트 q..

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: [..

팰린드롬(회문)이란 앞뒤가 똑같은 문장으로 , 뒤집어도 같은 말이 되는 단어 또는 문장을 팰린드롬(Palindrome)이라고 한다. 우리말로는 '회문'이라 부르며, 문장 중에서는 대표적으로 '소주 만 병만 주소'를 예로 들 수 있다. 기본적인 palindrome 유형의 문제는 어떻게 해결하는지 다음의 예제를 통해 알아보자. 주어진 문자열이 팰린드롬인지 확인하여 맞다면 True, 아니라면 False를 출력하라. 단 대소문자를 구분하지 않으며, 영문자와 숫자만을 대상으로 한다. // 입력 1 : "A man, a plan, a canal: Panama" // 입력 2 : "race a car" 풀이 1 : 리스트로 변환 여기서는 직접 문자열을 입력받아 팰린드롬 여부를 판별해 본다..