Do you believe in you?

#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 = ""; 정답 출력을 쉽게 하기 위..

▷ 문제설명 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 집이 있는 곳은 1, 집이 없는 곳은 0으로 표현된 지도정보(정사각형)를 주고, 단지의 수와 각 단지 내 집의 수를 오름차순으로 출력하는 문제 조건) 연결된 집들은 상하좌우에 있는 집이다. 대각선 X. 지도의 크기 N은 5 map_size; for (int i = 0; i < map_size; i++) { for (int j = 0; j < map_size; j++) { scanf_s("%1d", &map[i][j]); // 공백없는 숫자를 한줄씩 입..

★ BFS/DFS 탐색의 목적 : 시작점 X에서 시작해서 모든 정점을 한 번씩 방문하는 것. 1. DFS(깊이 우선 탐색) Stack(후입선출) 과 재귀함수 사용 : 한 시작점에서 갈 수 있을 때까지 계속해서 진행. 더 이상 진행할 수 없을 때 이전으로 돌아와서 다시 갈 수 있을 때까지 진행 : 방문했는 지, 안했는 지를 체크할 visited[] 배열 사용 i 1 2 3 4 5 6 visited[i] 0 0 0 0 0 0 1) 1 방문 stack 1 visited[1] = 1 대입 2) 1과 연결된 2, 5 중에 작은 값인 2 방문(정점 값이 작은 곳으로 이동) stack 1 2 visited[2] = 1 3) 2와 연결된 3, 5 중에 3 방문 stack 1 2 3 visited[3] = 1 3) 3과..

그래프란? : 자료구조의 일종 : 정점(Node, Vertex), 간선(Edge)로 구성 -> 간선이란? 정점과의 관계를 의미한다. : G=(V,E)로 나타낸다. 1. 그래프의 경로란? : 시작점->도착점으로 가는 간선의 연속 ex) 위의 그림으로 표현해보면 정점 2에서 1로 가는 경로는 아래 두 가지 이다. 2 -> 1 2 -> 3 -> 1 2. 사이클이란? : 시작점과 도착점이 모두 같은 경우. 즉, 출발한 정점으로 다시 되돌아오는 경우 2-1. 단순 경로와 단순 사이클? 단순하다는 건, 경로/사이클에서 같은 정점을 두 번 이상 방문하지 않는 경로/사이클을 의미한다. 즉, 특별한 말이 없으면 일반적으로 단순 경로/사이클을 의미한다는 것을 알아두자. 3. 방향이 있는 그래프? : 위 그림과 같이 A -..

vector와 array의 주소값을 전달해서 지역변수로 관리하는 방법 - vector를 함수의 인자로 전달하기 #include #include #include using namespace std; void tossVector(vector&); int main() { int N = 0, num = 0; vector v; //Input cin >> N; for (int i = 0; i > num; v.push_back(num); } tossVector(v); //Output for (int i = 0; i > arr[i]; } tossArr..