Do you believe in you?

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

* C++ sort함수란? : C++STL에서 제공하는 sort 알고리즘 - 헤더파일: - 구문: sort(start, end); //start부터 end개를 오름차순(default)로 정렬한다. - 내부는 Quick sort(퀵 정렬)로 구현되어 있다. 따라서 평균 시간 복잡도는 O(NlogN)을 가진다. 1) 함수 원형 template void sort(T start, T end); template void sort(T start, T end, Compare comp); : 3번째 인자 값(Compare comp)을 넣으면 오름차순, 내림차순 등으로 정렬할 수 있다. compare 함수는 true 인 경우를 기준으로 정렬한다. 2) 배열(array) 사용할 때 예시 sort(arr, arr+n); /..

* 배열의 길이를 고정한다는 것과 동적할당한다는 것의 차이점은? - 고정배열(fixed array): 컴파일 타임에 배열의 길이를 정하는 것. - 동적배열(dynamically array): 런타임 동안에 배열의 길이를 정하는 것. * 동적할당을 위해 필요한 연산자: new[], delete[] * 배열의 길이를 동적으로 할당하고 값을 초기화시켜보자. #include int main(){ int length; cin >> length; int *array = new int[length]; //이렇게 하면 배열의 길이를 입력받은 length로 할당 가능 for(int i = 0; i> array[i]; } delete[] array;// 동적할당 시, 배열 할당한 메모리 꼭 해제해주기. return 0; ..