본문 바로가기

코딩/알고리즘20

[이코테] 23강 퀵 정렬 퀵 정렬 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나이다 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이다 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정한다 퀵 정렬 동작 예시 [Step 0] 현재 피벗의 값은 '5'이다. 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '7'이 선택되고 오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '4'가 선택된다. 이제 이 두 데이터의 위치를 서로 변경한다 [Step 1] 현재 피벗의 값은 '5'이다. 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '9'가 선택되고 오른쪽에서부터 '5'보다 작은 .. 2024. 3. 20.
[이코테] 17강 재귀 함수 재귀 함수 재귀 함수(Recursive Function)란 자기 자신을 다시 호출하는 함수를 의미한다 단순한 형태의 재귀 함수 예제 '재귀 함수를 호출합니다'라는 문자열을 무한히 출력한다 어느정도 출력하다가 최대 재귀 깊이 초과 메세지가 출력된다 def recursive_function(): print("재귀 함수를 호출합니다.") recursive_function() recursive_function() 재귀 함수의 종료 조건 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 합니다 종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있다 종료 조건을 포함한 재귀 함수 예제 def recursive_function(i): #100번째 호출을 했을 때 종료되도록 종.. 2024. 3. 20.
[이코테]4장_DFS, BFS 스택: 입구=출구, 가장 늦게 집어넣은 것을 가장 일찍 뺌 큐: 먼저 온 사람이 먼저 나감 재귀함수: 자기자신을 다시 호출하는 함수, 스택 자료구조 이용, 스택자료구조를 활용해야 하는 상당수 알고리즘은 재귀 함수를 이용해서 간편하게 구현될 수 있다. 재귀 함수의 종료 조건 명시해야 def recursive_function(i): if i == 100: return print(i, '번째 재귀 함수에서', i+1, '재귀 함수를 호출합니다.') recursive_function(i+1) print(i) recursive_function(1) def factorial_iterative(n): result=1 for i in range(1, n+1): result*=i return result def fact.. 2024. 3. 8.
[이코테]10장(3)_기타(소수판별, 에라토스테네스의 체) 소수 (Prime Number) 소수란 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수이다 6은 1, 2, 3, 6으로 나누어떨어지므로 소수가 아니다 7은 1과 7을 제외하고는 나누어떨어지지 않으므로 소수이다 코딩 테스트에서는 어떠한 자연수가 소수인지 아닌지 판별해야 하는 문제가 자주 출제된다 #소수 판별 함수(2이상의 자연수에 대하여) def is_prime_number(x): # 2부터 (x-1)까지의 모든 수를 확인하며 for i in range(2,x): #x가 해당 수로 나누어떨어진다면 if x%i == 0: return False #소수가 아님 return True print(is_prime_number(4)) print(is_prime_number(7).. 2024. 3. 8.
[이코테]10장_그래프이론(2)신장트리, 크루스칼 알고리즘 신장 트리 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이기도 하다 최소 신장 트리 최소한의 비용으로 구성되는 신장 트리를 찾아야 할 때 어떻게 해야 할까? 예를 들어 N개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결될 수 있게 도로를 설치하는 경우를 생각해 보자 두 도시 A,B를 선택했을 때 A에서 B로 이동하는 경로가 반드시 존재하도록 도로를 설치한다 크루스칼 알고리즘 대표적인 최소 신장 트리 알고리즘이다 그리디 알고리즘으로 분류된다 구체적인 동작 과정은 다음과 같다 간선 데이터를 비용에 따라 오름차순으로 정렬한다 간선을 하나씩 확인하며 현재의 간선이.. 2024. 3. 7.
[이코테]10장_그래프이론(1)서로소집합 서로소 집합 자료구조는 union과 find 이 2개의 연산으로 조작할 수 있다. union: 합집합 find: 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 1. union(합집합) 연산을 확인하여, 서로 연결된 두 노드 A,B를 확인한다. 1)A와 B의 루트노드 A', B'를 찾는다. 2)A'를 B'의 부모 노드로 설정한다.(B'가 A'를 가리키도록 한다.) 2. 모든 union(합집합) 연산을 처리할 때까지 1번 과정을 반복한다. 실제로 구현할 때에는 A'와 B' 중에서 더 작은 원소가 부모 노드가 되도록 구현하는 경우가 더 많다. ex> A'가 1이고, B'가 3이면 B'가 A'를 가리킨다(부모 노드로 설정한다). 전체 집합 {1,2,3,4,5,6}이 6개로 구성되어 있고, 다음과 같은 .. 2024. 3. 7.

티스토리툴바