본문 바로가기

하루 30분 알고리즘 기초다지기

 (18)
[python]파이썬 나이트 투어 반복 알고리즘 Knight's Tour Problem iteration https://codinghago.tistory.com/55 [python]파이썬 나이트 투어 재귀 알고리즘 Knight's Tour Problem recursiveKnight's Tour Problem 체스판에서 기사(Knight)말의 움직임은 아래와 같다. 임의의 위치에 놓여진 기사를 움직여서 모든 64개의 격자를 모두 방문하도록 기사말을 옮기는 방법을 계산하라. 단, 기사가codinghago.tistory.com 앞서 살펴보았던 나이트 투어 알고리즘을 재귀함수가 아닌 반복문으로 해결해 보려고 한다. stack을 사용하면 반복문으로 해결할 수 있다.  스택(STACK)스택은 자료구조의 한 형태로, LIFO(Last In First Out) 후입선출의 원칙에 따라 데이터를 관리한다. 즉,  가장 마지막..
[python]파이썬 나이트 투어 재귀 알고리즘 Knight's Tour Problem recursive Knight's Tour Problem 체스판에서 기사(Knight)말의 움직임은 아래와 같다. 임의의 위치에 놓여진 기사를 움직여서 모든 64개의 격자를 모두 방문하도록 기사말을 옮기는 방법을 계산하라. 단, 기사가 이미 방문한 격자는 다시 방문하지 않는다.  풀이 과정나이트가 움직일 수 있는 방향 저장 [1, -2], [2, -1], [2, 1], [1, 2], [-1, 2], [-2, 1], [-2, -1], -1, -2]초기 위치에서 나이트가 갈 수 있는 방향으로 전진. 체스판 안의 위치인지 확인.한번도 가지 않은 길이면 전진가능 mark배열에 갔던곳 표시 .한번 갔던 길이면 다시 후진 다른 경로 찾음.위의 과정을 반복하며 갈 수 있는 길로 전진, 갈 수 없으면 되돌아오기를 반복한다.  코드 구현..
[python] 파이썬 선택 정렬 알고리즘 (selection sort) Selection sort선택 정렬은 제자리 정렬(in-place) 알고리즘의 하나로, 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다. 시간 복잡도는 O(N^2)이다.  알고리즘은 이렇다. 아직 정렬이 안된 배열에서 가장 작은 수를 찾는다.  min그 값을 정렬이 안 된 배열의 맨 앞으로 보낸다. 이 과정을 반복한다. def selectSort(arr, n): for i in range(0,n-1): min = i; j = i+1 while(j
[python]파이썬 삽입정렬 알고리즘 (insertion sort) Insertion Sort삽입 정렬은 자료배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열부분과 비교하여, 자신의 위치를 찾아 삽입하는 정렬 알고리즘이다. 삽입 정렬은 배열이 길어질수록 효율이 떨어지지만 구현이 간단하다는 장점이 있다. 시간 복잡도는 O(n^2)이다.  과정정렬이 안된 배열에서 제일 앞에 것을 선택 arr[i]정렬된 배열의 가장큰 원소부터 작은 원소 순으로 비교 arr[j]만약 arr[i]가 arr[j]보다 크다면  j+1위치에 arr[i] 삽입 만약 arr[j]가 arr[i]보다 크다면 arr[j+1]위치에 arr[j]를 옮겨서 한칸씩 뒤로 옮김  파이썬 코드로 구현하면 이와 같다. def insesrtionSort(arr, n): for i in range(1,n): ..
[파이썬] Permutation 순열 나라야나 판디타 알고리즘 구현하기 Permutation(순열)순열은 어떤 집합의 원소들을 특정한 순서로 배열하는 것을 말한다. 서로 다른 원소로 만들어진 순열의 수는 n!이다. ex) a, b, c가 원소일 때 순열abcacbbacbcacabcba Compute All Permuntaionn개의 서로 다른 문자로 만들어진 스트링이 주어졌을 떄, 이 문자열에 속하는 문자들의 모든 순열로 만들어진 n!개의 문자열을 출력하는 알고리즘을 구현해 보자.파이썬으로 순열을 구하는 가장 기본적인 방식으로 백트래킹을 사용하는 방법이 있다. 이 방법은 문자열의 각 문자를 하나씩 고정하고, 나머지 문자를 재귀적으로 순열을 구하는 방식이다.   def permute(str_list, start, end): if start == end : print(""..
[python] 최대공약수 유클리드 호제법 알고리즘 최대공약수 정수들의 공약수는 동시에 그들 모두의 약수인 정수이다. 공약수 가운데 가장 큰 것을 최대공약수라고 한다.  유클리드 호제법유클리드 호제법은 2개의 자연수의 최대공약수를 구하는 알고리즘이다. 두개의 자연수 a, b (a > b)가 있다고 할 때 a, v에 대해서 a를 b로 나눈 나머지를 r이라고 하면 a와 b의 최대 공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라 b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 떄 나누는 수가 a와 b의 최대공약수 이다.  1. 반복되는 규칙 찾기 두 정수 a, b의 최대 공약수 gcd( a, b ) 를 구하고자 하낟. a를 b로 나눈 나머지를 r이라고 한다.a와 b의 최대공약수는 b와 ..
[python] 하노이 탑/타워 알고리즘 재귀함수로 구현하기 (Hanoi Tower) Hanoi Tower하노이 타워는 3개의 기둥에 원반들을 쌓아 놓고 다른 쪽으로 옮기는 게임이다. 원반은 가장 아래쪽에 있는것이 가장 크고 위로 갈 수록 점차 작아져 전체적으로 원추형의 탐을 이루고 있다. 1에 놓여있는 모든 원반을 3으로 모두 옮겨야 하는데 이때 규칙이 있다.  [규칙]1. 한번에 하나씩만 옮길 수 있다.2. 작은 원반위에 더 큰 원반을 놓을 수 없다.  이렇게 복잡해 보이는 하노이 타워도 재귀함수로 쉽게 구현할 수 있다. 원반을 직접 옮겨보며 반복되는 규칙을 찾아보자!!  1. 하노이 타워  반복되는  규칙 찾기 1) n=1 1 ➞ 3 ... 1회 2) n=2 1 ➞ 21 ➞ 32 ➞ 3 ... 3회 3) n=31 ➞ 31 ➞ 23 ➞ 2 1 ➞ 3 2 ➞ 12 ➞ 31 ➞ 3 .....
[파이썬]팰린드롬(Palindrome) 판별하기 Palindrome(회문) 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열 등이다. ex) 기러기, madam, malayalam ....  Palindrome 판별 방법 제일 처음과 제일 끝의 문자열 비교 ➞ 두번째와 끝에서 두번째 비교 ➞ 세번째와 끝에서 세번째 비교 .......➞ 겹치는 지점까지 비교해서 두 문자가 같은지 다른지 판별하면 된다. 비교했을 때 같은 값이 나온다면 넘어가고 다른 값이 나오면 팰린드롬이 아니기 때문에 멈추면 된다.   알고리즘 구현 Palindrome판별 방법을 재귀함수로 구현해보자. def palindrom(num_list, first, last): if(last  palindrome 문제를 재귀함수로 구현하게 되면 단점이있는데 바로 호출이 ..

티스토리툴바