https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net # 2017년 상반기 삼성 SW 역량 테스트 기출문제이다. # DP문제치곤, 그렇게 어렵지 않았다. # N일부터 1일까지 앞으로 가며 dp테이블을 갱신하는 코드: 1. 우선 arr[i][0] + i (현재 일수 + 상담에 걸리는 일수)가 N보다 크면 상담을 못하므로 dp[i]에 m을 넣어준다. 2. N보다 작을때 dp[i] = max(현재 상담을 완료하면 받는 금액(arr[i][1]) + 현재 상담을 마친 일자부터의 최대 이윤(dp[arr[i][0] + i], m) 으로 갱신해준다. (m = 마지막날부터 계산할 때 현재까지의 최대 상..
https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net # 'N개의 행성을 터널로 연결하는데 필요한 최소비용' 보자마자 MST가 떠올랐다. # 처음에 N개의 행성 사이의 터널 건설비용을 모두 구한 뒤, 크루스칼 알고리즘을 사용하려 했다. 그런데, 모든 터널 건설비용을 구하기 위해선 N^2번의 연산이 필요하지만 N이 최대 10만이므로 이렇게 하면 시간초과가 발생한다. # A와 B 사이의 터널 건설비용은 min(|xA-xB..
https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net # union-find로 푸는 방법과 BFS+이분탐색으로 푸는 방법 두가지가 있다. I. Union-Find 1. M개의 그래프정보를 입력받을 때 graph배열에 [-c, a, b]를 append해준다. (c = 중량제한, a = 시작 섬, b = 끝 섬) 아래 코드처럼 -c로 중량제한을 받은 뒤, sort해도 되고 c로 입력받은 뒤, 내림차순 so..
https://leetcode.com/problems/top-k-frequent-elements/ Top K Frequent Elements - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com # 문제해설: nums 배열과 k가 주어졌을때, nums배열에서 가장 자주 등장하는 k개의 수를 return해라. (순서는 상관없다) # heap을 사용해서 푸는 간단한 문제이다. # defaultdict을 사용해 cnt에 nums의 숫자들의 갯수를 저장해준다. (Count..
https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net # 꽤 까다로운 BFS 문제이다. # 이 문제를 푸는데 있어서 주의할 점은 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없으므로 물을 먼저 흘려보낸 뒤 고슴도치를 이동시켜야 한다는 것이다. # dist_beaver는 고슴도치가 이동하는데 걸리는 시간, dist_water는 물이 차는데 걸리는 시간 두 가지 배열로 상태를 나타내고 비교했다. # bfs_water함수를 통해 먼저 물을 흘려보낸 뒤, ..
https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net # BFS 문제이다. # 1번 후보부터 N번 후보까지 각각 bfs함수를 실행해 dist값을 갱신해준다. (dist값 = 현재 후보와의 거리 = 문제에서 요구하는 '점수') # dist값의 최대가 현재 후보의 점수이다. 따라서 점수가 가장 작은 사람이 회장후보이므로 chairman 배열에 회장후보들을 넣어준다. 마지막에 점수와, 후보 수, 후보들을 출력해주면 끝 import sys from coll..
https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net # 2019년 하반기 삼성SW 역량테스트 문제이다. # 문제를 이해하는데 오래 걸렸다. 그림만 보면 금방 이해가 갔을텐데, 글로 길게 써놓으니 헷갈렸다.. # 5개의 선거구로 나누고 각각의 선거구의 인구 합을 구한 뒤, 인구가 가장 많은 선거구와 가장 작은 선거구의 인구 차이를 구하는 문제이다. # (x, y, d1, d2) = (1, 1, 1, 1)부터 (N-2, N-2, N-2, N-2)까지 완전탐..
https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net # 2017 하반기 삼성SW 역량테스트 문제이다. # 단순 구현, 시뮬레이션 문제라 어렵지 않았다. # 톱니바퀴도 4개로 고정이고, 톱니개수도 8개여서 그냥 브루트포스형식으로 풀면된다. import sys from collections import deque input = sys.stdin.readline gear = {} for i in range(4): gear[i+1] = deque(in..
모르는 사이에 조금씩 조금씩..
