huiyu's blog

리스트(List) - 자료구조의 하나, 데이터를 일렬로 순차적으로 나열한 형태리스트를 구현하는 방법에는 배열을 이용하는 방법과 동적할당을 이용해 구현하는 방법이 있습니다.배열로 구현할 경우,구현이 간단하고, 인덱스를 참조하여 한번에 참조가 가능하다는 장점을 갖고 있지만, 갯수에 제한이 있어 유한적인 데이터만 넣을 수 있다는 단점을 갖고 있습니다. 동적할당으로 구현을 할 경우,새로운 자료가 입력될 때마다 새로운 주소로 메모리를 할당해주고 이전에 할당된 메모리를 연결해주므로 메모리 관리에 용이하다고 볼 수 있습니다.그래서 연결리스트(Linked List)란 각 노드가 데이터와 포인터를 갖고 있어, 각 노드가 다음 순서의 노드의 위치정보를 갖고 있는 방식으로 데이터를 저장하는 자료구조입니다. 연결리스트엔 세가..

백준 9465번 스티커 문제 풀이 : https://www.acmicpc.net/problem/9465 문제요약 : - 2xn개의 스티커를 갖고있다. 각 스티커는 점수가 있다.- 스티커를 떼면 그 스티커와 변을 공유하는 스티커는 찢어져 사용할 수 없다(점수x)- 뗄 수 있는 스티커 점수의 최댓값을 구하시오. 우선 이런 유형의 문제는 완전탐색을 하여 구현을 해봅니다.. 그다음 DP를 적용.. 1. 완전탐색을 할 경우를 생각해봅니다. "-->" 오른쪽 방향으로 탐색을 했을 때, 스티커를 떼는 방법은 위를 떼는 방법, 그리고 아래를 떼는 방법 두가지가 존재합니다. 우선 공유하는 변의 스티커가 뜯어지는 경우를 무시하고 전체 경우를 구한다면, 아래와 같이 구현할 수 있습니다. 12345678int solve(in..

배낭문제(Knapsack Problem)란, 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제를 말합니다 배낭에 짐을 넣을 때,짐을 쪼개서 넣을 수 있는 경우와 쪼개지 못하고 넣는 경우 두가지가 존재하는데, 쪼갤 수 있는 경우 분할가능 배낭문제(Fractional Knapsack Problem),쪼갤 수 없는 경우 0-1 배낭문제(0-1 Knapsack Problem)이라 부릅니다. 쪼갤 수 없는 0-1 Knapsack의 경우 동적계획법(Dynamic Programming)으로 풀 수 있습니다. -> 위키백과 냅색 문제는 아래 링크에서 풀어 볼 수 있습니다. ->0/1 Knapsack 문제 보러가..

문제)타일채우기(S)2x1 혹은 2x2 크기의 타일을 2xn 크기의 직사각형 모양 틀에 넣으려고 한다. 이 때 가능한 경우의 수를 구하여라. 경우의 수가 커지므로, 주어지는 수 m으로 나눈 나머지를 출력한다. 첫 줄에는 직사각형 틀의 가로 길이 n이 주어진다. 둘째 줄에는 m이 주어진다 (1

문제)Combination nCk 는 n개 중 k개를 고르는 방법의 수이다. nCk를 구하는 일반식은 다음과 같다. 위 식은 n!을 이용하기 때문에 n이 커지면 overflow가 발생하여 정확한 값을 구할 수가 없다. 물론 위 방법 외에도 다양한 점화식으로 구할 수 있다. nCk를 정확하게 구하는 프로그램을 작성하시오. 첫 번째 줄에 n과 k가 공백으로 구분되어 입력된다. (단, 1 n >> k; cout

DFS/BFS의 경우 사실 이론은 조금만 읽어도 금방 이해가 가능한데요,그러나 막상 처음 구현하려 하면 바로 구현하기 힘든 경우가 많은데 알고리즘 문제를 반복적으로 풀며 구현해보면 금방 익숙하게 구현할 수 있게 됩니다. 다음은 DFS/BFS 학습을 위해 풀었던 문제들로[기본]은 간단하게 DFS/BFS를 이용하여 풀 수 있는 문제이고, [응용]은 DFS/BFS 중에도 조금 응용을 해야 풀 수 있는 문제입니다기본적인 이론을 학습한 후 아래 문제들을 순서대로 풀어보면 좋을 것 같습니다. [기본]1. 바이러스 : https://www.acmicpc.net/problem/26062. 단지번호 붙이기 : https://www.acmicpc.net/problem/26673. 보물섬 : https://www.acmic..

관계기반 알고리즘 설계(1) 탐색기반 알고리즘 설계 : 컴퓨터의 빠른 연산 속도를 이용하여 짧은 시간에 가능한 해의 집합을 탐색하면서 최적의 해를 구하는 기술적인 방법(2) 관계기반 알고리즘 설계 : 해를 구하는 행위를 하나의 함수로 표현하고 이 함수들의 관계를 이용하여 해를 구하는 방법 - 문제의 정의 및 상태를 함수로 정의, 이 함수들 간의 관계를 점화식 혹인 이와 유사한 형태로 표현, 수학적 귀납법/점화식 등의 표현 기반 수학적 귀납법 - 자연수 n에 관한 명제 P(n)이 모든 자연수에 대해서 성립함을 증명하기 위한 수학의 증명법 중 한 방법 - 다음의 두가지 단계로 증명 1) P(1)이 성립함을 보인다. 2) P(k)가 성립한다고 가정하고 P(k+1)이 성립함을 보인다. - 수학적 귀납법을 이용한..

