순열, 조합, 중복순열, 중복조합을 만드는 방법

순열, 조합, 중복순열, 중복조합을 만들 수 있는 여러가지 방법을 설명하겠다 마지막에는 한가지 방법으로 순열, 조합, 중복순열, 중복조합을 모두 만들 수 있는 방법을 알려주겠다 사용할 배열에는 1 2 3이 저장되어 있는 상태이다 이 배열을 이용하여 3개 중에서 2개를 뽑는 순열, 조합, 중복순열, 중복조합을 생성해보겠다 순열을 만드는 방법 1. 반복을 이용한 순열 가장 쉽게 만들 수 있는 순열이다 2~3개를 뽑는 경우에는 간단하게 사용할 수 있지만 뽑는 수가 많아지면 코드가 더러워(?)진다 static int[] arr = {1, 2, 3}; public static void per() { for (int i = 0; i < 3; i++) { for (int j = 0; j n) 함수를 종료시킨다 sta..

위상 정렬을 구하는 두 가지 방법

위상 정렬이란 다음과 같은 그래프가 있다 각 노드는 해야할 작업이며 작업은 이전 작업이 끝나야 시작할 수 있다 예를 들어 3번 작업을 하기 위해서는 2번 작업을 먼저 해야하고 2번 작업을 하기 위해서는 1번 작업을 먼저해야한다 그러므로 작업순서는 1 2 3이 된다 그러면 다음과 같은 경우를 보자 3번이나 5번 작업을 하기 위해서는 2번 작업을 먼저 해야하고 2번 작업을 하기 위해서는 1번과 4번 작업을 해야한다 그러므로 작업 순서는 1 4 2 3 5 or 4 1 2 3 5 or 1 4 2 5 3 or 4 1 2 5 3 이 될 수 있다 이처럼 작업 순서가 있는 경우 작업 순서를 구하는 것을 위상 정렬이라 한다 위상 정렬하는 방법 위상 정렬을 구하는 방법에는 두 가지가 있다 진입 차수가 0인 노드를 지우면서..

스택 - 후위표기식

계산기 문자열로 된 계산식이 주어질 때, 스택을 이용하여 계산식의 값을 계산할 수 있다 중위 표기법의 수식을 스택을 이용하여 후위 표기법으로 바꾼다 후위 표기법의 수식을 스택을 이용하여 계산한다 중위 표기법의 수식을 후위 표기법으로 변환하는 방법 수식을 하나씩 읽는다 수식이 피연산자이면 출력한다 수식이 연산자이면 스택에 push한다 연산자의 우선순위를 따진다 더이상 읽을 수식이 없으면 스택에 있는 연산자를 모두 pop한다 변환 방법의 예 1. 덧셈과 뺄셈의 경우 연산자는 스택에 push, 피연산자는 출력하기 스택에 사칙연산 우선순위가 동등한 연산이 있을 경우 해당 연산을 pop한 후 push하기 중위 표기식이 3+4+5 인 경우의 예 3은 피연산자이므로 출력한다 +는 연산자이므로 push한다 4는 피연산..

스택 - 괄호검사, DFS

스택의 구현 스택을 구현하기 위해서 필요한 자료구조 - 자료를 선형으로 저장할 저장소. 배열을 이용하여 스택 구현이 가능하다 스택의 연산 삽입(push) - 저장소에 자료를 저장한다 삭제(pop) - 저장소에서 자료를 꺼낸다 isEmpty - 스택이 공백인지 아닌지를 확인한다 peek - 스택이 top에 있는 item을 반환한다 static int st[] = new int [10]; int top = -1; // 스택에 마지막 삽입된 원소의 위치를 가리킴 st[++top] = 1; // 단순하게 구현한push st[top--] // 단순하게 구현한 pop // 간단하게 push 구현 void push(int x) { if (++top > st.length) { // overflow } else { st..

이진 트리의 종류

이진 트리란? 각 노드가 최대 2개의 자식 노드를 가질 수 있는 트리이다 정 이진 트리 (Full Binary Tree) 모든 노드가 2개 또는 0개의 자식을 갖는 이진 트리이다 아래 그림처럼 3의 자식이 하나밖에 없는 경우는 정 이진 트리가 아니다 완전 이진 트리 (Complete Binary Tree) 마지막 레벨 직전의 레벨까지는 모든 노드들이 다 채워진 트리이다 마지막 레벨에서는 노드들이 모두 채워질 필요가 없더라도 왼쪽부터 오른쪽으로 노드들이 채워져야 한다 아래 그림처럼 마지막 레벨 직전까지의 레벨이 모두 채워졌지만 마지막 레벨에서 노드가 왼쪽에서부터 채워지지 않은 경우는 완전 이진 트리가 아니다 완전 이진 트리의 높이 완전 이진 트리에는 높이와 관련된 성질이 있다 완전 이진 트리 안에 n개의 ..

Direct Access Table과 Hash Table

다음과 같은 key-value쌍의 데이터를 저장하려고 한다 key-value쌍을 저장하는 기본적인 두 가지 방법에 대해 알아보자 Direct Access Table 배열의 인덱스로 바로 접근하는 방법이다 배열에서 인덱스를 순서가 아니라 key라고 생각하고 key-value쌍을 저장하는 방식이다 key를 바탕으로 배열의 인덱스에 데이터를 저장한다 '57'키는 배열의 57번 인덱스에 저장하고 '208'키는 배열의 208번 인덱스에 저장하고 '900'키는 배열의 900번 인덱스에 저장하면 된다 각 key에 해당하는 value를 알고 싶으면 해당 인덱스에 접근하면 된다 가장 큰 장점은 배열의 인덱스에 O(1)으로 바로 접근할 수 있다는 것이다 반면에 단점은 공간을 많이 낭비한다는 것이다 위의 예시를 보면 사용하..

더블리 링크드 리스트 연산의 시간 복잡도

더블리 링크드 리스트의 접근, 탐색, 삽입, 삭제 연산에 대하여 시간 복잡도를 알아보자 더블리 링크드 리스트의 접근, 탐색 연산 더블리 링크드 리스트의 접근, 탐색 연산은 싱글리 링크드 리스트의 접근, 탐색과 똑같다 head 노드부터 하나씩 다음 노드로 가면서 원하는 위치에 접근하거나 원하는 데이터를 가진 노드를 찾는다 시간 복잡도는 리스트의 길이 n에 비례하므로 O(n)을 갖는다 더블리 링크드 리스트의 삽입, 삭제 연산 삽입 연산의 경우 특정 노드가 주어졌을 때, 특정 노드의 앞과 뒤 노드의 레퍼런스만 바꿔주면 된다 링크드 리스트의 길이와 상관없이 항상 일정한 시간이 걸리므로 시간 복잡도는 O(1)을 갖는다 삭제 연산도 마찬가지로 레퍼런스만 바꿔서 연결만 끊어주면 되므로 링크드 리스트의 길이와 상관없이..

싱글리 링크드 리스트 연산의 시간 복잡도

싱글리 링크드 리스트의 접근, 탐색, 삽입, 삭제 연산에 대하여 시간 복잡도를 알아보자 싱글리 링크드 리스트의 접근 연산 링크드 리스트의 접근 연산은 해당 노드에 바로 접근이 불가하다 head에서부터 차근차근 다음 노드로 가서 원하는 노드에 접근을 해야 한다 인덱스 x에 있는 노드에 접근하려면 head에서부터 x번 가야 한다 원하는 노드에 접근하는데 걸리는 시간이 몇 번째 인덱스인지에 비례하는 것이다 링크드 리스트 안에 있는 노드의 수를 n이라고 하면 마지막 노드에 접근하려면 head에서부터 총 n-1번을 가야 한다 그러므로 접근 연산은 최악의 경우 O(n)의 시간 복잡도를 갖는다 싱글리 링크드 리스트의 탐색 연산 링크드 리스트의 탐색 연산은 선형 탐색을 이용한다 가장 앞에서부터 다음 노드를 하나씩 보면..

시간복잡도 분할 상환 분석(동적 배열의 추가 연산)

동적 배열의 추가(append) 연산 동적 배열의 추가 연산의 시간 복잡도를 계산해보자 다음과 같은 배열에 새로운 데이터를 추가한다고 하자 두 가지 경우에 대해서 생각해 볼 수 있다 1. 배열에 남는 공간이 있을 때 이 경우는 그냥 빈 공간에 데이터를 저장하면 되므로 시간 복잡도는 O(1)이다 2. 배열이 꽉 찼을 때 이 경우는 기존의 배열보다 큰 배열을 만들고 기존 배열에서 새로운 배열로 값을 다 복사해야 된다 기존 배열의 0번 인덱스에 접근해서 값을 복사하고 새 배열의 0번 인덱스에 접근해서 값을 붙여 넣고... 이미 있던 n개의 데이터를 복사해야 되므로 O(n)이 되고 새로운 데이터를 추가해야 되므로 O(1)이 되어 총 O(n+1) = O(n)이 된다 정리 배열에 남는 공간이 있을 때: O(1) 배..

리스트는 사실 배열?(3/3)

리스트 그렇다 파이썬 리스트는 사실 동적 배열이다 C의 배열을 이용해서 구현한 동적 배열이다 리스트를 하나 만들어 보았다 리스트는 동적 배열이므로 내부적으로는 C의 배열이 만들어져 있다 우리는 리스트에 마음대로 값을 추가할 수 있다 동적 배열이기 때문에 상황에 맞게 배열의 크기가 조절되기 때문이다 우리는 리스트 내부에 있는 배열의 크기를 모른다 현재 리스트에 담긴 데이터 수가 5개여도 내부적으로는 5개짜리 배열이 있을 수도 있고 6개짜리 배열이 있을 수도 있고 16개짜리 배열이 있을 수도 있다 현재 num 리스트에는 5개의 데이터가 저장되어 있다 리스트의 길이를 출력해보면 리스트의 길이는 5라고 나온다 실제 내부적으로 사용하고 있는 공간이 더 많을지라도 파이썬은 우리가 저장한 공간에 대해서만 알려준다 파..