알고리즘

[알고리즘] Kadane’s(카데인) Algorithm - Array에서 부분합의 최대 찾기

요즘 매일 leetcode daily 문제를 풀고 있다. 생각보다 동기부여가 잘 되어서 너무 좋다! 오늘은 Dynamic Programming 알고리즘의 일종인 Kadane’s(카데인) Algorithm에 대해 포스팅해보고자 한다. Dynamic programming은 문제를 sub problems로 나누어, sub problem을 그 다음 step의 답을 구하는데에 계속해서 저장해놓고 이용하는 개념이다. # Kadane's Algorithm? 일단 이 알고리즘은 숫자 Array가 주어졌을 때, 이 array 내 연속된 subset 원소들의 합 중 가장 max인 값을 반환하는 알고리즘이다. 문제를 예로 들면 이렇다. 주어진 배열 A를 [1,-2,3,5,-4,2,5] 라고 했을 때 Maximum Subar..

[백준] 치킨배달(Python) - 구현 & 백트래킹

# 문제 문제가 언뜻 보면 복잡해보이지만, 사실 M개의 치킨집을 선택하는 최적의 입지를 구하는 문제다. 여기서 최적의 입지의 기준이란 각 집으로부터 "치킨거리"의 합이 가장 작아지는 M개의 치킨집을 고르는 경우를 구하는 것 ! "치킨거리"를 구하는 공식 또한 인덱스를 기준으로 하기에 그렇게 어렵지 않다. # 입출력 # Idea # Code 우선 이 문제는 구현과 백트래킹으로 풀 수 있으므로, 구현으로 푸는 방법을 먼저 소개하겠다. itertools의 combination 함수를 이용하면 쉽게 구현 가능하다. """ 치킨 배달 - Combination으로 먼저 풀기 """ from itertools import combinations # 해당 치킨집 조합과 1들의 거리를 리턴하는 함수 def distanc..

[알고리즘] 수학 관련 알고리즘 Code - 에라토스테네스의 체, 유클리드 호제법

기초적인 수학적 알고리즘의 코드를 모아놓은 간단한 포스팅이다! 소수를 구하는 알고리즘과 최대공약수를 구하는 알고리즘! 1. 에라토스테네스의 체 소수를 구하는 알고리즘 특정 배수를 지워가는 식으로 전개된다. def era(n): """ Input : 몇까지 탐색할지 Output : n까지 숫자 중 소수를 포함한 리스트 """ a = [False, False] + [True] * (n-1) primes = [] for i in range(2, n+1): if a[i]: primes.append(i) for j in range(2*i, n+1, i): a[j] = False # 배수를 지운다! return primes 2. 유클리드 호제법 최대공약수, 최소공배수 구하기 유클리드 호제법은 최대공약수를 구하는 알..

[백준] N-Queens 문제(Python) - 백트래킹

# 문제 즉, 상하좌우 대각선으로 이동하는 N개의 퀸을 서로 부딪히지 않도록 배열하는 방법 수를 리턴하는 문제이다. 백트래킹의 전형적인 문제 유형이라고 한다. 아래의 예시처럼 말을 놓는 경우의 수는 하나의 경우의 수가 될 것이다. # 입출력 # Idea 우선 해당 문제는 백트래킹 문제로, DFS 방법으로 문제를 푸는 방법을 고안할 수 있다. (백트래킹에 대해 궁금하신 분들은 여기를 참고!) 특히 이 문제를 처음 봤을 때, 나는 다음과 같이 DFS노드를 뻗으면 어떨지 생각을 했다. 각 raw별 좌표를 노드로 놓고, Depth는 raw 단위가 되도록 노드를 뻗는 것이다. 특히 백트래킹은 유망한 노드(정답이 될 가능성이 있는 노드)이면 계속 DFS 탐색을 하고, 그렇지 않으면 탐색을 멈추고 위 depth의 노..

