알고리즘/백준 문제풀이

문제 링크 : https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 인접 리스트 방식으로 그래프를 표현했다. 오랜만에 알고리즘 하려니 엄청 어색하네. #include #include #include using namespace std; vectoradj[1001]; bool vis[1001]; int main() { ios::sync_with_stdio(0); cin.tie(0); in..

[C/C++]백준 번 - 문제 링크 : https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 접근방식 일반적인 BFS문제. 백준 4179문제와 푸는 방식이 동일하다. 코드 #include using namespace std; #define X first #define Y second string board[1002]; int dist1[1002][1002]; //불 int dist2[1002][1002]; //상근 int dx[4] = {-1,0,1,0}; in..

문제 링크 : https://www.acmicpc.net/problem/10807 10807번: 개수 세기 첫째 줄에 정수의 개수 N(1 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 정수가 공백으로 구분되어져있다. 셋째 줄에는 찾으려고 하는 정수 v가 주어진다. 입력으로 주어지는 정수와 v는 -100보다 크거 www.acmicpc.net 접근방식 2가지 풀이를 생각해 볼 수 있다. 1번째) 그냥 단순하게 배열을 처음부터 순회하면서 정수v의 개수를 확인하는 방법. 2번째) 배열의 저장공간을 좀 더 써서 입력받은 정수들을 배열의 대응되는 인덱스의 값을 1씩 증가시키는 방식. 2번째 방법에는 좀 변형이 필요하다. v의 구간때문이다. (-100

문제 링크 : https://www.acmicpc.net/problem/2490 2490번: 윷놀이 우리나라 고유의 윷놀이는 네 개의 윷짝을 던져서 배(0)와 등(1)이 나오는 숫자를 세어 도, 개, 걸, 윷, 모를 결정한다. 네 개 윷짝을 던져서 나온 각 윷짝의 배 혹은 등 정보가 주어질 때 도(배 한 www.acmicpc.net 접근방식 0과 1의 개수를 저장할 배열을 선언해서 배열의 0의 개수를 확인 후 결과를 출력. 코드 #include int arr[2]; int main() { int number; for (int k = 0; k < 3; k++) { arr[0] = 0; arr[1] = 0; for (int i = 0; i < 4; i++) { scanf("%d", &number); arr[..

문제 링크 : https://www.acmicpc.net/problem/2752 2752번: 세수정렬 숫자 세 개가 주어진다. 이 숫자는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 이 숫자는 모두 다르다. www.acmicpc.net 접근방식 입력이 3개 밖에 없어서 간단하게 버블 정렬을 이용. 코드 #include using namespace std; int arr[3]; void bubbleSort() { int tmp; for (int i = 0; i arr[j]) { tmp = arr[j]; arr[j] = arr[i]; arr[i] = tmp; } } } } int main()..

문제 링크 : https://www.acmicpc.net/problem/10808 10808번: 알파벳 개수 단어에 포함되어 있는 a의 개수, b의 개수, …, z의 개수를 공백으로 구분해서 출력한다. www.acmicpc.net 접근방식 알파벳의 개수를 세기 위한 배열을 선언 후에 단어를 구성하는 알파벳을 하나씩 확인한 후에 알파벳의 대응되는 인덱스 값의 위치를 1씩 증가시킨다. 그렇게 하면 O(n) 시간이 걸린다. 시간 복잡도 O(n) 코드 #include using namespace std; string arr; int alphabet[26] = { 0, }; //알파벳 개수를 저장하기 위한 배열 int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> ..

문제 링크 : https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 문제 색종이 수를 세는 문제. 자세한 내용은 위의 링크를 참고. 접근방식 쿼드 트리 문제와 똑같은 문제다. base case에서 1인 경우 파란색 색종이 변수의 수를 1 증가시키고, 0인 경우에는 하얀색 색종이 변수의 수를 1증가 시키면 된다. 단, 입력에 공백이 있어서 char이 아닌 int형 배열을 이용했다. 코드 #include int paper[12..

문제 링크 : https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 문제 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다. 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있..