본문 바로가기

전체 글282

3745. 오름세 (Python) 3745번: 오름세 입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 주가를 관찰한 날의 수 N (N ≤ 100000)이 주어진다. 둘째 줄에는 관찰한 주가가 첫 날부터 순서대로 주어진다. www.acmicpc.net 풀이 간단하게 최장 증가 부분 수열(Longest Increasing Subsequence, LIS)을 활용하여 해결하는 문제이다. 문제 알고리즘 자체는 어려울게 없으나 입력에 따로 종료하는 부분이 주어지지 않아 그 부분만 해결하면 된다. 파이썬에서는 try 구문을 사용하여 exception이 발생했을 때 입력이 종료되도록 해주면 된다. 코드 import sys from bisect import bisect_left input = sys.stdin.readli.. 2022. 3. 23.
1949. 우수 마을 (Python) 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 풀이 임의의 마을 하나를 루트 노드로 설정하여 해당 노드부터 리프 노드까지 탐색하면 된다. 코드에서 사용된 dp[n][flag]의 경우 flag가 0일 경우는 n번 마을을 우수 마을로 설정하지 않았을 때의 마을 주민 수의 최댓값이고 flag가 1일 경우는 n번 마을을 우수 마을로 설정했을 때의 마을 주민 수의 최댓값을 의미한다. 재귀 호출되는 함수의 경우 3개의 매개변수를 받게 되어있는데 node의 경우는 현재 마을 번호, parent의 경우는 현재 마.. 2022. 3. 22.
8980. 택배 (Python) 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 풀이 먼저 입력 받은 박스 정보를 받는 마을이 빠른 순으로 정렬해주고 받는 마을이 빠른 쪽에 최대한 많은 박스를 보낼 수 있도록 트럭에 실어주면 된다. boxInTruck이라는 배열을 사용하였는데 boxInTruck[i]의 뜻은 i번째 마을에서 현재 트럭에 실린 박스의 개수를 의미한다. 보내는 마을부터 받는 마을의 바로 이전 마을까지 트럭에 가장 많은 박스가 담겨 있는 경우와 비교했을 때 트럭에 박스를 더 실을 수 있을 경우 실을 수 있는 만.. 2022. 3. 21.
18430. 무기 공학 (Python) 18430번: 무기 공학 첫째 줄에는 길동이가 가지고 있는 나무 재료의 세로, 가로 크기를 의미하는 두 자연수 N, M이 주어진다. (1 ≤ N, M ≤ 5) 다음 N개의 줄에 걸쳐서, 매 줄마다 나무 재료의 각 위치의 강도를 나타내 www.acmicpc.net 풀이 백트래킹을 이용하여 해결할 수 있는 문제다. 함수를 호출할 때 받는 매개변수의 인덱스는 부메랑의 중심을 기준으로 한다. 위의 그림과 같은 4개의 부메랑 형태 각각을 만들 수 있는지 체크하여 만들 수 있을 경우 해당 부메랑의 강도의 합을 구하고 다음 인덱스로 넘겨 같은 과정을 반복한다. 마지막 인덱스를 벗어났을 경우 현재까지 구한 부메랑 강도의 합을 비교하여 최댓값을 가져오도록 구현하면 된다. 아래 코드에서 인덱스를 하나의 숫자로 바꾸어 사용.. 2022. 3. 19.
15591. MooTube (Silver) 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 풀이 bfs를 통해서 유사도를 탐색하도록 구현하여 해결할 수 있다. 질문이 주어지면 해당 동영상으로부터 bfs 탐색을 하여 각 동영상의 USADO를 구하여서 개수를 출력하도록 한다. 이때 질문에 중복된 동영상이 들어올때를 대비하여 플래그를 기록하는 리스트를 하나 만들어 동일한 동영상에 대한 bfs 탐색을 중복으로 하지 않도록 하였다. 코드 import sys input = sys.stdin.readline INF.. 2022. 3. 18.
15997. 승부 예측 (Python) 15997번: 승부 예측 첫 번째 줄에 조별리그를 진행할 국가명 네 개가 공백으로 구분되어 주어진다. 주어지는 모든 국가명은 알파벳 대문자로만 구성된 길이가 1 이상 10 이하인 문자열이다. 두 번째 줄부터 일곱 번 www.acmicpc.net 풀이 모든 경우의 수를 고려하여 dfs를 통해서 확률을 구하면 된다. 게임의 승패에 따른 각 나라의 승점을 기록하고 모든 경기가 끝났을 때 순위를 참고하여 확률을 더해주면 된다. 문제는 승점이 같은 나라가 있을 경우의 처리인데 문제에서 추첨으로 순위를 정한다고 하였다. 예를 들어 1위 승점이 9점이고 2위, 3위, 4위의 승점이 5점인 경우를 생각해 보자. 이 때, 1위는 문제 없이 진출할 수 있으므로 확률을 그대로 더해주면 되고 2위, 3위, 4위의 경우는 추첨.. 2022. 3. 15.
1405. 미친 로봇 (Python) 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 풀이 백트래킹을 활용해서 해결할 수 있는 문제다. 먼저 30 * 30 사이즈의 방문 체크 리스트를 만들고 로봇이 해당 리스트의 가운데에 위치해 있다고 가정한다. 그 후 동서남북으로 한 번씩 체크하여 방문하지 않은 위치에 해당하면 로봇을 해당 위치로 이동시키고 다시 함수를 호출한다. 동서남북으로 진행해 나갈때마다 해당 방향으로 이동할 확률을 곱해 나가 N번 이동을 마쳤을 때 구한 확률을 모두 더해준다. 만약 이동중에 이미 방문한 위치에 해당할 경우에는 함수를 .. 2022. 3. 15.
2616. 소형기관차 (Python) 2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있 www.acmicpc.net 풀이 구간합 개념과 dp를 사용하여 해결할 수 있다. dp 배열은 2차원 배열로 이루어져 있는데 의미는 다음과 같다. # dp[1][n]: n번째 객차까지 1개의 소형 기관차를 사용했을 때 운송할 수 있는 최대 손님 수 # dp[2][n]: n번째 객차까지 2개의 소형 기관차를 사용했을 때 운송할 수 있는 최대 손님 수 # dp[3][n]: n번째 객차까지 3개의 소형 기관차를 사용했을 때 운송할 수 있는 최대 손님 수 dp = [[0 for _ in ra.. 2022. 3. 13.
1655. 가운데를 말해요 (Python) 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 풀이 가운데를 기준으로 낮은쪽을 저장하는 힙(smallerNumbers)과 높은쪽을 저장하는 힙(biggerNumbers)을 사용하여 해결하였다. smallerNumbers의 경우는 최대힙을 사용하였고 biggerNumbers의 경우는 최소힙을 사용하였다. 이는 작은 숫자들중에서는 가장 큰 숫자(smallerRep)가 가운데에 올 수 있고 큰 숫자들중에서는 가장 작은 숫자(biggerRep)가 가운데에 올 수 있기 때문이다. smallerRep와.. 2022. 3. 12.

티스토리툴바