Algorithms 💻/Basic

[알고리즘] 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..

[알고리즘] 수학 관련 알고리즘 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. 유클리드 호제법 최대공약수, 최소공배수 구하기 유클리드 호제법은 최대공약수를 구하는 알..

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

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

[알고리즘] 특정 기준으로 리스트 정렬하기 (python) - key=lambda

요즘 정렬 문제를 많이 풀다보면, 리스트를 특정 기준으로 정렬해야할 때가 많다. 단순히 .sort(), sorted()로의 오름차순 내림차순으로는 풀 수 없는 문제도 많이 만났고, 이럴때는 key=lambda 함수를 사용하면 된다! 오늘은 이러한 용법에 대해 포스팅 해보도록 하겠다. :) 이 게시글은 여기를 참고하였다. # key=lambda 용법 우선 key=lambda 용법은 sorted 함수의 인자로 쓰인다. 그리고 다음과 같이 사용한다. # key가 하나일 때 모든 정렬의 기반은 오름차순 정렬이다. ex 1) 리스트의 각 원소를 기준으로 정렬하기 (일반 오름차순) 참고로 문자열을 다음과 같이 정렬하면 사전순으로 정렬이 된다. arr = ['abc', 'bac', 'bca'] sorted(arr, ..

[코테] 자주 쓰이는 Python 기본 함수 정리 (계속 업데이트)

블로그 주인이 계속 공부하면서 업데이트 될 예정입니다. 구현 등의 코딩테스트 문제 유형에 기출되었던 기본적인 내장 Python 함수 모음입니다! 자세한 내용은 제 github repo를 참고해주세요 :D 개인 기록용이긴 합니다ㅎㅎ.. GitHub - daeunni/For_codingtest: 다은이의 알고리즘 아카이브 📝🔥 다은이의 알고리즘 아카이브 📝🔥. Contribute to daeunni/For_codingtest development by creating an account on GitHub. github.com ord( ) / chr( ) ord()는 문자열을 아스키코드(숫자)로 반환하는 함수이고, chr()은 아스키코드를 문자열로 반환하는 함수! chr(65) >>> A ord('a') >>..

[알고리즘] 큐를 이용해 BFS 구현하기 (python)

오늘은 BFS 구현에서 주로 사용하는 큐에 대해 포스팅하고, 관련 적용 사례를 복습해보려고 한다. 사실 BFS/DFS 문제를 풀다보면 나는 DFS에 훨씬 더 익숙해서, DFS로 주로 풀이를 한다. 그 이유가 BFS 구현에서 큐에서 막히기 때문이라고 생각했고, 관련 포스팅을 하게된 것이다! # 큐(Queue) 우선 큐는 쉽게 말해서 다음과 같은 선입선출 구조이다. 먼저 들어온 요소가 먼저 나가는, 그런 것이다. BFS(너비우선탐색) 구현에는 큐를 이용하는 것이 정석인데, 그 이유는 BFS는 인접한 노드부터 차례로 넓게 탐색하는 알고리즘이기 때문이다. (BFS에 대해서는 따로 설명하지 않겠다) Python에는 친절하게도 deque 라이브러리가 존재해서, 큐 자료구조를 이용하고 싶을 때는 관련 라이브러리를 다..

[자료구조] - (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 ..