Python/알고리즘 개념 (13) 썸네일형 리스트형 [Python] 재귀함수와 스택, 지역변수와 전역변수 이번 포스팅에서는 Python의 재귀함수가 스택을 활용한다는 점과 Python에서의 지역변수, 전역변수를 살펴보려고 한다. 이번 내용은 생각보다 기초적인 개념이지만 알고리즘 공부를 하면서 몰랐던 내용 중심으로 포스팅하려고 한다. 1. 재귀함수는 스택을 활용한다! 재귀함수는 스택을 활용한다는 것을 알고리즘 공부하면서 솔직히 처음 알았다. DFS 관련 문제를 풀기 시작했는데, 재귀함수가 아직도 와닿지 않았었는데, 스택을 활용한다는 것을 듣고 '아!' 소리가 절로 나왔다. 이런 기초적인 내용을 이제야 알았다는 것에 아쉽긴 하지만 지금이라도 안 게 어딘가! 먼저 스택이란 자료구조는 처음 들어간 데이터가 가장 나중에 나오는 FILO(Frist In Last Out) 방식을 취하는 자료구조이다. 아래처럼 말이다. .. [Python] 가장 긴 증가하는 부분 수열 길이를 찾는 LIS 알고리즘 🔊 이번 포스팅에는 최근에 Python으로 알고리즘을 공부하기 시작하면서 알게 된 여러 알고리즘의 원리와 Python으로 구현하는 방법에 대해 소개해보려 한다. 필자는 최근 알고리즘 공부를 '나동빈'님의 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 이라는 책과 백준 온라인 저지 사이트로 하고 있다. 이 중 '나동빈'님이 저자이신 책에서 가르쳐주는 내용을 기반으로 배운 내용을 정리해보려 한다. 이번 포스팅에서는 가장 긴 증가하는 부분 수열 길이를 찾는 LIS(Longest Increasing Subsequence) 알고리즘 동작 과정을 이해해보고 Python으로 구현하는 방법에 대해 알아보자. 1. 가장 긴 증가하는 부분 수열 가장 긴 증가하는 부분 수열이란 무엇일까? 단어로만 이해하기에는 잘 와.. [Python] 알아두면 좋을 기타 알고리즘 🔊 이번 포스팅에는 최근에 Python으로 알고리즘을 공부하기 시작하면서 알게 된 여러 알고리즘의 원리와 Python으로 구현하는 방법에 대해 소개해보려 한다. 필자는 최근 알고리즘 공부를 '나동빈'님의 '이것이 취업을 위한 코딩 테스트다 with 파이썬'이라는 책과 백준 온라인 저지 사이트로 하고 있다. 이 중 '나동빈'님이 저자이신 책에서 가르쳐주는 내용을 기반으로 배운 내용을 정리해보려 한다. 이번 포스팅에서는 책 속 이론의 마지막 부분인 평소에 알아두면 코딩 테스트나 기타 상황에 잘 사용할 수 있는 기타 알고리즘들에 대해 소개하려고 한다. 소개할 알고리즘 종류들은 소수의 판별, 에라토스테네스의 체, 투 포인터, 구간 합 계산, 순열과 조합으로 총 5가지 알고리즘들에 대해 소개한다. 1. 소수의 .. [Python] 노드 간의 선후 관계를 고려하는 위상(Topology) 정렬 알고리즘 🔊 이번 포스팅에는 최근에 Python으로 알고리즘을 공부하기 시작하면서 알게 된 여러 알고리즘의 원리와 Python으로 구현하는 방법에 대해 소개해보려 한다. 필자는 최근 알고리즘 공부를 '나동빈'님의 '이것이 취업을 위한 코딩 테스트다 with 파이썬'이라는 책과 백준 온라인 저지 사이트로 하고 있다. 이 중 '나동빈'님이 저자이신 책에서 가르쳐주는 내용을 기반으로 배운 내용을 정리해보려 한다. 이번 포스팅에서는 노드들 간의 선후 관계를 고려하여 정렬을 수행하는 정렬 알고리즘 중 하나인 위상(Topology) 정렬에 대해 알아본다. 그리고 이를 구현한 Python 소스코드도 살펴보자. 1. 진입차수 위상 정렬은 정렬 알고리즘이기도 하지만 노드들 간의 선후 관계를 고려한다는 측면에서 그래프 데이터가 주.. [Python] 최소 신장 트리를 찾는 크루스칼(Kruskal) 알고리즘 🔊 이번 포스팅에는 최근에 Python으로 알고리즘을 공부하기 시작하면서 알게 된 여러 알고리즘의 원리와 Python으로 구현하는 방법에 대해 소개해보려 한다. 필자는 최근 알고리즘 공부를 '나동빈'님의 '이것이 취업을 위한 코딩 테스트다 with 파이썬'이라는 책과 백준 온라인 저지 사이트로 하고 있다. 이 중 '나동빈'님이 저자이신 책에서 가르쳐주는 내용을 기반으로 배운 내용을 정리해보려 한다. 이번 포스팅에서는 최소 신장 트리를 찾는 데 사용되는 알고리즘 중 하나인 크루스칼(Kruskal) 알고리즘에 대해 알아보려고 한다. 해당 알고리즘을 이해하기 위해서는 신장 트리라는 개념이 선행되어야 하므로 신장 트리에 대한 개념을 먼저 소개한 뒤 크루스칼 알고리즘에 대해 알아보고 Python으로 구현하는 소스.. [Python] 그래프 알고리즘 - 서로소 집합 자료구조 🔊 이번 포스팅에는 최근에 Python으로 알고리즘을 공부하기 시작하면서 알게 된 여러 알고리즘의 원리와 Python으로 구현하는 방법에 대해 소개해보려 한다. 필자는 최근 알고리즘 공부를 '나동빈'님의 '이것이 취업을 위한 코딩 테스트다 with 파이썬'이라는 책과 백준 온라인 저지 사이트로 하고 있다. 이 중 '나동빈'님이 저자이신 책에서 가르쳐주는 내용을 기반으로 배운 내용을 정리해보려 한다. 이번 포스팅에서는 그래프 알고리즘 종류 중 하나라고 할 수 있는 서로소 집합 자료구조를 활용한 알고리즘에 대해 알아보려고 한다. 책에서 소개하는 그래프 알고리즘 종류로는 그리디 알고리즘이라고도 할 수 있는 크루스칼 알고리즘과 스택과 큐를 활용해야 하는 위상 정렬 알고리즘이 있다. 이러한 알고리즘을 배우기에 앞.. [Python] 모든 지점에서의 최단경로를 찾는 플로이드 워셜(Floyd-Warshall) 알고리즘 🔊 이번 포스팅에는 최근에 Python으로 알고리즘을 공부하기 시작하면서 알게 된 여러 알고리즘의 원리와 Python으로 구현하는 방법에 대해 소개해보려 한다. 필자는 최근 알고리즘 공부를 '나동빈'님의 '이것이 취업을 위한 코딩 테스트다 with 파이썬'이라는 책과 백준 온라인 저지 사이트로 하고 있다. 이 중 '나동빈'님이 저자이신 책에서 가르쳐주는 내용을 기반으로 배운 내용을 정리해보려 한다. 이번 포스팅에서는 또 다른 최단 경로 알고리즘인 플로이드 워셜 알고리즘에 대해 알아보려고 한다. 저번 포스팅에서 배운 다익스트라(Dijkstra) 알고리즘은 특정 노드라는 시작 노드 1개를 지정하고 그 시작 노드에서 다른 노드들 까지의 최단거리를 구하는 방법이었다. 하지만 플로이드 워셜 알고리즘은 시작 노드를.. [Python] 우선순위 큐를 활용한 개선된 다익스트라(Dijkstra) 알고리즘 🔊 이번 포스팅에는 최근에 Python으로 알고리즘을 공부하기 시작하면서 알게 된 여러 알고리즘의 원리와 Python으로 구현하는 방법에 대해 소개해보려 한다. 필자는 최근 알고리즘 공부를 '나동빈'님의 '이것이 취업을 위한 코딩 테스트다 with 파이썬'이라는 책과 백준 온라인 저지 사이트로 하고 있다. 이 중 '나동빈'님이 저자이신 책에서 가르쳐주는 내용을 기반으로 배운 내용을 정리해보려 한다. 이번 포스팅에서는 저번 시간에 배웠던 다익스트라 알고리즘의 간단한 구현 방법에 이어 이를 개선한 우선순위 큐 즉, heapq를 활용한 개선된 다익스트라 알고리즘에 대해 알아보려고 한다. 다익스트라의 구현 개념에 대해서는 거의 유사하므로 해당 포스팅에서는 우선순위 큐를 어떤 부분에 활용하고 Python으로 구현.. [Python] 최단경로를 위한 다익스트라(Dijkstra) 알고리즘 🔊 이번 포스팅에는 최근에 Python으로 알고리즘을 공부하기 시작하면서 알게 된 여러 알고리즘의 원리와 Python으로 구현하는 방법에 대해 소개해보려 한다. 필자는 최근 알고리즘 공부를 '나동빈'님의' '이것이 취업을 위한 코딩 테스트다 with 파이썬'이라는 책과 백준 온라인 저지 사이트로 하고 있다. 이 중 '나동빈'님이 저자이신 책에서 가르쳐주는 내용을 기반으로 배운 내용을 정리해보려 한다. 이번 포스팅에서는 최단 경로를 찾는 데 자주 사용되는 다익스트라(Dijkstra) 알고리즘 개념에 대해 알아보고 Python으로 구현하는 방법에 대해 알아보려고 한다. 다익스트라 알고리즘은 최단 경로 알고리즘 종류 중 하나이다. 말 그대로 특정 지점에서 다른 특정 지점까지의 최단 경로를 구한다거나 모든 지점.. [Python] 알고리즘을 위한 주요 라이브러리와 유의점 이번 포스팅에서는 Python으로 알고리즘 문제를 해결할 때 주로 사용하는 라이브러리와 유의점에 대해 알아보려고 한다. 해당 라이브러리들을 적절히 사용하면 손쉽게 문제를 해결할 때가 종종 있다고 한다. 해당 포스팅에서 소개하는 주요 라이브러리들 이외에는 여기를 참고해서 확인해보자. 이외의 라이브러리들도 사용해서 문제를 해결하는 경우도 자주 있다고 하니 해당 링크를 참고해서 찾아 사용하는 습관을 기르는 것을 권장한다. 1. 내장함수 내장함수란, print 문이나 input 문 같은 기본 입출력 기능부터 sorted 같은 정렬 기능을 포함하는 기본 내장 라이브러리다. 1-1. sum sum 함수는 iterable한 객체(리스트, 딕셔너리, 튜플, 집합자료)가 입력으로 주어졌을 때, 모든 원소의 합을 반환한다.. [Python] Dynamic Programming(동적계획법) 알고리즘 🔊 이번 포스팅에는 최근에 Python으로 알고리즘을 공부하기 시작하면서 알게 된 여러 알고리즘의 원리와 Python으로 구현하는 방법에 대해 소개해보려 한다. 필자는 최근 알고리즘 공부를 '나동빈'님의'이것이 취업을 위한 코딩 테스트다 with 파이썬'이라는 책과 백준 온라인 저지 사이트로 하고 있다. 이 중 '나동빈'님이 저자이신 책에서 가르쳐주는 내용을 기반으로 배운 내용을 정리해보려 한다. 이번 포스팅에서는 "한 번 계산한 문제는 다시 계산하지 않도록 한다!" 는 다이나믹 프로그래밍(Dynamic Programming, 동적 계획법이라고도 함)에 대해서 소개해보고 이를 Python으로 구현하는 방법에 대해 알아보자. 다이나믹 프로그래밍은 메모리 공간을 약간 더 사용해서 연산 속도를 비약적으로 증가.. [Python] 순차(Sequential) 탐색과 이진(Binary) 탐색 알고리즘 🔊 이번 포스팅에는 최근에 Python으로 알고리즘을 공부하기 시작하면서 알게 된 여러 알고리즘의 원리와 Python으로 구현하는 방법에 대해 소개해보려 한다. 필자는 최근 알고리즘 공부를 '나동빈'님의'이것이 취업을 위한 코딩 테스트다 with 파이썬'이라는 책과 백준 온라인 저지 사이트로 하고 있다. 이 중 '나동빈'님이 저자이신 책에서 가르쳐주는 내용을 기반으로 배운 내용을 정리해보려 한다. 이번 포스팅에서는 저번에 알아보았던 '탐색' 알고리즘의 또 다른 종류인 순차 탐색(Sequential Search)과 이진 탐색(Binary Search) 알고리즘에 대해 알아보고 Python으로 구현하는 방법에 대해 알아보려고 한다. 1. 순차 탐색(Sequential Search) 순차 탐색은 리스트 또는 .. [Python] DFS/BFS 탐색 알고리즘과 다양한 정렬 알고리즘 🔊 이번 포스팅에는 최근에 Python으로 알고리즘을 공부하기 시작하면서 알게 된 여러 알고리즘의 원리와 Python으로 구현하는 방법에 대해 소개해보려 한다. 필자는 최근 알고리즘 공부를 '나동빈'님의 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 이라는 책과 백준 온라인 저지 사이트로 하고 있다. 이 중 '나동빈'님이 저자이신 책에서 가르쳐주는 내용을 기반으로 배운 내용을 정리해보려 한다. 알고리즘 종류가 다양하지만 이번에 배운 개념들은 탐색 알고리즘의 대표적 방법들인 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색), 그리고 정렬 알고리즘의 종류들인 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬에 대해 알아보자. 또 각 챕터마다 하단에는 Python으로 알고리즘을 구현해 보기도 하자. 탐색.. 이전 1 다음