[백준] 로또(Python) - 백트래킹 & 1차원 dfs 탐색

# 문제 단순히 combination을 구하는 것 같은 아주 간단한 문제이지만, 사실 dfs로 풀어야 진가를 볼 수 있는 문제이기도 했다! # 입출력 K가 집합 S에 포함되는 수의 개수인데 생각보다 6에서 13 사이이면 작은 범위라고 생각했다. 그래서 처음으로 itertools 모듈을 고려하게 된 것 같다. # Idea 처음에는 앞서 언급한대로 from itertools import combinations 을 사용했다. 범위가 작게 주어졌다고 생각했기 때문이다. 이런 방식으로 구한 답도 맞았지만, 이 문제는 백트래킹 단원의 문제인 만큼 dfs로 접근하는 것이 중요한 문제였던 것 같다. 사실 이제 dfs는 좀 익숙한 상태였는데, 모두 2차원 그래프를 대상으로 한 dfs 문제를 풀이했었다. 그래서 이 문제는..

[알고리즘] 백트래킹(Backtracking)을 알아보자

요즘 백준 문제집을 풀고있는데, 백트래킹 개념의 문제가 나와서 한번 개념을 블로그에 정리해보려고 한다. # 등장 배경 이 글을 읽고있는 분들이라면 DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 등의 유명한 완전탐색 알고리즘은 한번쯤 들어본 적이 있을 것이다. 이러한 알고리즘은 모든 가능한 경우의 수를 탐색하는 특징이 있는데, 백트래킹도 이와 비슷한 motivation을 공유한다. 즉, '가능한 모든 방법'을 탐색하는 데에 관심사가 있는 것 ! 하지만 DFS와 BFS는 정말 모든 노드를 탐색한다. 그러다보면 해답이 될 가능성이 없는 그래프의 노드까지 "모두" 탐색하게 되는 것이다. 우리는 알고리즘 문제를 풀고있으므로, 전혀 가능성이 없는 노드는 관심이 없을 것이다. 따라서 백트래킹(Backtracki..

[자료구조] - (2) 스택(Stacks) with Python

스택(Stacks) 역시 추상적 선형 자료 구조 중 하나이다. 본 게시글은 Python 코드로 작성되었습니다. 1. 스택의 구조 기본적으로 스택은 넣을 때는 한쪽 끝에서 밀어넣어야 하고(push), 꺼낼 때에는 같은 쪽에서 뽑아 꺼내야한다.(pop) 간단히 그림으로 나타내면 다음과 같다. 이와 비슷한 선형 자료구조 큐(Queue)는 좀 다르다. 큐는 '선입선출'의 구조로서, 먼저 들어간 요소가 가장 먼저 나오는 구조이다. 기본적으로 스택은 한쪽에서 꺼내고 빼고를 하는 반면, 큐는 한쪽에서 들어가면 다른쪽에서 나온다! 그리고 스택은 가장 마지막에 들어간 요소가 가장 먼저 나온다 (후입선출) 스택에는 정해진 저장 공간이 있다. 따라서 비어있는 스택에서 원소를 꺼내려 하거나, 꽉찬 스택에 데이터 원소를 넣으려..

[자료구조] (1) - 연결리스트(Linked List) with Python

연결리스트는 대표적인 추상적 자료구조(Abstract Data Structures) 중 하나이다. 본 게시글은 Python 코드로 작성되었습니다. 1. 단순 연결리스트의 기본 구조 각 연결리스트는 Node로 구성되어있고, Node안에는 data와 link로 구성되어있다. 안에 들어있는 data는 그림에 나와있는 정수형 말고도 문자, 레코드 등 여러 구조가 가능하다. Node를 코드로 구성해보면 다음과 같다! class Node: def __init__(self, item): self.data = item # data self.next = None # next link (다음 인자를 가리킴) 여기서 next는 다음 노드에 접근하는 방법이다. 예시 ) L.head == a a.next == b b.next ..