Do you believe in you?

▷ 문제설명 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; ..

▷ 문제설명 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하는 문제 이 때, n의 범위는 1 T; for (int t = 0; t > num; cout

14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net ▷ 문제설명 NxM 크기의 종이 위에 테트로미노를 하나 놓아서 놓인 칸에 쓰여 있는 수의 합을 최대로 하는 문제 N, M의 범위는 4 > N >> M; for (int i = 0; i > arr[i][j]; } } StartCalculation(arr, N, M); } void StartCalculation(int arr[SIZE][SIZE], int N, int M) { int ..

1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net ▷ 문제설명 준규가 사는 나라는 연도를 표현할 때 E, S, M 세 문자로 표현한다. 각각의 문자가 가지는 범위는 1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19 이다. E, S, M이 주어질 때, E S M으로 표시되는 가장 빠른 연도를 출력하자. ▷ 문제풀이 이 문제의 경우 표현할 수 있는 년도는 15 * 28 * 19 = 7980년까지 이므로 브루트포스 방법으로 1년 부터 7980년까지 구하다가 정답과 같아지는 순간을 찾으면 된다. 이 때, 문제에..

2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net ▷ 문제설명 찐 일곱난쟁이를 찾는 문제! 즉, 가짜 난쟁이 2명이 포함된 9명의 난쟁이 중에서 찐 일곱난쟁이를 찾아야 한다. 그리고 일곱난쟁이의 키를 오름차순으로 출력해야 한다. ▷ 문제풀이 1) 일곱 난쟁이의 키의 합이 100인 것과 순열의 성질을 이용한다. 2) 9명 중, 7명을 선택하는 방법이 아닌 2명의 난쟁이를 선택하는 경우를 구한다.(9C7 = 9C2) 3) 전체 키의 합에서 2명 키를 빼본다. 4) 그 값이 100이 된다면 그 둘이 가짜 난쟁이들이다. ▷ 시..