문제https://www.acmicpc.net/problem/26086 26086번: 어려운 스케줄링첫째 줄에 업무의 고유번호의 범위 제한 $N$과 명령 횟수 $Q$, $k$가 주어진다. ($1\leq N,Q \leq 100\,000,\ 1\leq k \leq$ '0번 명령의 등장 횟수') 둘째 줄부터 $Q$개 줄에 걸쳐 명령에 대한 정보가 주어진다.www.acmicpc.netstack 구조의 스케쥴러를 이용해 명령을 수행하고 k번째로 처리할 업무를 찾는 문제였다. 명령은 다음과 같다.0 p : 스케줄러의 맨 앞에 번호 p인 업무를 추가한다.1 : 스케줄러의 업무를 p 기준으로 오름차순 정렬한다.2 : 스케줄러의 업무 처리 순서를 뒤집는다.명령 횟수는 100000, 시간 제한은 1초였다. 문제 풀이명령 ..
문제 https://www.acmicpc.net/problem/24461 24461번: 그래프의 줄기 그래프에서 사이클이란, 한 정점에서 같은 정점까지, 반복되는 간선이 없으며, 길이가 $0$이 아닌 경로이다. 사이클이 존재하지 않는 그래프가 주어진다. 우리는 이 그래프의 정점 중에서 연결된 www.acmicpc.net 가장자리 정점을 '동시에' 없애는 행동을 가장자리 정점이 2개 이하로 남을 때까지, 즉 일직선이 될 때까지 반복하고 남은 일직선의 정점을 오름차순으로 출력하는 문제였다. 문제 풀이 그래프를 생성하면서 in, out 배열을 만든다. 초기 가장자리 정점 queue를 생성한다. in, out이 모두 1인 정점이 가장자리 정점이 된다. 가장자리 정점 제거 queue에 담긴 정점을 제거한다. 제거..
문제 https://www.acmicpc.net/problem/12764 12764번: 싸지방에 간 준하 첫째 줄에 사람의 수를 나타내는 \(N\)이 주어진다. \((1 \le N \le 100,000)\) 둘째 줄부터 \(N\)개의 줄에 걸쳐서 각 사람의 컴퓨터 이용 시작 시각 \(P\)와 종료 시각 \(Q\)가 주어진다. \((0 \le P \lt Q \le 1,000 www.acmicpc.net 모든 사람은 비어있는 자리 중 번호가 가장 작은 자리에 앉아야 한다. 다음과 같은 이용 규칙으로 모든 사람이 기다리지 않는 컴퓨터의 최소 개수와 자리별로 몇 명의 사람이 사용했는가를 구하는 문제였다. 문제 풀이 처음에 비어있는 자리 중 번호가 가장 작은 자리에 앉는다는 규칙을 제대로 보지 않아서 틀렸었다. ..
문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 아기상어가 최대 몇 초 동안 물고기를 먹을 수 있는지 구하는 문제였다. 문제의 조건은 다음과 같았다. 아기상어는 크기가 작은 물고기만 먹을 수 있다. 크기가 같은 물고기일 경우 지나갈 수 있다. 먹을 수 있는 물고기 1마리 → 먹으러 감 먹을 수 있는 물고기 2마리 이상 → 거리 가장 가까운 물고기 거리 : 지나야 하는 칸 개수 최솟값 가까운 물고기가 많으면 가장 위, 위인 물고기도 ..
문제 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 1초마다 먼지가 확산되고 공기청정기가 가동되는 상황에서 T초 후의 방 안에 남은 먼지 개수를 구하는 문제였다. 문제 풀이 문제에서 요구하는 대로 구현하기만 하면 되는 문제였다. 1초마다 먼지가 확산되는 메서드와 공기청정기가 가동되는 메서드를 실행시키고, T초가 끝난 후에 map에 있는 먼지를 다 더해준 것이 답이었다. #define _CRT_SECURE_NO_WARNINGS #include..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/258707 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 카드 게임을 진행해서 게임에서 도달 가능한 최대 라운드 수를 구하는 문제였다. 문제 풀이 게임을 진행하면서 카드를 살 수 있는 경우에 바로 사거나 보류하도록 했다. 각 카드의 상대 숫자의 라운드가 0일 때는 코인이 1개가 필요하고, 현재 라운드보다 작거나 같을 때에는 코인이 2개가 필요하다. 상대 카드가 현재 라운드보다 큰 라운드에 위치해 있다면 아직 살 수 없다. coin 1개 필요 ->..
문제 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에서..
