ALGORITHM/이코테9 [이코테 / GREEDY] 모험가 길드 문제 # 모험가 N명, 공포도 X인 모험가는 반드시 X명 이상으로 구성된 모험가 그룹에 참여해야 # 모험가 몇몇은 마을에 남아있어도 됨. # 여행 떠날 수 있는 모험가 그룹 수 최댓값 구하기 입력 출력 5 2 3 1 2 2 2 생각 '모험가 몇몇은 마을에 남아있어도 된다'는 조건 때문에 공포도가 제일 큰 사람의 경우에 포함하려고 노력 안 하고 버려도 된다. 공포도가 큰 사람은 포함 안 시키는 방향으로 간다면, 오름차순으로 정렬해주고 공포도가 1인 사람의 경우에 혼자 갈 수 있게 해주면 되지 않을까 하는 생각이 들었다. 그래서 오름차순으로 해준 후에 어떻게 할지 고민이 컸다. # 1번째 1, 1+2번째 2, 1+2+3번째가 3이면 그룹 하나씩 만들어질 수 있음. # for i in range(1, n+1).. 2022. 5. 12. [ALGORITHM] 10. 그래프 이론 이것이 취업을 위한 코딩테스트다 with python 문제 풀이 10-7. 실전 문제 '팀 결성' # C10. 그래프 이론 - 실전 문제 '팀 결성' import sys put = sys.stdin.readline n, m = map(int, put().split()) #학생 총 n번까지, m은 입력 개수 parent = [0] * (n + 1) # 부모 테이블 초기화하기 # 특정 원소가 속한 집합을 찾기 def find_parent(parent, x): # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출 if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] # 두 원소가 속한 집합을 합치기 def u.. 2022. 3. 8. [ALGORITHM] 9. 최단 경로 이것이 취업을 위한 코딩테스트다 with python 문제 풀이 9-4. 실전문제 '미래 도시' # C9. 최단 경로 - 실전문제 '미래 도시' import sys put = sys.stdin.readline INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정 # 회사간 1만큼 시간으로 연결된 도로 통해 이동 가능 # 방문판매원이 1번 회사에서 k번 회사를 거쳐 x번 회사로 가는 최소 이동 시간 # 노드의 개수 및 간선의 개수를 입력받기 n, m = map(int, put().split()) # 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화 graph = [[INF] * (n + 1) for _ in range(n + 1)] # 자기 자신에서 자기 자신으로 가는 비용은.. 2022. 3. 7. [ALGORITHM] 8. 다이나믹 프로그래밍 이것이 취업을 위한 코딩테스트다 with python 문제 풀이 8-5. 실전문제 '1로 만들기' # C8. 다이나믹 프로그래밍 - 실전문제 '1로 만들기' import sys put = sys.stdin.readline # 그리디로 elif문 써서 큰 수 순서대로 하면 안 되는 이유 # 맨 처음에 5로 나누는 것보다 1 빼고 시작하는 게 더 작은 케이스가 있을 수 있다! # 그래서 부분문제로 나누고, 기존 연산값 재활용하는 dp로 해야 함 x = int(put()) d = [0]*30001 # DP 테이블 초기화 # x = 1일 때는 이미 1로 만들어졌으니까 연산 필요 없음 -> 2부터 시작 for i in range(2, x+1): # 뒤에 붙은 +1은 계산한 횟수 더하는 것! # -1, /2, /3.. 2022. 3. 6. [ALGORITHM] 7. 이진 탐색 이것이 취업을 위한 코딩테스트다 python 문제 풀이 7-5. 실전문제 '부품 찾기' # C7. 이진 탐색 - 실전문제 '부품 찾기' import sys put = sys.stdin.readline n = int(put()) store = list(map(int, put().split())) m = int(put()) customer = list(map(int, put().split())) for i in customer: if i in store: print("yes", end=' ') else: print("no", end=' ') 이진 탐색으로 풀기 # C7. 이진 탐색 - 실전문제 '부품 찾기' - 이진 탐색으로 풀기 import sys put = sys.stdin.readline n = int.. 2022. 3. 5. [ALGORITHM] 6. 정렬 이것이 취업을 위한 코딩테스트다 python 문제 풀이 6-10. 실전문제 ‘위에서 아래로’ # C6. 정렬 - 실전문제 '위에서 아래로' n = int(input()) nums = [] for i in range(n): nums.append(int(input())) nums = sorted(nums, reverse=True) for i in nums: print(i, end=' ') 6-11. 실전문제 ‘성적이 낮은 순서대로 학생 출력하기’ # C6. 정렬 - 실전문제 '성적이 낮은 순서대로 학생 출력하기' n = int(input()) array = [] for i in range(n): name, score = input().split() #원래 map으로 하려고 했는데 둘 다 int형인 게 아니라.. 2022. 3. 4. 이전 1 2 다음