컴굥일지

문제 https://www.acmicpc.net/problem/2667 문제 내용 0은 집이 없는 곳, 1은 집이 있는 곳이다. 집들이 서로 이어져있으면 같은 단지에 속해있다. 단지의 개수를 출력하고, 각 단지에 포함된 집의 개수를 오름차순으로 정렬하여 출력하면 된다. 문제 풀이 bfs/dfs를 통해 문제를 풀 수 있다. (dfs로 풀었다.) 일단 dfs를 돌며, 서로 이어진 집끼리 단지 번호를 같게 하여 used배열에 추가한다. 모든 집에 대해 dfs 탐색이 끝나면, used배열에 있는 값을 카운트하여 출력하면 된다. 코드 #include #include #include using namespace std; int dr[4] = {1, -1, 0, 0}; int dc[4] = {0, 0, 1, -1};..

문제 https://www.acmicpc.net/problem/1992 문제 내용 배열을 입력받아 규칙대로 압축을 진행하면 된다. 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다 문제 풀이 재귀를 사용하여 문제를 해결할 수 있다. 먼저 범위에 해당되는 부분이 다 같은 수로 채워져 있는지를 체크하고, 그렇지 않으면 4등분으로 분할하여 각각에 대해 같은 과정을 거친다. 만약 다 같은 수로 채워져 있으면 결과에..

문제 https://www.acmicpc.net/problem/15903 문제 내용 입력받은 원소 n개짜리 배열에 대해, 아래 과정을 m번 수행하면 된다. 1. x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산한다. (x ≠ y) 2. 계산한 값을 x번 카드와 y번 카드 두 장 모두에 덮어 쓴다. m번의 과정이 모두 끝나고, 전체 원소의 합이 최소가 되도록 해야 한다. 문제 풀이 x와 y를 골라 두 값을 더해 카드를 덮어써야 한다. 즉, x와 y의 값은 기존과 같거나 커지게 된다. (값이 줄어드는 경우는 없다) 전체 합이 최소가 되게 하기 위해선, 매 과정마다 가장 작은 두 수를 x, y로 골라야 한다. 코드 #include #include using namespace std; in..

문제 https://www.acmicpc.net/problem/1780 문제 내용 아래 문제와 매우 유사한 문제이다. [BOJ/백준 2630][C++] 색종이 만들기 문제 https://www.acmicpc.net/problem/2630 문제 내용 주어진 입력에서 색종이 개수를 구하는 문제이다. 색종이는 정사각형+같은 색이어야 하며, n*n 크기의 종이가 전부 같은 색이 아니면 가로 세로를 반 gyong0117.tistory.com 1780 종이의 개수 문제 역시 색종이의 개수를 구하는 문제이다. 차이는 2630번은 매번 n/2가 되지만 이 문제는 n/3을 해야 한다는 점, 종이의 종류가 다르다는 점이다. 문제 풀이 역시나 재귀를 통해 문제를 풀면 된다. 먼저 종이가 다 같은 수로 채워져 있는지를 체크하..

문제 https://www.acmicpc.net/problem/14889 문제 내용 N명을 2개의 팀으로 나눈 후, 각 팀의 능력치를 구한다. 각 팀의 능력치 차가 최소가 되는 값을 구하면 된다. 이때 팀의 능력치는 팀에 속한 모든 쌍의 능력치의 합이다. (아래는 예시) 1,2번이 같은 팀이고 3,4번이 같은 팀일 때 (1,2)가 속한 팀의 능력치 = arr[1][2]+arr[2][1] (3,4)가 속한 팀의 능력치 = arr[3][4]+arr[4][3] 문제 풀이 이 문제에서 가장 중요한 부분은, 팀을 두 개로 나누는 것이다. 이 부분을 위해 백트래킹으로 문제를 풀었다. 사람은 1~n번으로 주어지고, 순서가 의미가 없기 때문에 N과 M (2)를 참고하면 좋을 것 같다. [BOJ/백준 15650][C++..

