https://www.acmicpc.net/problem/2563 2563번: 색종이 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 www.acmicpc.net 1. Logic 도화지의 사이즈가 최대 100*100이라고 했기 때문에 최악의 경우의 완탐을 돌아도 10000에 입력받는거까지 넉넉잡아도 1초안에는 무조건 계산이 가능하다. 처음 문제를 읽고 색종이의 갯수 n * 100에 중복 구간을 어떻게 빼줄까를 고민하다가 굳이 어렵게 생각해서 값을 빼주지 말고 그냥 한번만 세주면 되겠다는 생각을 했다. 입력 받은 좌표값에 +10까지 방문 처리를 해주고 갯수를 세..
Algorithm/Beakjoon
https://www.acmicpc.net/problem/2012 2012번: 등수 매기기 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다. www.acmicpc.net 1. Logic 자기가 예상한 등수랑 다르면 불만도가 생기기 때문에 자신의 예상 등수를 입력받은후 정렬한다. 테스트 케이스로 예를 들면 1 5 3 1 2 > 1 1 2 3 5 1 ~ 5등까지 나오기 때문에 작은것부터 숫자를 맞춰주면 된다. 코드를 보면 더 이해가 잘 갈것이다. 2. Code #include #include #include using namespace std; vector vec; int ..
https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 1. Logic 4등분을 해서 모든 칸이 일치하면 해당 칸의 번호를 출력하는 문제이다. 기본적인 분할 정복 문제이지만 출력을 할 때 한번 생각해야 되서 실버 1인듯?하다 기본적인 분할 정복 아이디어를 활용하여 풀이하면 되고, 출력은 분할하는 부분에서 즉 섞여있는 부분을 확인하려고 재귀를 들어갈 때 '('를 출력하고 들어가서 확인하고 나오면서 ')'를 출력해주면 된다. 2. Code #..
https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 1. Logic 대표적인 분할정복의 예제인 것 같다. N의 범위가 3^7이라고 했기 때문에 3^7=2187 넉넉잡아 배열의 크기를 2200으로 잡아줬다. 함수에 처음 들어가면 내가 지금 보고 있는 종이가 전부 같은 숫자로 이루어졌는지 확인 하고 하나라도 다르다면 다시 9등분으로 쪼개서 확인해 준다. 아래의 표는 코드의 주석과 대응되는 9등분 한 위치이다. 1 2 3 4 5 6 7 8 9..
https://www.acmicpc.net/problem/4779 4779번: 칸토어 집합 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다. 전체 집합이 유한이라고 가정하고, www.acmicpc.net 1. Logic 사이즈를 쪼개 들어가서 0일 떄 -를 출력하면 됨. 테스트 케이스를 보면 항상 n에서는 n-1의 모양이 두번 나온다. 그리고 사이 사이에는 3의 n제곱만큼 공백이 있다 분할 정복 공부할 때 처음 풀어보면 좋은 문제 같다. 2. Code #include #include #include #include using namespace std; void cantor(int n) { int ..
https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. Logic 재귀를 이해하고 있다면 쉽게 풀 수 있는 문제이다. 각 노드의 부모 노드를 순서대로 출력해야 하기 때문에 부모 노드를 저장하는 배열(check)에 저장해줬다. 양방향으로 입력을 받았기 때문에 반복되는 계산을 막아주기 위해 vis배열도 추가해줬다. 수정 > 원래는 vis배열에 넣어줬지만 check배열을 -1로 초기화 시켜준 다음 -1이 아니면 continue하도록 설계해주면 100001개짜리 배열 하나를 덜 써도 된다 2. Code #includ..
https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 1. Logic 처음에 이 문제를 딱 보고 위상정렬인줄 알았다. 하지만 위상정렬의 탈을 쓴 DP문제였고 결국 멘토한테 도움을 받았다. 내가 처음에 짠 코드는 동시에 진행하는 작업 중에 가장 시간이 오래 걸리는 작업의 시간이 고려되지 않을 수도 있는 코드였다. 그래서 이 문제는 위상정렬과 코드가 비슷하긴 하지만 DP로 풀이해야 한다. 2. Code #include using namespac..
https://www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 1. Logic 조건 그대로 구현하면 된다. 구현이 약간 까다롭지만 계란의 수 N의 크기가 8로 엄청 작기 때문에 브루트포스로 풀이할 수 있다는 것을 유추할 수 있다. 구조체를 사용하지 않고 내구도와 무게를 따로 저장하는 배열을 선언하여 풀이했다. 2. Code #include #include using namespace std; int n; int dura[10]; int weig..
https://www.acmicpc.net/problem/1431 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루어 www.acmicpc.net 1. Logic 각 조건에 따라 compare 함수를 커스텀해서 정렬하면 된다. 2. Code #include #include #include using namespace std; vector input; bool cmp(string a, string b) { //1번 조건 if(a.length() != b.length()) return a.length() < b.length(); //2번 ..
https://www.acmicpc.net/problem/11652 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net 1. Logic map을 사용해서 풀었다. 2. Code #include #include using namespace std; map m; int main() { long long ans = 0; long long n; cin >> n; while(n--) { long long a; cin >> a; m[a]++; ans = max(ans, m[a]); } for(auto &a : m) { ..
