supergravity

목차 -시작 -이진 탐색 알고리즘 -이진 탐색 감잡기 -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). ..

목차 -인트로 -피보나치수열 -뒤에서 내려가기 : recursion -뒤에서 내려가는 방식을 효율적으로 만들기 : memo -앞에서 올라가기 : tublatioin -정리 시작 1.다이나믹 프로그래밍이 뭐임? 다이나믹 프로그래밍은 계산 결과를 저장해 두었다가, 필요할 때 사용하는 알고리즘 기법입니다. 우리는 다이나믹 프로그래밍 기법과 비슷한 행동을 초등학교 때부터 했습니다. 초등학교 때 했던 3 자릿수 곱셈에 대해서 생각해봅시다. 머리가 좋으신 분들은 이를 암산하여 계산하겠지만, 대부분의 우리는 그렇지 못했습니다. 그래서 학교에서는 곱할 두 수를 이면지에 작성하고, 한 자리씩 계산하여 마지막에 결과를 취합하는 방법을 사용하였습니다. 이 방법은 메모지에 결과를 저장하였다 사용한다는 점에서 다이내믹 프로그래..

목차 시작 좋은 알고리즘 알고리즘 성능 평가 문제를 접근하는 법 : 읽기 전부다. 짝퉁코드. 구현 출력결과 n 1 sum_1: 2 sum_2: 1 sum_3: 0 sum_4: 1 ---------------- n 1000 sum_1: 76 sum_2: 34320 sum_3: 1 sum_4: 1 ---------------- n 10000 sum_1: 662 sum_2: 3287307 sum_3: 1 sum_4: 2 ---------------- n 100000 sum_1: 7501 sum_2: 345793250 sum_3: 38 sum_4: 3 ---------------- 자 그럼 출력 결과를 분석해 봅시다. 함수 sum_1 sum_2 sum_3 sum_4 인풋 n에 대한 루프 1 중첩 2 중첩 0 중..