Do you believe in you?

[문제] 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net [설명] ★이 문제가 DP 인 이유: 현재 값을 구할 때 이전 결과값을 이용할 수 있는 모양이 나오기 때문 포도주가 1잔 일 때, 1잔 모두를 선택해야 최대이다. 포도주가 2잔 일 때, 2잔 모두를 선택해야 최대이다. 포도주가 3잔 일 때, 3번째 잔을 선택할 경우와 선택하지 않을 경우로 나눌 수 있다. 이 때, 3번째 잔을 선택하지 않을 경우는 포도주가 2잔 이었을 때 구한 최대값과 같다. 3번째 잔을 선택했다면, 2번째 잔을 선택하고 1번째 잔을 선택..

백트래킹(Back Tracking) - 완전 탐색에서 불필요한 분기(Branch)를 가지치기(Pruning) - 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법 즉, Backtracking이란, 간단하게 말해 brute-force(전부 일일히 다 해보는 것)방법을 수행하지만 한정 함수(bounding function)을 이용해 경우의 수를 줄여나가는 방법을 말한다. [관련문제] 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net [풀이] 1차원 행열 int queen_col[15] 을 이용해서 퀸의 위..

2차원 행열을 2차원 벡터를 활용해서 표현해보고, 그 값을 초기화해보자. vector visited_map(4, vector(3, false)); 뜻은 2차원 행열과 같은 역할을 하는 4 X 3 짜리 2차원 벡터를 생성과 동시에 false로 초기화한다는 말이다. 그럼 아래와 같은 데이터 공간이 만들어지게찌~ false false false false false false false false false false false false 참고로 1차원 벡터의 생성과 초기화는 다음 구문으로 표현할 수 있다. vector v(4,0); 뜻은 4열짜리 벡터를 만들고 0으로 초기화 해준다는 말~ 0 0 0 0 #2차원 벡터 동적할당 및 해제 방법! #include int main(){ //동적할당 생성 vector..

▶ 다익스트라(Dijkstra) 알고리즘이란? 다이나믹 프로그래밍(DP)를 활용한 최단 경로(Shortest Path) 탐색 알고리즘. 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 구현은 Greedy 알고리즘이나 DP 알고리즘을 사용하는데, Greedy 알고리즘을 사용할 수 있는 이유는 인접한 노드들 중 가장 작은 비용을 갖고 있는 노드를 선택하여 탐색을 진행하기 때문이다. DP 알고리즘을 활용할 수 있는 이유는 "최단 거리는 여러 개의 최단 거리들"로 이루어져있기 때문이다. (최단 거리 = 최단 거리 정보들의 합) 위의 그림은 a(1)와 b(5)사이의 최단 경로를 찾는 다익스트라 알고리즘의 흐름을 보여준다. 가장 낮은 값을 가진 방문하지 않은 꼭짓점을 선택하고, 방문하지 않은 각 인..

1. SELECT(검색) 1) 테이블의 특정 칼럼을 불러올 때 SELECT 칼럼명 FROM 테이블명; 여러 개의 칼럼을 불러올 때는 콤마(,)를 사용한다. SELECT 칼럼명1, 칼럼명2, 칼럼명3 FROM 테이블명; 모든 칼럼은 * 기호 사용 SELECT * FROM 테이블명; AS 구문을 사용하여 별명(새로운 이름)을 붙일 수 있다. SELECT 칼럼1 AS 별명1 FROM 테이블명; 중복을 제외하고 가져오고 싶을 때는 DISTINCT 연산자를 쓴다. 데이터는 오름차순으로 정렬된다. SELECT DISTINCT 칼럼명 FROM 테이블명; 2) 특정 조건을 만족하는 칼럼을 불러올 때 SELECT 칼럼명 FROM 테이블명 WHERE 칼럼명 = 값; /*조건비교는 =, !=, , =, IS NULL 등이 ..

=> map과 unordered_map의 차이는 구현방식이다. map은 균형 이진트리(Red-black tree)로 구현되고, unordered_map(hash_map)은 hash 방식(hash table)으로 구현된다. 즉, map에 들어가는 element 들은 key에 따라 정렬되어 저장되고, unordered_map은 key의 hash값에 따라서 저장된다. => 데이터가 적은 경우는 map > unordered_map, 데이터가 많은 경우는 map < unordered_map 성능이 더 좋다. map의 데이터들은 정렬되어 저장되므로 O(logN)의 탐색 속도를 보장하고, key값으로 탐색하는 unordered_map의 경우 O(1)의 탐색속도를 갖기 때문이다. 참고로 map의 경우 데이터 추가, 삭..

#1. 데이터 형식의 구분 - string: 1) 사용하기: string str = ""; (#include 헤더를 써줘야 사용가능하다. "" 큰 따옴표 사용!) 2) 입력받기: cin>>str; 로 하고 공백이 포함된 문자열이 저장된다. 3) 크기 구하기: str.size() 혹은 str.length(); 로 구할 수 있다. 4) 출력: cout charater; 하면 한글자씩 char형 배열에 저장된다. 반복문으로 공백 전까지 입력받을 수도 있다. 3) 크기 구하기: strlen(character); 로 구할 수 있다. 4) 출력: cout

▶ DP(Dynamic Programming)? : 큰 문제를 작은 문제로 나눠서 푸는 알고리즘. : 분할정복 알고리즘과 비슷. 분할정복은 작은 문제가 한 번씩 나오지만, DP는 작은 문제가 여러번 반복되어 나온다는 차이가 있다. [DP의 특징 2가지] 1) Overlapping Subproblem: 부분 문제가 겹친다. 2) Optimal Substructure: 최적 부분 구조를 가진다. * Overlapping Subproblem? Overlapping Subproblem의 대표적인 예로 피보나치 수를 구하는 방법을 들어보자. 피보나치 수는 다음과 같이 표현할 수 있다. F0 = 0 F1 = 1 Fn = Fn-1 + Fn-2(n>=2) => 0, 1, 1, 2, 3, 5, 8, 13, ... 위의 ..

보통 1억 번의 연산을 하는 데에 1초가 걸린다. 문제에서 제한시간이 1초로 주어졌을 때, 최대 연산 횟수가 1억 번을 넘지 않는지 확인해야 한다. 1. Big-O 표기법 1단계: 수행되는 연산(산술, 비교, 대입 등)의 개수를 대략적으로 판단한다. public int Add(int N){ return N + N; } => 대입하는 1번의 연산 public int Add2(int N){ int sum = 0; for(int i = 0; i N(for문) + 1(sum에 0을 대입하는 연산) 번의 연산 public int Add3(int N){ int sum = 0; for(int i = 0; i N) 3. Big-O 표기법 크기 비교 O(1) < O(logN) < O(N) < O(NlogN) < O(N²)

[문제 설명] 다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다. (), [], {} 는 모두 올바른 괄호 문자열입니다. 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다. 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다. 대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 retur..