본문 바로가기
반응형

분류 전체보기103

[이취코] 모험가 길드 출처 : 이것이 취업을 위한 코딩테스트다 with python p. 311 참고 : https://ssssol.tistory.com/49 (여기서 반례를 찾았다) 유형 : 그리디 1. 문제 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했다. 첫째 줄에 모험가의 수 N이 주어지고, 둘 째줄에 각 모험가의 공포도의 값을 N 이하의 자연수로 주어지면, 각 자연수는 공백으로 구분한다. 단, 몇 명의 모험가는 마을에 그대로 남아 있어도 되기 떄문에, 모든 모험가를 특정한 그룹에 넣을 필요는 없다. 예시 5 2 3 1 2 2 예시 출력 2 2. 내 코드 n = int(input()) group = list(map(int, input().split())) gr.. 2022. 2. 9.
[백준] 1931번 : 회의실 배정 유형 : 정렬, 그리디 1. 문제 예제 11 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14 예제 출력 4 # (1,4), (5,7), (8,11), (12,14) 2. 코드 N = int(input()) data = [] for _ in range(N): data.append(list(map(int, input().split()))) data.sort(key = lambda x:(x[1],x[0])) cnt = 1 x = data[0][1] # 끝 for i in range(1,N): # 첫 번째 회의를 두 번째 회의 일정부터 비교 if x 2022. 2. 9.
[이취코] 1이 될 때까지 출처 : 이것이 취업을 위한 코딩테스트다 with python p.99 유형 : 그리디 1. 문제 (자세한 건 책을 참고) 어떠한 수가 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다. 1) N에서 1을 뺀다. 2) N을 K로 나눈다. 첫째 줄에 N이 될 때까지 1번 혹은 2번의 과정을 수행하는 횟수의 최솟값을 출력한다. 예시 25 5 예시 출력 2 2. 내 코드 ## 내 코드 N, K = map(int, input().split()) cnt = 0 while N > 1: if N % K == 0: N = N//K else: N -= 1 cnt += 1 print(cnt) 처음에 별 생각없이 N을 K로.. 2022. 2. 8.
[이취코] 숫자 카드 게임 출처 : 이것이 취업을 위한 코딩테스트다 with python 유형 : 그리디 1. 문제 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한장을 뽑는 게임이다. 룰은 다음과 같다. 1) 숫자가 쓰인 카드들이 N * M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다. 2) 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다. 3) 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다. 4) 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 낮은 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다. 예시 3 3 3 1 2 4 1 4 2 2 2 예시 출력 2 2. .. 2022. 2. 8.
[이취코] 큰 수의 법칙 출처 : 이것이 취업을 위한 코딩 테스트다 with python p.92 1. 문제 배열의 크기 N, 숫자가 더해지는 횟수 M, K가 주어질 때 큰수의 법칙에 따른 결과를 출력하시오. (단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없다) 예시 5 8 3 # N,M,K 2 4 6 4 6 예시 출력 46 2. 내 코드 N, M, K = map(int, input().split()) data = list(map(int, input().split())) data.sort() max1, max2 = data[-1], data[-2] _list = M * [max1] for i in range(K,M,K+1): _list[i] = max2 print(sum(_list)) _list.. 2022. 2. 8.
[이취코] 미로 탐색 출처 : 이것이 취업을 위한 코딩 테스트다 with python 같은 문제 : https://www.acmicpc.net/problem/2178 문제는 링크에 있는 백준에 들어가서 보면 된다. 이 문제 같은 경우는 경로의 길이를 세는 것이기 때문에, BFS로 해야 효과적으로 해결할 수 있다. BFS는 너비우선탐색으로 시작 지점에서 가까운 노드부터 차례대로 모든 노드를 탐색하기 때문이다. DFS는 재귀를 이용해 깊이 우선 탐색을 한다면, BFS는 큐로 어느 정도 탐색하는 지를 볼 수 있다. 여기 풀이에서 특이한 점은 경로의 길이가 원래 노드 값(0,1)을 대체하게끔 푼다는 점이다. 경로의 길이가 노드 값을 대체하기 때문에 마지막 (N-1, M-1) 좌표에서 대체된 값을 출력하면 원하는 결과를 얻을 수 있다.. 2022. 2. 8.
반응형

티스토리툴바