개발윗미

[수학에서의 서로소 집합이란 ?] 수학에서의 서로소 집합이란 공통 원소가 없는 두 집합을 의미한다. 예를 들어 집합 {1, 2}와 집합 {3, 4}는 서로소 관계이다. 반면에 집합 {1, 2}와 집합 {2, 3}은 2라는 원소가 두 집합에 공통적으로 포함되어 있기 때문에 서로소 관계가 아니다. [서로소 집합 자료구조란 ?] 서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조라고 할 수 있다. 서로소 집합 자료구조는 union과 find 연산으로 조작할 수 있다. 여기서 union(합집합) 연산은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산이다. find(찾기) 연산은 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다. 서로소 집합 자료구조를..

[구간 합 문제란 ?] 연속적으로 나열된 N개의 수가 있을 때 특정 구간의 모든 수를 합한 값을 계산하는 문제이다. 예를 들어 5개의 데이터로 구성된 수열 {10, 20, 30, 40, 50}이 있다고 가정하고, 두번째 수부터 네번째 수까지의 합은 20 + 30 + 40 = 90 이다. 구간 합 문제를 빠르게 계산하기 위해 접두사 합(Prefix Sum)을 활용한 알고리즘을 사용할 수 있다. [접두사 합이란 ?] 배열의 맨 앞부터 특정 위치까지의 합을 미리 구해 놓은 것이다. 즉, 접두사 합을 활용한 알고리즘 동작과정은 다음과 같다. 1. N개의 수 위치 각각에 대하여 접두사 합을 계산하여 P에 저장한다. 2. 매 M개의 쿼리 정보를 확인할 때 구간 합은 P[Right] - P[Left - 1] 이다. ..

[투 포인터란 ?] 투 포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘이다. 리스트에 담긴 데이터에 순차적으로 접근해야 할 때는 시작점과 끝점 즉, 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다. 투 포인터 알고리즘의 동작 과정은 다음과 같다. 1. 시작점(start)과 끝점(end)이 첫 번재 원소의 인덱스(0)를 가리키도록 한다. 2. 현재 부분 합이 M과 같다면 카운트한다. 3. 현재 부분 합이 M보다 작다면 end를 1 증가시킨다. 4. 현재 부분 합이 M보다 크거나 같다면 start를 1 증가시킨다. 5. 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다. [투 포인터 알고리즘 예제] # 데이터의 개수 N n = 5 # ..

[에라토스테네스의 체란 ?] 에라토스테네스의 체는 다수의 자연수에 대하여 소수 여부를 판별할 때 사용하는 대표적인 알고리즘이다. 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다. 에라토스테네스의 체 알고리즘의 동작 과정은 다음과 같다. 1. 2부터 N까지의 모든 자연수를 나열한다. 2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다. 3. 남은 수 중에서 i의 배수를 모두 제거한다. (단, i는 제거하지 않는다.) 4. 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다. 이러한 에라토스테네스의 체를 이용해서 소수판별 프로그램을 C언어로 구현한 코드는 아래의 게시물에서 확인할 수 있다. https://unie2.tistory.com/42?categ..

[소수란 ?] 소수란 1보다 큰 자연수 중에서 1과 자기자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수이다. 즉, 6은 1, 2, 3, 6으로 나누어 떨어지므로 소수가 아니며, 7은 1과 7을 제외한 다른 수로 나누어 떨어지지 않기 때문에 소수이다. [기본적인 소수 판별 예제] def is_prime_number(x) : for i in range(2, x) : if x % i == 0 : return False return True print(is_prime_number(4)) print(is_prime_number(7)) 소수 판별 함수(is_prime_number) 를 통해 2부터 x-1 까지의 모든 수를 확인하며 만약 x가 해당 수로 나누어 떨어지면 소수가 아니기 때문에 False를 반환하고..

[위상 정렬이란 ?] 위상 정렬은 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미한다. 위상 정렬 알고리즘 학습 시 진입차수(Indegree)와 진출차수(Outdegree)가 존재하는데, 진입차수는 특정한 노드로 들어오는 간선의 개수이고, 진출차수는 특정한 노드에서 나가는 간선의 개수이다. 큐를 이용하는 위상 정렬 알고리즘의 동작 과정은 다음과 같다. 1. 진입차수가 0인 모든 노드를 큐에 삽입한다. 2. 큐가 빌 때까지 다음의 과정을 반복한다. (1) 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다. (2) 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. 3. 결과적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과와 같다. 구..

[신장 트리란 ?] 신장 트리는 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. [크루스칼 알고리즘이란 ?] 크루스칼 알고리즘은 대표적인 최소 신장 트리 알고리즘이다. 그리디 알고리즘으로 분류가 되며, 동작 과정은 다음과 같다. 1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다. 2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다. 만약, 사이클이 발생하지 않는다면 최소 신장 트리에 포함시키고, 사이클이 발생한다면 최소 신장 트리에 포함시키지 않는다. 3. 모든 간선에 대하여 2번의 과정을 반복한다. 구체적인 동작 과정은 아래의 게시물에서 확인할 수 있다. https://unie2.tistory.com/37?category=873806 크루스칼 ..

[순차 탐색이란 ?] 순차 탐색(Sequential Search)이란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용하며, 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소를 찾을 수 있다는 장점이 있다. [순차 탐색 예제] def sequential_search(n, target, arr) : for i in range(n) : if arr[i] == target : return i + 1 print("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.") data = input().split() n = int(data[0]) target = data[..

[정렬 알고리즘 이란?] 정렬(Sorting이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것이다. 정렬 알고리즘의 종류는 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬 등이 있다. 7 5 1 2 4 6 3 위와 같이 각각의 수가 존재할 때 기본적으로 오름차순으로 수를 정렬한다면 아래와 같다. 1 2 3 4 5 6 7 내림차순 또한 마찬가지로 정렬한다면 아래와 같다. 7 6 5 4 3 2 1 이와 같이 우리는 특정한 수들이 존재할 때 정렬을 금방 수행할 수 있지만, 컴퓨터는 인간과 다르게 데이터의 규칙성을 직관적으로 알 수 없으며, 어떻게 정렬을 수행할지에 대한 과정을 소스코드로 작성하여 구체적으로 명시해야 한다. [선택 정렬] 선택 정렬은 현재의 범위에서 가장 작은 데이터를 선택하여 맨 앞에 있는 ..

[재귀 함수란?] 자기 자신을 다시 호출하는 함수이다. [단순한 형태의 재귀 함수 예제] def recursive_function() : print('재귀 함수 호출') recursive_function() recursive_function() [재귀 함수의 종료 조건] 재귀 함수를 문제 풀이에서 사용할 때에는 재귀 함수의 종료 조건을 반드시 명시해야 한다. 종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있다. [종료 조건을 포함한 재귀 함수 예제] def recursive_function(i) : # 100번째 호출 했을 때 종료 if i == 100 : return print(i, '번째 재귀함수에서', i + 1, '번째 재귀함수를 호출') recursive_function(i + 1..