Do you believe in you?

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..

▷ 문제설명 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 0과 1로 이루어진 지도(1은 땅, 0은 바다)에서 섬의 개수를 탐색하는 문제 상, 하, 좌, 우, 대각선 방향에 땅이 있다면 섬으로 판단. 지도의 가로, 세로로 0 0이 입력될 때까지 지도 입력과 정답 출력을 반복한다. ▷ 문제풀이 지도좌표 (0, 0)에서 부터 현재 위치가 땅인지 판단하고 땅이면 탐색을 시작한다. 탐색은 상, 하, 좌, 우, 대각선을 체크하여 지도 범위내이고 1로 연결되어 있는 곳만 탐색한다. 좌표만 옮겨서 탐색을 반복하므로..

▷ 문제설명 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 주어진 암호를 만들 수 있는 문자열 L 개에서 C개를 골라서(순열) 오름차순으로 출력하는 문제. 단, 암호는 모음의 개수는 1개 이상이고 자음의 개수는 2개 이상인 문자로 이루어져 있다. ▷ 문제풀이 순열문제 이므로 재귀함수를 이용한 DFS 방법으로 풀이할 수 있습니다. [ 변수 설명 ] vector alpha; 알파벳의 개수만큼 쉽게 입력받기 위해 vector 자료구조 사용(동적할당) string answer_arr = ""; 정답 출력을 쉽게 하기 위..