supergravity

목차 -시작 -문제 1: 백준 - 1, 2, 3 더하기 -문제 2: 백준 - 정수 삼각형 -문제 3: 백준 - 스티커 -문제 4: 백준 - 평범한 배낭 -문제 5: 최장 공통부분 문자열

목차 -시작 -플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) -다익스트라 알고리즘(Dijkstra algorithm) -벨먼-포드 알고리즘(Bellman-Ford algorithm) -문제 시작 최단 경로 알고리즘은 graph가 주어 질 때 최단 경로를 찾는 방법입니다. graph는 node와 edge로 구성된 집합입니다. 만약 위의 문장이 생소하다면 여기를 클릭해 주세요. 클릭 이전에 배운 BFS 또한 최단 거리 알고리즘이라 할 수 있습니다. BFS는 weight가 없는(edge의 거리가 모두 1인) graph가 주어질 때 시작 node에서 모든 노드로 가는 최단 거리를 구하는 알고리즘이었습니다. BFS가 크리스털 클리어하지 않다면 여기를 클릭해 주세요. 클릭 최단 경로 알고리즘..

목차 -시작 -이진 탐색 알고리즘 -이진 탐색 감잡기 -tree 자료구조와 이진 탐색 -시간복잡도 -구현 -bisect 라이브러리 -정리 시작 binary search algorithm에 대해서 알아봅시다. binary search algorithm은 한국어로 이진 탐색 알고리즘이라고 불리고 있습니다. 이번 글에서 이진 탐색 알고리즘이라고 부르겠습니다. 이진 탐색은 탐색 방법의 한 종류입니다. 이진 탐색은 정렬된 리스트가 있을 때 target과 같은 값이 리스트에 있는지 찾는 탐색 방법입니다. 이진 탐색은 이름을 보면 어떤 알고리즘 인지 대략적으로 이해할 수 있습니다. 이름의 이진은 두 부분으로 라는 뜻을 가지고 있습니다. 그래서 이진 탐색은 "두 부분으로 나누어 찾는 방법이다"라고 이해할 수 있습니다...

목차 -graph? 어떻게 학습해야 하나 -directed graph, undirected graph -neighbor -graph 구현 -graph에 사용되는 기본적인 알고리즘 2개(bfs, dfs) -문제 graph? 어떻게 학습해야 하나 그래프가 뭘까요? 그래프는 아래의 그림과 같이 원안에 데이터를 포함하는 노드와. 노드들을 연결하는 엣지로 구성됩니다. 노드와 엣지로 구성된 그래프는 현실 문제를 표현하고 해결하기 참 좋습니다. 그래서 코딩테스트에서는 현실 상활을 응용한 문제들이 출제되고 있습니다. 현실 문제를 그래프로 표현하는 방법은 node를 현실에 존재하는 객체로 표현하고, 엣지를 객체들의 관계로 표현하면 됩니다. 예를 들어 도시의 교통문제를 해결하기 위해 도시와 이들의 관계를 graph로 표현..

목차 -시작 -기본 -lambda 함수 -거꾸로 정렬 -2중 정렬, 다중 정렬 -문제 시작 파이썬 내장함수인 sorted를 잘 활용하면. 정렬관련 문제는 거뜬히 해결할 수 있습니다. sorted는 여러개의 조건을 충족시키는 정렬을 진행할 수 있는데. 이 기능은 간결한 코드로 문제를 해결할 수 있는 실마리를 제공합니다. 그러면 시작해 봅시다. 기본 sorted()는 리스트와 같은 반복가능한 객체를 파라매터로 받고. 이를 정렬된 리스트로 리턴합니다. sorted()는 파라매터로 반복가능한 객체 iterable을 받기때문에. dictionary, set, tuble, string, generator 모두 사용이 가능합니다. a = [1,3,1,2,3,4,56,6,2,8,3,7,6 ] print(sorted(a..

목차 -재귀함수? -간단한 재귀함수 동작 -피보나치 재귀함수 동작 -정리 재귀함수 재귀함수는 함수 안에 함수를 호출하는 함수를 말합니다. 예를 들면. 아래와 같은 코드가 재귀함수입니다. def go_to_zero(n): if n == 0: return 0 print(n) return go_to_zero(n-1) 재귀함수는 자기 자신을 호출하기 때문에 실수하면. 무한히 자기 자신을 호출하게 됩니다. 그래서 탈출 조건이 필수입니다. 위의 코드의 경우 함수의 파라매터가 호출될 때마다 1식 감소하고. 만약 0이 되면 탈출하는 조건을 포함하고 있습니다. 그러면 이 함수가 잘 동작하는지 확인해 봅시다. 인풋을 10을 넣으면 -1씩 감소하면서 함수를 호출하다. 0이 되면 빠져나오는 것을 확인할 수 있습니다. 간단한 ..

목차 -시작 -permutaions -combinations -문제 시작 파이썬 itertools를 이용하면. 쉽게 순열조합을 처리할 수 있습니다. 대부분 순열조합을 사용하는 문제는 인풋값이 10개 정도로 작아. 모든 경우의 수를 탐색해도 작은 시간을 소요할떄 사용합니다. 인풋값이 작아 모든 경우를 탐색해도 무방할 때. "순열조합을 사용하면 편하겠군, 개꿀~!" 이란 생각이 나는 것을 목표로 학습하면 좋습니다. permutaions permutaions(리스트, r) permutaions는 리스트와 같은 반복 가능한 객체와 자연수 r을 파라매터로 받습니다. 이를 실행하면 리스트에서 r개를 뽑아 순서를 고려하여 나열한 모든 경우의 수를 리턴합니다. 아래의 예시는 반복 가능한 객체 집합 {A, B, C}에 ..

목차 -시작 -stack -queue -문제 시작 stack과 que는 핵심 유형으로 분류될 만큼 중요한 자료구조입니다. 또한 다양한 알고리즘에 응용이 되어 사용됩니다. 이 두 알고리즘은 개념적으로 쉽지만. 처음 접한다면 문제에 응용하는데 까다롭습니다. 그래서 꼭! 문제를 풀어 보고 어떤 상황에 사용하면 좋은지 익혀야 합니다. stack stack은 사전에서 찾아보면. 쌓아 올린다는 뜻을 가지고 있습니다. 그래서 stack 자료구조는 자료가 들어오면 맨위에 쌓고. 자료가 나갈떈 마지막에 쌓아 올린 자료를 내보냅니다. stack 자료구조에 데이터를 저장하는 행위를 push라고 하고. 마지막 데이터를 빼내는 행위를 pop이라고 합니다. 위의 그림은 텅!빈 스택에 1과 2를 순차적으로 들여보내고(push). ..