Dolphins의 HelloWorld

빅 오 분석 : 입력 값의 개수에 따라 알고리즘이 수행되는 데 걸리는 시간을 바탕으로 알고리즘의 효율성을 판단하는 실행 시간 분석법 빅 오 분석법에서는 입력 값의 개수(크기)를 n개라고 가정한다. 빅 오 실행시간 분석은 다음과 같이 이루어진다. 1. 입력 값을 확인하고 n을 어떤 값으로 놓아야 할지 결정.2. 알고리즘에서 수행해야 할 연산 횟수를 n으로 이루어진 식으로 표현3. 차수가 제일 높은 항 남기기.4. 모든 상수 인수를 없앤다. 성능이 좋은 것부터 나쁜 것까지 순서대로 알고리즘 종류를 나열해보면 다음과 같다. O(lg n) > O(n) > O(n lg n) > O(n^c) > O(c^n) > O(n!)(lg는 밑이 2인 로그함수를 의미) 왼쪽이 성능이 가장 좋은것이고 오른쪽으로 갈 수록 나빠지는..

유니온파인드란? 유니온 파인드는 상호 배타적 집합이라고도 하며 누군가 어떤 집합에 속해있는지 알아내기위해, 또는 집합끼리 합치기 위해 사용하는 자료구조이다. 구현 트리를 통해서 이 자료구조를 구현하게 되는데 기본은 각 원소마다 배정된 배열에 자신의 index를 넣는것이다 즉 arr[i] = i로 초기화하는 것이다. 이것을 풀어서 설명하면 i의 부모노드는 i 라는것을 의미한다. 먼저 x가 어떤 집합에 포함되어 있는지 찾는 연산인 find함수에 대해 설명하겠다. 다음과 같이 구현이 되어 있다. 일단 if문을 보면 가장 상위 노드까지 올라가면 그 노드를 반환하는 식으로 되어있다. 그렇다면 else문에서 그냥 find함수를 호출하기만 하면 되는데 arr[x] = y라는 과정을 추가했을까 그 이유는 실제로 활용할..

문제링크 : https://www.acmicpc.net/problem/9935 풀이 스택을 이용하여 푼 문제이다. 스택에는 pair형식을 통해 첫번쨰 인자로 해당 문자, 두번째 인자로 index를 주었다. index같은 경우는 폭탄의 각 문자의 index로써 index를 0으로 초기화 한후 만약 문자열[i] = 폭탄[index]라면 스택에 문자열[i]와 index를 넣어준 후 index+1을 하여 계속 비교해나가는 식으로 진행하였다. 이 떄 만약 폭탄에 없는 문자가 나왔을 떄는 index로 -1을 넣어 주었으며 이렇게 진행하다가 index가 폭탄의 마지막 index까지 도달하면 해당 폭탄의 문자열만큼 스택에서 제거해주는 방식을 취하였다. #include #include #include #include u..

문제링크 : https://www.acmicpc.net/problem/1182 풀이 이런 문제를 해결해야 할 때 가장 먼저 하게되는 고민은 어떻게 모든 부분집합을 검사하는가이다. 이 때 이런 고민을 쉽게 해결할 수 있게 해주는 것이 비트마스크를 활용하는 것이다. 위의 문제의 경우같이 원소가 5개인 집합의 부분집합을 모두 검사한다고 해보자 일단 만약 원소가 5개라면 부분집합의 총 가짓수는 2^5 인 32가지가 될 것이다.(원소가 n개일 때 부분집합의 총 갯수는 2^n 이다.) 고로 변수 n에 원소의 갯수가 저장되어있다고 하면 0부터 1

다음 순열 순열을 사전순으로 나열했을 때, 다음에 오는 순열을 어떻게 찾을것인가? ex) 현재 3 4 1 2 라고 나열되어 있을 때 다음 순열인 3 4 2 1 을 어떻게 출력할 수 있을까 다음 순열을 찾는 알고리즘은 다음과 같다. 1. A[i-1] = i 이면서 A[j] > A[i-1]을 만족하는 가장 큰 j를 찾는다. 3. A[i-1]과 A[j]를 swap 4. A[i]부터 순열을 뒤집는다. 코드를 작성한 후 결과를 확인해보면 다음과 같다. #include using namespace std; bool next(int *arr, int size) { int x, y; for (int i = size - 1; i > 0; i--) { if (arr[i..

