문제 https://www.acmicpc.net/problem/20924 20924번: 트리의 기둥과 가지 첫 번째 줄에는 노드의 개수 $N$($1 \le N \le 200\,000$)과 루트 노드의 번호 $R$($1 \le R \le N$)이 주어진다. 이후 $N-1$개의 줄에 세 개의 정수 $a$, $b$, $d$($1 \le a, b \le N$, $ a \ne b$)가 주어진다. 이는 $a$번 www.acmicpc.net 트리의 기둥 길이(루트~기가)와 가장 긴 가지의 길이(기가~리프)를 구하는 문제였다. 문제 풀이 처음에는 단순하게 size가 2보다 작은 노드가 나올 때까지 dfs를 돌려 기가 노드를 구하고, 기가 노드에서부터 각 노드들까지 dfs를 돌려 가장 긴 가지의 길이를 구하려고 했다. ..
문제 https://www.acmicpc.net/problem/22251 22251번: 빌런 호석 LED를 2개까지 바꿀 수 있을 때, 5층에서 3층, 6층, 8층, 그리고 9층으로 바꿔버릴 수 있다. www.acmicpc.net 치르보기 빌딩의 엘리베이터 디스플레이의 숫자를 변경할 수 있는 경우의 수를 계산하는 문제였다. 아래는 각각의 숫자가 보이는 방식이다. 문제 풀이 0~9까지의 숫자들의 7개의 표시등을 모두 저장하고 각각의 숫자가 다른 숫자로 바뀔 때 필요한 반전 횟수를 계산해 저장했다. 그리고 숫자를 변경할 때 K자리의 LED이기 때문에 12라는 숫자를 0012라고 표기해야 하기 때문에 string 으로 변환해준 후, 백트래킹을 하며 앞자리부터 계속해서 바꿔줬다. 처음에 아무리 생각해도 로직상 ..
문제 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 주어진 맵에서 각각의 테트로미노를 회전, 대칭해서 최댓값을 찾는 문제였다. 문제 풀이 500x500의 맵이고 회전과 대칭을 한 테트로미노의 총 개수가 19개였다. 대략 5,000,000 정도가 나왔고, 각각의 합을 더해줄 때 각 테트로미노마다 4번의 연산이 필요하기 때문에 20,000,000 정도가 나왔다. 제한 시간이 2초로 아주 넉넉했기 때문에 완전 탐색으로 풀었다. 처음에는 회전하는 메..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/12927# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 야근을 하고 남은 일의 제곱의 합의 최솟값을 구하는 문제였다. 문제 풀이 남은 일의 제곱의 합을 구해야 하기 때문에 큰 수를 최대한 줄여야 했다. 만약 works가 [10, 10, 8, 6, 4]가 있고 N이 5라면 합이 최소가 되기 위해서는 일을 한 결과가 [8,8,7,6,4]가 되어야 한다. 이렇게 하기 위해서 먼저 works를 내림차순으로 정렬했고, N만큼 반복하면서 현재 work에서..
문제 https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net 왼쪽부터 계산하는 수식에 괄호를 추가해 식의 최댓값을 구하는 문제였다. 문제 풀이 처음에 이 문제를 굳이 그리디로 풀려고 시도하다가 조건이 너무 많아져서 실패했다. 그냥 dfs로 푸니까 쉽게 해결됐다.. dfs를 할 때, 다음 연산을 바로 하는 경우와 다음 숫자와 다다음 숫자가 다다음 연산을 먼저 하는 경우로 나뉘게 하면 된다. #define _CRT_SECURE_NO_WAR..
문제 https://www.acmicpc.net/problem/16926 16926번: 배열 돌리기 1 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net 크기가 NxM인 배열을 한 줄씩 나눠서 R번 회전한 결과를 출력하는 문제였다. 문제 풀이 배열이 최대 300 x 300 크기고, 돌리는 횟수도 최대 1000번이라 실제로 다 돌려도 최대 90000000이어서 아슬아슬하게 제한 시간을 통과할 수는 있을 것 같았다. 하지만 다른 방법을 이용해 풀었다. ..
문제 https://www.acmicpc.net/problem/22234 22234번: 가희와 은행 가희는 창구가 하나인 은행을 운영하고 있습니다. 가희의 은행이 영업을 시작했을 때, 대기 줄에는 손님이 N명 있습니다. [그림 1] 카운터 직원과 N명의 손님 x번 손님에 대한 정보는 x번 손님의 www.acmicpc.net 1초마다 현재 처리하고 있는 고객의 id를 출력하는 문제였다. 손님들은 순서대로 줄을 서 있으며 한 번에 한 손님에게 할당할 수 있는 시간이 정해져있다. 할당된 시간이 끝나면 시간이 남은 손님일 경우에는 줄의 맨 뒤로 간다. 문제 풀이 queue를 이용해 풀 수 있었는데, 이때 queue에 넣는 순서가 중요하다. 영업 이후에 들어온 손님은 들어온 시간까지 알아야 하기 때문에 구조체를 ..
문제 https://www.acmicpc.net/problem/23747 23747번: 와드 와드를 설치하지는 않았지만, 한별이의 최종 위치의 위, 아래, 왼쪽, 오른쪽 칸은 시야로 확보하고 있다. 지나온 경로를 모두 시야로 확보하지는 않는다. www.acmicpc.net 여행 기록을 입력받아 맵에서 이동하고, 기록이 W일 경우에 같은 구역의 시야를 밝힌 후 모든 여행이 끝난 후의 맵의 시야를 출력하는 문제였다. 문제 풀이 입력받은 방향대로 이동하다가 W가 나오면 dfs를 호출해 같은 구역(같은 문자)인 곳을 탐색해줬다. 마지막에 이동한 곳과 그 위치의 상하좌우까지 방문처리 해준 후, isVisit 값이 true면 .을 false면 #을 출력했다. #define _CRT_SECURE_NO_WARNINGS..