※ 탐색이란? - 같은 형태의 한 개 이상의 자료들이 모여 있는 집합에서 특정 자료를 찾는 모든 작업 - 탐색할 자료가 저장되어 있는 구조를 먼저 파악하는 것이 중요 (탐색 구조가 직접적으로 드러난 경우는 쉬운문제, 직접 드러나지는 않으나 문제 해결과정에서 자체적으로 구조화하며 탐색하는 경우 중급 이상 문제) ※ 탐색기반설계 - 주어진 문제에서 주어진 데이터를 특성에 맞도록 구조화하고 이 자료를 적절한 방법으로 탐색해 나가면서 원하는 해를 찾는 알고리즘 설계법 - 전체를 탐색하는 전체탐색법과 탐색할 영역을 적절한 방법으로 배제하여 탐색의 효율을 높은 부분탐색법이 있다. ※ 탐색이 되는 구조 - 선형구조 : 배열이나 연결리스트로 표현될 수 있는 구조 - 비선형구조 : 트리나 그래프의 형태로 표현되는 구조 ..

병합정렬은 전체 원소를 하나의 단위로 분할한 후 분할한 원소를 다시 병합하는 정렬방식이다. 병합정렬 작동 순서1. 정렬한 데이터 집합을 반으로 나눈다.2. 나누어진 하위 데이터 집합의 크기가 2이상이면 이 하위 데이터 집합에 대해 1을 반복한다.3. 원래 같은 집합에서 나뉘어져 나온 하위 데이터 집합 둘을 병합하여 하나의 데이터 집합으로 만든다. 단 병합할 때 데이터 집합의 원소는 순서에 맞춰서 정렬한다.4. 데이터 집합이 다시 하나가 될 때까지 3을 반복한다. 5, 1, 6, 4, 8, 3, 7, 9, 2의 데이터를 정렬한다고 할 때 다음의 과정을 거쳐서 정렬을 한다.먼저 알고리즘의 1-2 과정을 반복해 데이터 집합을 나눈다.파란색 블록은 중간의 기준점을 의미 분할을 끝낸 뒤에는 '정복'을 수행, 합칠..

분할정복이란?문제를 더 이상 나눌 수 없을 때까지 나누고, 이렇게 나누어진 문제들을 각각 풂으로써 결국 전체 문제의 답을 얻는 알고리즘 분할 정복의 과정 1. 분할(Divide) : 문제가 분할이 가능한 경우, 2개 이상의 하위 문제로 나눕니다. 2. 정복(Conquer) : 하위 문제가 여전히 분할이 가능한 상태라면 하위 집합에 대해 1-을 수행합니다. 그렇지 않다면 하위 문제를 푼다. 3. 결합(Combine) : 2과정에서 정복된 답을 취한다. 분할정복법은 어떤 것에 적용하는가? 1. 문제를 작게 쪼개는 것이 가능한가?(Divide) 2. 쪼개진 문제들을 조합하여 문제의 답을 효율적으로 구할수 있는지(Merge & Conquer)