영..환...코테..정..리한..다..하..기싫..다...그..래도...한..다... 1. 각 자리수의 합 10으로 나눈 나머지는 1의 자리 수기존의 수를 10으로 나눈 몫은 1의 자리 수를 날리는 것.n = int(input())answer = []while n != 0: answer.append(n%10) n = n // 10 2. 순열 검사 중복없는 배열인지. 배열의 길이 만큼만 있는지[4, 1, 2, 3] OK[4, 2, 3] No ->  4는 배열의 길이 3보다 크므로. 풀이 방법 1 : 확인해야 할 array와 길이가 같으며 index가 값의 위치이다.ex) index = 0 : 숫자 1의 위치 and 숫자 1이 array에 있는 개수 def solution(arr): answer ..

다이나믹 프로그래밍은 이름처럼 문제 해결과정을 역동적으로 진행해 나가는 알고리즘 풀이 방식이다.예를들어, divide and conquer 방식의 경우 문제의 크기를 줄여나가면서 그 문제를 정복해 나가며 합치는 과정을 진행한다. 하지만! 다이나믹 프로그래밍은 단순히 문제의 크기를 나누어 가는 것이 아니라, 중복된 부분에 대한 효율적인 처리 방법에 대해서 고민한다. 어떤 때에 이 방식을 사용할 수 있을까?최적부분구조가 있을 때중복된 부분이 있을 때. 최적 부분 구조란 부분문제의 '최적의 답'을 이용해 전체 문제의 '최적의 답'을 찾을 수 있는 구조이다.  예를들어 피보나치의 경우 전체 큰 문제를 계속 나눠가며 그 값들을 합쳐 올라가는데, 이 나누어진 값들을 최적부분구조라고 한다. *divide가 된다면, ..

문제의 크기가 너무나 커서 접근하기 어려울 때, 우리는 그 문제의 크기를 줄여나가면서 해결책을 찾아보기도 한다.예를들어 크기가 100인 문제가 있으면 이를 각각 50의 크기로 쪼개 부분문제를 만들어 이를 각각 해결하고,해결한 문제의 답을 합쳐서 100의 크기의 문제를 해결하는 식이다. 이 알고리즘은 총 3종류의 단계가 있다. DivideConquerCombineDivide 단계는 문제의 크기를 나누는 과정으로 문제의 크기를 계속 줄여준다는 점에서 recursive case로 표현된다Conquer 단계는 문제의 크기가 충분히 작아 답을 찾을 수 있는 단계라는 점에서 base case로 표현 가능하다.그런데... 이게 말처럼 쉽지는 않다.conquer를 하는 과정에서 문제 크기가 예상외로 충분히 작지 않아 ..

우리가 알고리즘 문제를 만났을 때, 가장 먼저 해보아야 할 방식이 Brute force 접근 방식이다.Brute = 무식한 , Force = 힘 으로, 무식하게 접근하는 알고리즘 문제 접근 방법이다. 해가 존재할 것이라 기대되는 영역의 처음부터 끝까지를 조사하는 방식으로, 알고리즘 설계 방식에서가장 기초적인 방식이라 할 수 있다.원하는 답을 설계시 영역을 잘 설정했다면 100% 얻어낼 수 있는 방식이지만 input이 매우 큰 경우에도 과연 그럴까? 이 알고리즘은 답을 찾을 확률이 상대적으로 높으나 반드시 찾을 수 있는 것은 아니다. input의 값이 매우 크거나 컴퓨터 성능이 좋지않다거나해서 모든 범위를 탐색하는 것이 유의미한 시간 범위를 넘어가는순간에 답을 찾는 것이 의미가 없어지는 상황이 발생할 수 ..

이진 탐색을 사용하기 위해선, 정렬된 리스트를 사용해야 한다고 했다. 그러면 그냥 sort 메소드나 sorted 함수를 사용하면 될탠데... 이런 기능이 어떻게 작동하는지 알아보자! 선택 정렬선택 정렬은 기준 값을 하나 선택해서 모든 다른 리스트의 값과 비교해가며 더 작은 값들을 찾아서 정렬해가는 알고리즘을 사용한다.-> 각 위치에 어떤 값이 들어갈지 찾는 것. def selectSort(list_): for i in range(len(list_)): minIndex = i for j in range(i+1,len(list_)): if list_[i] list_[j]: minIndex = j temp = list_..

우리가 늘상 사용하는 index(list, data)는 과연 어떤 원리로 동작하는 것일까?기본적으로 어떠한 리스트에서 데이터의 위치를 찾는 것을 목표로 동작해야한다. 즉, 데이터의 값이 어디있는지 찾고, 그 값의 인덱스를 리턴해주어야 한다. 우리는 보통 무언가를 찾을 때 처음부터 쭈욱~ 찾아보거나 어떤 기준을 잡고 살펴보기 시작한다.한 뭉텅이씩 눈에 들어오는 양만큼 그룹을 묶어서 찾는다거나, 절반을 먼저보고 나머지를 본다거나... 컴퓨터도 똑같이 리스트에서 데이터를 찾을 때, 처음부터 쭉 살펴보거나 어떠한 기준을 가지고 리스트를 살펴보기 시작한다. 가장 기본적인 탐색 방법으로 선형 탐색과 이진 탐색에 대해서 살펴보자. 선형 탐색선형 탐색은 말 그대로 리스트를 linear하게 살펴보면서 데이터의 위치를 찾..

점근 표기법에서 n은 무엇인가?점근 표기법에서 n은 특별한 의미를 가지는 것은 아니다. 우리가 함수에 매개변수를 임의로 설정하듯이 이 n 또한 임의로 설정된 인풋의 크기이다. 인풋 리스트의 크기를 x라고 부르기로 하면 O(x), O(x^2).. 이런식으로 하겠지? “트리”나 “그래프” 같은 조금 특수한 자료 구조가 인풋으로 들어올 수도 있다.트리와 그래프가 특수한 이유는 리스트처럼 “선형적”이지 않기 때문인데, 예를 들어서 그래프는 꼭짓점(vertex)과 변(edge)으로 이루어져 있다. 꼭짓점의 개수를 V라고 하고 변의 개수를 E라고 하면,두 꼭짓점 간 최단 경로를 찾는 BFS 알고리즘의 시간 복잡도는 O(V + E)이다. O(1)은 코드 한 줄의 단위?아니다!인풋 크기와 상관 없이 실행되는 코드만 O..