문제 https://www.acmicpc.net/problem/7562 문제 내용 각 테스트 케이스별로 체스판의 길이, 나이트의 현재 위치와 이동하려는 위치가 주어진다. 나이트가 최소로 이동하여 목적지까지 갔을 때, 몇 번의 이동이 필요한지 출력하면 된다. 문제 풀이 bfs를 통해 이 문제를 풀면 좋다. 체스판의 길이를 len이라 했을 때 len*len 배열을 선언하고, 초기 위치부터 bfs를 돌리면 된다. 초기 위치의 값을 1로 하고, 해당 위치로부터 갈 수 있는 곳을 +1 하여 배열에 저장하는 방식으로 문제를 풀었다. 그렇게 하면 목적지에 해당하는 arr배열의 값-1 이 구하고자 하는 값이 된다. (시작을 1로 세팅했기 때문에 -1 필요) 나이트가 이동할 수 있는 위치는 문제에 주어진 것처럼 8개이다..

문제 https://www.acmicpc.net/problem/7562 문제 내용 각 테스트케이스 별로, k개의 숫자를 입력받아 그중에서 6개를 골라 수열을 만들면 되는 문제이다. k개의 숫자는 오름차순으로 주어진다. 문제 풀이 N과 M문제와 많이 비슷한 유형으로, 백트래킹으로 풀면 되는 문제이다. 입력의 마지막이 0으로 주어진다는 점을 잘 처리하는게 중요한 부분이고, 이외에는 백트래킹 풀이와 똑같이 하면 된다. 코드 #include #include using namespace std; vector arr; vector result(6, 0); int k; void back(int cnt, int before) { if (cnt == 6) { for (int i = 0; i < 6; i++) { cout..

문제 https://www.acmicpc.net/problem/15666 문제 내용 입력받은 N개의 자연수 중에 M개를 골라 수열을 만들어 출력하면 된다. 이때 수열을 사전순으로 증가하는 순서대로 출력해야 하며, 수열이 중복되면 안 된다. 입력받은 N개의 자연수 중에 고르는 수는 서로 중복이어도 상관없으나, 비내림차순 수열이어야 한다 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 문제 풀이 N과 M (11)과 다르게 N과 M (12)는 수열이 비내림차순이어야 한다는 조건이 추가되었다. 따라서, N과 M (10)처럼 이전에 어떤 값을 선택했는지도 같이 인자로 넘겨주어야 한다. 또한, N과 M (11)처럼 원소의 중복을 허용하기 때문에 used 배열..

문제 https://www.acmicpc.net/problem/15665 문제 내용 입력받은 N개의 자연수 중에 M개를 골라 수열을 만들어 출력하면 된다. 수열을 사전순으로 증가하는 순서대로 출력해야 하며, 수열이 중복되면 안 된다. 이때 고르는 자연수는 서로 중복이어도 상관없다. 문제 풀이 N과 M (9)과 다르게 N과 M (11)는 수열의 원소가 중복이어도 된다는 조건이 추가되었다. 그렇기 때문에 굳이 used 배열로 사용 여부를 판단할 필요가 없다. [BOJ/백준 15663][C++] N과 M (9) 문제 https://www.acmicpc.net/problem/15663 문제 내용 입력받은 N개의 자연수 중에 M개를 골라 수열을 만들어 출력하면 된다. 이때 수열을 사전순으로 증가하는 순서대로 출력..

문제 https://www.acmicpc.net/problem/15664 문제 내용 입력받은 N개의 자연수 중에 M개를 골라 수열을 만들어 출력하면 된다. 이때 수열을 사전순으로 증가하는 순서대로 출력해야 하며, 수열은 비내림차순이어야 한다. 당연히 수열은 중복되어 출력되면 안 되지만, 입력으로 주어지는 원소 N개 사이에는 중복이 있을 수 있다. 문제 풀이 N과 M (9)과 다르게 N과 M (10)는 수열이 비내림차순이어야 한다는 조건이 추가되었다. N과 M (9)은 몇 개를 선택했는지만 인자로 넘겨서 종료조건을 체크하면 되었지만, N과 M (10)는 비내림차순 수열을 만들어야 하기 때문에, 이전에 어떤 값을 선택했었는지에 대한 정보도 넘겨주어야 한다. (값 자체가 아니라, 그 값의 인덱스를 넘겨준다.)..