문제 https://www.acmicpc.net/problem/13265 13265번: 색칠하기 각 테스트 케이스에 대해서 possible 이나 impossible 을 출력한다. 2 가지 색상으로 색칠이 가능하면 possible. 불가능하면 impossible 이다. www.acmicpc.net 그래프를 2가지 색으로 색칠하는 문제였는데, 서로 연결된 두 노드를 다른 색으로 칠할 수 있는지의 여부를 구하는 문제였다. 문제 풀이 그래프를 만들고 dfs로 모든 노드를 탐색하면서 색을 바꿔주면서 풀었다. dfs 현재 노드가 아직 색칠이 되지 않았으면 1로 색칠해준다. 현재 노드와 연결된 노드들을 탐색한다 다음 노드의 색이 없으면 방문 전이기 때문에 현재 노드 색과 다른 색으로 칠해주고 방문한다. 다음 노드의 ..
문제 https://www.acmicpc.net/problem/14629 14629번: 숫자 조각 곧 7살을 맞이하는 준하는 유치원에서 숫자가 적힌 나무 조각들을 가지고 노는 것을 좋아한다. 숫자 조각은 총 10개이며, 각각의 조각엔 0부터 9까지의 숫자가 한 숫자씩 적혀있다. 준하는 각 숫 www.acmicpc.net 준하가 수포자가 되지 않도록 0~9까지의 숫자를 한 번만 사용해 입력받은 숫자 N과 가장 차이가 적은 숫자를 구하는 문제였다. 문제 풀이 그리디로 풀면 될 것 같아서 그리디로 풀었다. 근데 백트래킹으로 푸는게 정신 건강에 더 좋을 것 같다. 처음에는 long long으로 N을 입력받고, int 배열에 각 자리를 저장해줬었다. 문제를 풀다가 string으로 받게 하는게 더 간단한 것 같아서..
문제 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 파이프를 맵의 마지막 위치로 옮길 수 있는 경우의 수를 구하는 문제였다. 문제 풀이 dfs로 완전탐색을 해서 풀 수 있었다. 처음 풀이 (고쳐서 맞추긴함) 문제를 풀다 시행착오가 2번 정도 있었다; 처음엔 문제를 제대로 읽지 않고 항상 3방향으로 갈 수 있는 상황이라 생각하고 풀어서 테케가 다 맞지 않았다. 그 다음에는 lx,ly,rx,ry를 넘겨 pipeDir를 구..
문제 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 서로 붙어있지 않은 스티커를 골라 가장 높은 점수를 구하는 문제였다. 문제 풀이 N이 100000이라 완전탐색으로 풀면 시간 초과가 날 것 같아서 dp로 풀었다. 처음에 예시만 보고 점화식을 만들어 풀었더니 틀렸다고 나와서 반례를 찾아 점화식을 수정했다. 0 : 50 1 : 100 50+50 vs 10 -> 100 2 : 200 100+100 vs 50+70 -> 200 3 : 2..
문제 https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 필요한 감독관 수의 최솟값을 구하는 문제였다. 문제 풀이 각각의 시험장에 총감독관은 오직 1명만 있어야 하고, 부감독관은 여러 명 있어도 된다. 이 문구에서 나는 총감독관은 1명까지 있을 수 있으니 0명도 괜찮다고 이해하고 풀어서 예제 케이스가 다른 값이 나왔다. 예제 케이스를 풀기 위해서는 총감독관은 항상 1명씩 있어야 한다. 해당하..
문제 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 주어진 트리를 전위, 중위, 후위 순회하는 문제였다. 문제 풀이 재귀함수를 이용해 해결했다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include using namespace std; pair G[27];//최대 노드 수 26 int N; int is..
문제 https://www.acmicpc.net/problem/1259 1259번: 팰린드롬수 입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 1 이상 99999 이하의 정수가 주어진다. 입력의 마지막 줄에는 0이 주어지며, 이 줄은 문제에 포함되지 않는다. www.acmicpc.net 팰린드롬 수인지 아닌지 확인하는 문제였다. 문제 풀이 정수를 문자열로 입력받았고 left와 right를 옮기면서 동일한지 확인해줬다. 만약 다르다면 팰린드롬 수가 아닌것으로 판단했다. 최근에 골드 문제만 풀다가 브론즈 문제를 푸니까 너무 쉽고 좋다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include using namesp..
문제 https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net string 배열을 길이순, 사전순으로 정렬하는 문제였다. 문제 풀이 사실 c++을 사용하면서도 string은 잘 사용하지 않고 char 배열을 많이 사용했는데, 확실히 string이 더 편하긴 하다. 앞으로는 string을 적극 사용해야겠다. string 사전순으로 비교할 때 >로만 비교할 수 있는게 충격적이다. 조건이 2개 이상일 경우 compare 함수를 커스텀하는 것도 처음..
