본문 바로가기

알고리즘

미로찾기 Maze [[0,0,0,0,0,0,0,1], [0,1,1,0,1,1,0,1], [0,0,0,1,0,0,0,1], [0,1,0,0,1,1,0,0], [0,1,1,1,0,0,1,1], [0,1,0,0,0,1,0,1], [0,0,0,1,0,0,0,1], [0,1,1,1,0,1,0,0]]위는 미로를 표현한 2차원 리스트이다. 1은 벽이라 통과할 수 없고 0은 통로이다. 출발점은 [0][0]이고 출구는 [n-1][n-1]인 지점이다. 순환적 사고현재 위치에서 출구까지 가는 경로가 있으려면1) 현재 위치가 출구이거나 혹은2) 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있거나 def findpath(x,y):if maze[x][y] == exit: return True #현 위치가 출구라면 Tru..
순환의 개념과 기본 예제 3 순환 함수의 기본 조건적어도 하나의 base case, 순환되지 않고 종료되는 case가 있어야 함.모든 case는 base case로 수렴해야 함. 암시적 매개변수가 아닌 명시적 매개변수를 사용해야 함 def search(data,n,target): for i in range(n): if data[i] == target: return i return -1 data = [1,2,3,4,5,6,7] print(search(data,7,4))암시적 : 리스트 data의 인덱스는 0부터 n-1이라고 생각하고 시작 인덱스는 생략함. def search(data,begin,end,target): if begin > end: # base case return -1 elif target==data[begin]:ret..
순환의 개념과 기본 예제 2 문자열의 길이 계산string = 'hello' def length(string): if string == '': return 0 else : return 1+length(string[1:]) print(length(string))문자열의 프린트str='hello' def printstr(str): if len(str) == 0: return print(str[0], end='') printstr(str[1:]) print(printstr(str))문자열을 뒤집어 프린트str='hello' def printstr(str): if len(str) == 0: return print(str[-1], end='') printstr(str[:-1]) print(printstr(str))2진수로 변환하여 출력def..
순환의 개념과 기본 예제 1 수도(pseudo) 코드로 적음 자기 자신을 호출하는 함수def func ():print("Hello") //Hello가 무한히 출력된다.func() 무한 루프에 빠지지 않기 위해서 recursion (재귀)를 벗어나는 base 조건이 필요하다k=4def func(k):if k
종만북 분할 정복 병합 정렬과 퀵 정렬 - 동작 원리와 시간 복잡도 병합 정렬 알고리즘은 수열을 절반으로 나눠 두개의 수열을 재귀 호출로 정렬한다. 쪼개서 정렬한 뒤 정렬된 배열을 합친다.수열의 크기가 1이 될때까지 쪼개고 정렬한 다음 합친다. 절반으로 나누는 건 O(1), 병합은 O(n)1. 반씩 나눈다.2. 재귀 호출로 정렬한다.3. 합친다.반씩 나눌수록 문제의 수가 증가하지만 문제의 크기는 줄어 한 단계에서 모든 병합에 필요한 총 시간은 O(n)이다.크기가 n인 배열을 크기가 1인 원소가 될 때까지 반으로 나누다보면 O(lgn)이 되고, 각 단계에 원소 수는 n으로 일정하므로병합 정렬의 시간 복잡도는 O(nlgn)이 된다.퀵 정렬 알고리즘은 병합 과정이 필요없다. pivot을 정해서 이보다 작은 건 왼쪽, 큰 건 오른쪽에 배치한다.pivot을 만드려면 O(n)이 걸..
종만북 수열의 빠른 합 파이썬 재귀 함수의 순서에 대해 설명책에는 c++로 쓰여 있는데 파이썬으로 코드 작성을 했다.import sys print('정수 n 입력') n = int(sys.stdin.readline()) def fastSum(n): if n == 1: return 1; if n%2==1: #홀수일 경우 return fastSum(n-1) + n; return 2*fastSum(n/2) + (n/2)*(n/2) print(int(fastSum(n))); 맨 아래 있는 print문의 fastSum 함수가 호출된다. n=10이다.fastSum은 fS라고 줄이겠다.스택엔fS(1)fS(2)fS(4)fS(5)fS(10)이렇게 쌓여있다.맨 위에 fS(1)은 n=1이므로 return 1이 된다.이후 fS(2)는 2*fS(1) + 1..
알고리즘 공부방법 출처 : https://www.acmicpc.net/board/view/13761 초중고 순으로 대회 문제를 푼다. 대회 문제를 풀고 솔루션 확인을 한다. 오일러 프로젝트 에서 기초를 쌓는다. 백준에서 접해보지 못한 문제를 푼다. 입사를 위해 실전 문제를 푼다.프로그래머스 코드 그라운드 에 들어가서 이것 저것 푼다. 카카오에선 c는 못쓰고 c++ java javascript python swift를 쓸 수 있다.삼성에선 c c++ java를 쓸 수 있다. 삼성에서 코딩 테스트를 만들자고 제안하시고 담당하신 분이 3개 언어를 제외한 다른 언어는 잡 기능이 많아서 안된다고 하셨던 것 같다. 헤더파일도 표준 입출력만 포함할 수 있다. 알고리즘 공부 순서 문제 해결 전략코딩과 디버깅알고리즘의 시간 복잡도 분석무..
빅오 표기법, 시간 복잡도, 공간 복잡도 이진 탐색 트리 O(log n)노드의 수는 8이므로 O(log 8) = 3이다. 만약 위와 같은 이진 탐색 트리에 1을 삽입하려면 1은 5보다 작으므로 왼쪽(1번), 1은 3보다 작으므로 왼쪽(2번), 1은 2보다 작으므로 왼쪽(3번)으로 가게 되고 3번의 비교만에 2의 자식 노드가 된다. 퀵 정렬, 병합 정렬, 힙 정렬 O(n log n) 6 4 3 1 을 하나의 원소가 될 때까지 나누려면 2번 나누면 된다. O(log 4) = 2, 원소의 개수만큼 버퍼에 원소를 넣어야 하므로 병합하려면 4번 해야한다. 병합 정렬의 시간 복잡도는 O(n log n)이다. 병합 정렬은 어떤 상황이던 O(n log n)의 시간 복잡도를 갖는다. 정렬이 어느 정도 되어 있는 배열이라면 다른 소트를 사용해야 한다. 삽입 정렬..

티스토리툴바