'📂코딩테스트:CodingTest' 카테고리의 글 목록 (8 Page)

[백준 11729번-파이썬]하노이 탑 이동 순서

2023.06.19

백준 (BOJ) 11729번 https://www.acmicpc.net/problem/11729 사용언어 : PYTHON 1.문제 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. *한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. *쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 2.풀이 재귀함수를 사용해서 풀어야 한다. 이전 포스팅에서 설명했던 암시적 매개변수인 각 장대를 명시적 매개변수 start, via end로 ..

📂코딩테스트:CodingTest

[알고리즘]최대 공약수(GCD) 알고리즘 - 유클리드 호제법

2023.06.19

기존 GCD구하는 방법 for i in range(min(a,b),0,-1): if a%i==0 and b%i==0: print(i) break a와 b중 작은 숫자부터 시작해서 1까지 감소하면서, 제일 처음 a와 b모두 나눠떨어트리는 수를 찾는 방법이다. 이러한 경우는 무차별 대입(Brute Force)로 O(N)의 시간복잡도를 갖는다. 유클리드 호제법 (Euclidean Algorithm) def gcd(a,b): # a>b if b==0: return a c=a%b return gcd(b,c) a를 b로 나눈 나머지를 r이라고 했을때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 성질을 이용한 것이다.(재귀함수 이용) 이러한 성질을 활용하여 b와 r의 최대공약수 r0를 구하고 r을 r0로 ..

📂코딩테스트:CodingTest

[알고리즘]병합 정렬(Merge Sort)

2023.06.19

병합 정렬(Merge Sort) 정렬 순서 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 분할(divide) : 정렬되지 않은 배열을 절반으로 잘라 두 배열로 나눈다. 정복(conquer) : 나눠진 두 배열을 재귀적으로 병합정렬을 사용해서 정렬한다. 결합(combine) : 두 배열을 다시 하나의 정렬된 배열로 합병한다. 분할 정복(divide and conquer)기법과 재귀 알고리즘을 이용하여 정렬하는 방식이다. 수행 과정 예시 다음과 같이 정렬되지 않은 배열이 있다. [6, 5, 3, 1, 8, 7, 2, 4]절반으로 잘라 두 배열로 나눈다. [6, 5, 3, 1] [8, 7, 2, 4]다시 두 배열을 나눠 네 개로 나눈다. [6, 5] [3, 1] [8, 7] [2, 4]마지막으로 네 ..

📂코딩테스트:CodingTest

카운팅 정렬(Counting Sort)Permalink

2023.06.19

카운팅 정렬(Counting Sort) 과정 배열에 존재하는 수의 개수를 세어서, 이를 바탕으로 정렬을 수행한다. 1.배열에 존재하는 각 값의 갯수를 저장하는 count 변수를 생성한다. 예를들어 count[1]=4 라면 배열에는 1의 값이 4개 있다는 것을 의미한다. count는 배열 원소의 최댓값까지를 인덱스로 사용한다. arr = [4, 7, 9, 1, 3, 5, 2, 3, 4] cnt = [0] * (max(arr) + 1) for num in arr: cnt[num] += 1 print(cnt) # [0, 1, 1, 2, 2, 1, 0, 1, 0, 1] 2. count배열을 누적합으로 계산하여 갱신하여 준다. 누적합으로 갱신하는 이유는 리턴 할 정렬된 배열 answer의 적절한 위치에 삽입하기 ..

📂코딩테스트:CodingTest

[알고리즘]시간복잡도

2023.06.19

시간복잡도 = 알고리즘의 자원(resource) 사용량을 분석 자원이란 실행시간, 메모리, 저장장치, 통신 등을 말하는 것 인데 그 중에서 실행시간에 대해서 표현 메모리 : 가격대비 메모리 용량이 크게 증가하여 상대적인 중요성이 감소되었다. 실행시간은 하드웨어, 운영체제, 언어, 컴파일러 등에 따라서 달라지게 되므로 실행시간을 측정하는 대신 연산의 실행 횟수를 측정해야 한다. 연산의 실행 횟수 입력 데이터의 크기(n)에 관한 함수로 표현하게 된다. 데이터의 크기가 같더라도 실제 데이터에 따라서 달라진다. (n개의 데이터에서 검색을 할 때, 운이 좋으면 바로 찾을 수도 있고, 운이 나쁘면 n개의 데이터를 모두 검색해서 찾아야 할 수도 있다.) 최악의 경우 시간복잡도 평균 시간복잡도 (평균 시간복잡도 분석이..

📂코딩테스트:CodingTest

[알고리즘]Recursion 응용(미로찾기)

2023.06.19

미로찾기 그림과 같이 wall 과 pathway로 구성된 미로를 탈출하는 코드를 recursion으로 구현할 수 있다. recursive하게 생각을 해야한다. 현재 위치에서 출구까지 가는 경로가 있으려면 현재 위치가 출구거나 이웃한 셀들 중 하나에서 출구까지 가는 경로가 있거나 간단하게 생각해보면 다음과 같이 구현할 수 있다. boolean findPath(x,y) if (x,y) is the exit return true; else for each neighbouring cell (x',y') of (x,y) do if (x',y') is a pathway cell if findPath(x',y') return true return false; (x,y)에서 출구까지 경로가 있으면 true, 없으면 f..

📂코딩테스트:CodingTest

[알고리즘]Recursion 개념

2023.05.03

순환은 수학함수 계산에만 유용한가? 팩토리얼, 피보나치 수열, 최대공약수와 같은 수학함수 뿐만 아니라, 다른 많은 문제들을 recursion으로 해결할 수 있다. 문자열 뒤집기 def f(s): if len(s)==0: return else: f(s[1:]) print(s[0],end='') s=input() f(s) abcdef fedcba Base Case : 문자열의 길이가 0이면 출력을 하지 않고 return 재귀적으로 이해를 해야한다. 첫 번째 문자를 제외한 문자열을 뒤집어서 출력하고, 그 다음 제외한 첫 번째 문자를 출력한다. 이렇게 하면 문자열이 뒤집어서 출력된다. 2진수로 변환하여 출력하기 def fun(n): if nend: return False elif lst[begin]==targe..

티스토리툴바