알고리즘 (11) 썸네일형 리스트형 스택 문제 풀이2(16909, 카드 구매하기3)[Stack PS] 스택 가장 큰 특징 : LIFO 마지막에 넣은 게 가장 먼저 나온다 문제를 풀이하면서 가장 중요한 건 스택을 어떤 용도로 사용하고. 어떤 경우에 push를 하고, 어떤 경우에 pop을 해야 할까? 를 생각해야 된다. 문제풀이 11052 - 카드 구매하기 (실버1) : https://www.acmicpc.net/problem/11052 풀이 : N개의 카드를 구매하기 위해 지불할 수 있는 금액의 최댓값을 구하는 문제. 전형적인 dp(다이나믹 프로그래밍) 문제이며, N의 범위가 10^3으로 시간복잡도가 O(N^2)일 때 10^6으로 제한시간 내에 충분히 가능하다. 가장 쉬운 방법으로는 가능한 모든 경우의 수를 구하여 값 중 최댓값을 구하는 것이다. 하지만 같은 카드를 구매하는 경우에서 굳이 적은 비용을 낼 .. 분할 정복법(Divide and Conquer)(이분 탐색, 퀵 소트, 퀵 셀렉트, 머지 소트(병합 정렬))(Binary Search, Quick Sort, Quick Select, Merge Sort) 1. 분할 정복법이란? 2. 분할 정복법의 속성 3. 대표적인 분할 정복 알고리즘(이분 탐색, 퀵 소트, 퀵 셀렉트, 머지 소트) 4. 분할 정복 문제 풀이 1. 분할 정복법이란? 분할 정복 :Divide and Conquer 작은 문제로 분할하여 문제를 해결하는 방법 헝가리 출신 미국인 수학자인 폰 노이만이 병합 정렬을 통해 분할 정복을 설명한 것은 1945년이다. 엄청나게 큰 문제를 조금씩 나눠가면서 풀기 용이한 문제로 나눈 다음 다시 합쳐서 해결하자는 개념에서 출발하였다. 2. 분할 정복법의 속성 분할 정복법은 상단에서 분할하고 중앙에서 정복하고 하단에서 조합하는 형태로 도식화할 수 있다. 분할: 문제를 동일한 유형의 여러 하위 문제로 나눈다. 정복: 가장 작은 단위의 하위 문제를 해결하여 정복한다.. 너비 우선 탐색(BFS, Breadth First Search) 너비 우선 탐색(Breadth First Search) breadth: 폭, 너비(=width)(->length) 그래프 전체를 탐색하는 방법 중 깊이 있게 먼저 탐색하는 DFS와 달리 깊이가 같은 너비를 먼저 탐색하는 BFS BFS의 정의 BFS의 특징 BFS와 DFS 과정 비교 BFS 구현 BFS 문제 풀이 BFS의 개념 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법. 시작 정점으로 부터 가까운 정점(height가 낮은 곳부터)을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회함으로써 노드를 넓게(wide) 탐색한다. BFS는 두 노드 사이의 최소 경로를 구하는 성질이 있어, 주로 '최단 경로', '최소 몇 번', '최소 이동 횟수', '최소 연산 횟수.. 비트마스크(BitMask) 비트마스크를 활용한 테크닉과 기법 비트마스크 자체는 알고리즘이 아니지만 다른 알고리즘과 같이 사용되어 어렵게 느껴질 수가 있다. 비트마스크(BitMask) 정수를 이진수 형태로 표현하여 비트연산을 활용하는 방법 이를 활용하면 비트연산을 통해 삽입,삭제,조회 등이 간단해짐 시간복잡도 O(1)으로 더 빠른 연산이 가능 메모리를 적게 사용함 비트 연산 AND (&) OR (|) XOR (^) SHIFT (>>,> n; for (int i = 0; i > a[i]; } for (int i = 0; i < (1 maps[i][j]; if (maps[i][j] == 'R') { r.first = i; r.second = j; } if (maps[i][j] == 'B') { b.firs.. 브루트 포스[1]:순열 (Brute Force[1]:Permutation) 암호학에서의 브루트 포스(brute force attack)가 아닌 알고리즘의 브루트 포스(brute force search)에 관한 것을 작성한다. 브루트 포스(brute force) brute: 무식한, force: 힘 무식한 힘으로 해석되며 즉, 무식하게 다해보는 것이다. 완전탐색 알고리즘: 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다. 이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다. 이러한 브루트 포스방법 중에서 순열에 관해서 소개를 하려고 한다. 순열(permutation) 수학에서, 순열 또는 치환은 서로 다른 n개의 원소에서 r(≤n)개를 뽑아 한 줄로 세우는 경우의 수이며, nPr로 나타낸다. 순서가 부여된 임의의 집합을 다른 순.. 자료구조 : 문자열 1. 문자열의 정의 스트링(string)이라고도 한다. 이러한 기호는 미리 정의된 집합이나 음소 문자에서 선택한다. 프로그래밍에서 문자열은 일반적으로, 요소가 문자 인코딩과 관련된 문자를 대표하는 일련의 자료값을 저장하고 있는 자료형으로 이해할 수 있다. 여기서 문자 인코딩의 경우 더 일반적인 배열 자료형과 차이가 있다. 이러한 환경에서 'binary string'과 'byte string'이라는 용어는 저장된 자료가 반드시 텍스트를 표시하지 않아도 되는 문자열을 표시하는 데 사용된다. 문자열 자료형으로 선언된 변수의 경우, 미리 정의된 어느 정도의 기호를 소유할 수 있는 메모리에 기억 자료를 할당하는 것이 보통이다. 문자열이 소스 코드에 보이면 그 문자열을 string literal이라고 일컫는다. 대.. 자료구조 : 덱(deque) 1. 덱의 정의 덱(deque, double-ended queue)은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조의 한 형태이다. 두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생 시킬 수 있다. 큐와 스택을 합친 형태로 생각할 수 있다. 양 끝에서만 데이터를 넣고 양 끝에서 뺄 수 있는 자료구조 2. 덱의 함수 push_front : 덱의 앞에 데이터를 넣음 push_back : 덱의 뒤에 데이터를 넣음 pop_front : 덱의 앞에서 데이터를 뺌 pop_back : 덱의 뒤에서 데이터를 뻼 front : 덱의 가장 앞에 있는 데이터 back : 덱의 가장 뒤에 있는 데이터 3.덱의 구현 스택과 큐를 합친것과 같음 4.덱 관련 문제 풀이 백준 10866번 덱 : https://www.ac.. 자료구조 : 큐(queue) 1. 큐의 정의 큐(queue)는 먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out)구조로 저장하는 형식을 말한다. 영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다. 한쪽 끝에서만 데이터를 넣고 다른 한쪽 끝에서만 데이터를 뺄 수 있다. 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다. 2. 큐의 함수 push : 큐에 자료를 넣음 pop : 큐에서 자료를 뺌 front : 큐의 가장 앞에 있는 자료 back : 큐의 가장 뒤에 있는 자료 empty : 큐가 비어있는지 아닌지 size : 큐에 저장되어있는 데이터의 개수 C++의 경우 STL의 queue,.. 이전 1 2 다음
