Problem Solving/Algorithm

1. 순열(Permutation) 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것 서로 다른 n개 중 r개를 택하는 순열은 아래와 같이 표현할 수 있다. 수식으로 나타내면 다음과 같다. 위 식을 간략화 하면 다음과 같다 순열 만드는 방법으로 반복문과 재귀문을 활용한 방법이 있다. 먼저 반복문으로 순열을 구하는 방법은 다음과 같다. 기존 수와 중복되지 않게 숫자를 한 개씩 뽑는 일을 가능한 모든 수에 대해 반복해서 시도한다. 목표하는 횟수만큼 "1"을 반복 (뽑는 횟수가 고정되어 있다면 목표하는 횟수까지 돌아가는 반복문으로 해결할 수 있지만, 정해지지 않았다면 뽑는 횟수만큼 재귀적으로 호출하는 구조를 이용하는 것이 적합할 수 있다.) (여기를 참고) 아래 코드는 반복문을 이용해 배열의 원소를 sw..

플로이드-워셜 알고리즘은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다. for문을 3번 사용하기 때문에 시간복잡도 O(N^3)이다. 플로이드-워셜 알고리즘은 2차원 테이블에 최단 거리 정보를 저장한다. (모든 지점에서 다른 모든 지점까지의 최단 거리를 저장해야 하기 때문) 그래프가 다음과 같다고 하자. 모든 정점 사이의 최단 경로를 다음 방법을 통해 찾는다. 1. n*n 2차원인 행렬 A0를 만든다. 여기서 n은 정점(노드)의 개수이다. n*n 배열에서 행, 열은 i, j로 인덱싱 된다. (i와 j는 그래프의 정점(노드) 이다) 2. 각 A[i][j]는 i번째 꼭짓점에서 j번째 정점까지 떨어진 거리로 채워진다. i번째 정점에서 j번째 정점까지 경로가 없으면 해당 원소를 무한대로..

Palindrome 알고리즘이란? 팰린드롬(회문) 은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열(sequence of characters) 등이다 - https://ko.wikipedia.org/wiki/%ED%9A%8C%EB%AC%B8 구현 def palindrome(a): if a == a[::-1]: return True else: return False print(palindrome([w for w in input()])) 이를 짧게 풀어서 다음과 같이 나타 낼 수 있다. def is_palindrome(word): return word[::-1]==word # True print( is_palindrome("kayak") ) print( is_palindrome("mad..

누적합 (Prefix sum) 누적합은 나열된 수의 누적된 합을 나타낸다. Sn은 An[0,0] 합, An[0,1]합, An[0,2]합 An[0,-1]합 을 나타낸다. 누적합의 점화식은 Sn = Sn-1 + An 이다. 위 그림은 인덱스가 0부터 4까지의 수열과 해당 수열의 누적합을 나타낸 이미지 이다. 누적합을 이용해서 인덱스가 2부터 4까지의 구간을 구하려면 [0부터 4까지의 누적합](녹색) - [0부터 1까지의 누적합](빨강색) 을 계산하면 된다. 즉, 구하고 싶은 구간은 보라색이며 누적합 0부터 4까지의 구간에서 빨강색 구간을 빼면 구할 수 있다. 누적합15-누적합3 = 12 (2부터 4까지의 구간) 인덱스가 2부터 4까지의 구간을 구하려면 2부터 4까지 인덱스를 돌면서 카운트 할 수 있겠지만 이..

이진 탐색 이진탐색은 정렬되어 있는 데이터에서 탐색범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 이진 탐색은 시작점, 끝점, 중간점의 위치 변수 3개를 이용한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다. 단계마다 탐색범위를 2로 나누어 시간복잡도는 O(logN) 이다. (log₂에 비례함) 이진탐색을 구현하는 방법은 재귀함수를 이용하거나, 반복문을 이용한다 이진탐색 문제는 탐색 범위가 큰 상황에서 탐색을 가정하는 문제가 많으므로 탐색범위가 2천만을 넘어가면 사용하는 것을 권장 이미지 출처 재귀함수로 구현 def binary_search(array, target, start, end): if start > end: return None mid = (s..

정렬(sorting) 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 선택정렬(Selection sort) 가장작은 데이터를 찾은 후에 맨 앞에 있는 데이터와 바꾸고, 그 다음으로 가장 작은 데이터를 찾은 후 두번째 데이터와 바꾼다. 가장 낮은 값이 맨 앞부터 정렬되며 전체 배열들이 정렬 될 때까지 이 과정을 계속 반복하여 정렬하는 과정을 선택정렬이라고 한다. 선택정렬은 구현이 간단하지만, 시간 복잡도가 (N^2 + N) / 2 이다. 즉 빅오표기법으로 O(N^2) 이다. 선택정렬은 기본 정렬 라이브러리를 포함해 다른 알고리즘과 비교했을 때 매우 비효율적이다. 선택 정렬 소스코드.py array = [22, 50, 17, 25, 18, 32, 33, 44, 29, 8] for i in range(le..

재귀함수를 이용한 피보나치를 구현해 보고 동적프로그래밍을 활용하여 쉽게 설명할 수 있는 예제인 피보나치 수를 소개한다. 그리고 동적프로그래밍이 무엇이고 이점이 뭔지 살펴보려 한다. 예제 문제 https://www.acmicpc.net/problem/10870 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 피보나치 수 정의 피보나치의 수를 구한다고 가정할 때 다음과 같이 나타낼 수 있다. (예시에서는 fib(5)) 피보나치 수열은 재귀함수 형태로 표현된다. pseudoco..

그래프를 탐색하는 방법인 깊이우선 탐색(DFS), 너비 우선 탐색(BFS)를 알아보자 깊이 우선 탐색(DFS) 한 지점을 골라서 팔 수 있을 때까지 계속해서 깊게 파다가 아무리 땅을 파도 물이 나오지 않으면, 밖으로 나와 다른 지점을 골라서 다시 깊게 땅을 파는 방법 즉, 루트 노드나 임의 로드에서 출발하여 최대로 진입할 수 있는 깊이까지 탐색하고 다시 돌아와 다른 노드로 같은 방법으로 탐색하는 방법. DFS는 방문한 노드들을 스택 자료구조를 통해 방문했는지 확인한다. DFS는 탐색시 해당 노드를 방문했는지 여부를 검사해야 한다. 이를 검사하지 않으면 계속 탐색하게 되어 무한 루프에 빠지게 된다 스택(Iterative) 또는 재귀함수(Recursive)로 표현함. 재귀함수로 간결하게 구현 가능 깊이 우선..