비트마스크란 비트연산을 사용하여 부분 집합을 표현하는 것이다. 기본적으로 &, | , ~ , ^ (and,or,not,xor) 연산이 있으며. 비트연산중에는 > 연산이 있다. 만약 A > B 같은 경우 오른쪽으로 B비트만큼 민다는 의미를 가진다. 실제로 직접 밀어보면 왼쪽으로 밀 때는 숫자가 2^B배가 되고 오른쪽으로 밀 때는 숫자가 2^B로 나눈값이 된다. 비트마스크의 가장 큰 특징은 정수로 집합을 나타낼 수 있다는 점이다. 예를들어 70을 8자리의 비트셋으로 나타내면 01000110이다. 이것을 1이 있는 자리인 {1,2,6}으로 표현할 수 있는것이다. - n이 포함되어 있는지 검사 만약 2가 포함되어있는지 검사하고 싶다면 70 & ( 1

문제 링크 : https://www.acmicpc.net/problem/1201 비슷한 문제를 풀 때 활용할만한 부분이 있어서 개념부분으로 따로 뺀 문제이다. 먼저 어떤 경우에 문제의 조건에 맞게 최대 부분 증가 수열의 길이가 M이고 최대 부분 감소 수열의 길이가 K인 수열을 출력할 수 있는지 살펴보겠다. 일단 주어지는 수 N은 M+K-1 이상이어야 한다. 당연히 증가,감소 수열이 한번씩은 나와야 하기 때문에 M+K라는 수식이 나오는 것이며 1이 빠지는 이유는 두 수열이 숫자 하나를 공유하기 때문이다. 예를들어 위의 예시에서 2 1 4 까지 보면 증가, 감소 수열이 하나씩 나타나는데 이 수열이 1을 공유하고있음을 볼 수 있다. 다음으로 N은 M*K보다는 작거나 같아야 한다. 예를들어 만약 M이 3이고 K..

트리의 모든 노드를 방문하는 순서 종류 - preorder (전위순회) - 루트 노드의 방문 - 왼쪽 서브트리의 순회 - 오른쪽 서브트리의 순회 ex) 탐색 순서를 살펴보면 그래프의 DFS순서와 같다는 것을 알 수 있다. - inorder (중위순회) - 왼쪽 서브트리의 순회 - 루트 노드의 방문 - 오른쪽 서브트리의 순회 ex) - postorder (후위 순회) - 왼쪽 서브트리의 순회 - 오른쪽 서브트리의 순회 - 노드방문 ex) 코드짜보기 백준 1991번 문제를 통해 트리의 순회에 대한 코드를 짜는 법을 살펴볼 것이다. 이 문제는 순회의 방법에 따라 코드를 짜는 것 자체가 풀이가 되기 때문에 만약 이 문제를 맞췄다면 어느정도 트리의 순회에 대해 이해를 했다고 볼 수 있을것이다. #include u..

Knapsack Problem이란 주어진 용량을 초과하지 않으면서 물건의 가격이 최대가 되게 하는것이다. 다음과 같은 조건이 있다고 해보자. 배낭의 용량 : 15kg 물건 번호 (i) 물건 i의 가격 물건 i의 무게 1 $4 12kg 2 $2 2kg 3 $2 1kg 4 $1 1kg 5 $10 4kg 이 문제를 해결하기 위해 다음과 같은 알고리즘을 적용한다. 여기서 OPT는 다음과 같은 이중배열을 의미한다. 여기서 물건번호가 1인것부터 우측으로 채워나갈 것이다. 먼저 하나라도 index가 0이면 0으로 채워준 상태에서 만약 물건의 무게가 좌표에서 가르키는 무게보다 크다면 바로 위의 좌표의 값을 채워준다.(채우고자 하는 무게보다 해당 물건의 무게가 무겁기 때문에 앞의 물건까지 채웠을 때 최댓값을 그대로 갖다..

Bipartite Graph 다음과 같은 성질을 가질 때 그 그래프는 Bipartite하다고 할 수 있다. 전체 vertex를 v1과 v2로 나누었을 때 -> v1노드끼리는 edge가 없음 -> v2노드끼리는 edge가 없음 -> v1과 v2와의 edge는 존재한다. v ∈ v1 , w ∈ v2 , (v,w) ∉ E 위의 그림에서 같은 집합의 노드끼리는 edge가 없는것을 쉽게 확인할 수 있다. 예를들어 다음과 같은 ring 형식의 그래프는 vertex가 홀수일 때는 Bipartite가 아니지만 , 짝수일 때는 Bipartite임을 알 수 있다. 이렇게 그래프가 Bipartite한지 아닌지는 DFS를 통해서도 판별할 수 있다. 다음의 문제를 통해 확인해보자. 확인을 위해 int check[]라는 배열을 ..