국문과 유목민

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다. 문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다. 소요시간: 7분 51초 1. 문제 설명 - 문자열이 주어질 때 +, *연산을 수행해서 최대값을 리턴시켜라 2. 접근 방식 - 0이 아니라면 무조건 곱하기가 훨씬 좋다. (라고 쉽게 생각했는데, 0뿐만 아니라 1일 때도 덧셈이 더 좋다는 것을 간과하고 있었다.) - 문자열의 경우 리스트로 만들고 하나씩 뽑아서 연산을 수행한다. 3. 코드 def mul_add(x): answer = 0 word_ls = list(x) for i in word_ls: now = int(i) if now in (0, 1) or answer == 0 : answer += now e..

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다. 문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다. 소요시간: 12분 30초 1. 문제 설명 - 모험가 집단에서 공포도에 따라 그룹을 나눌 때 최소로 나눌 수 있는 그룹을 정한다. 2. 접근 방식 - 여행을 떠날 수 있는 최대 공포자의 수 공포도가 최대인 경우를 정하고(내림차순)으로 그 밑으로 공포도가 같거나 최대인 애들을 넣었었다. - 주어진 테스트 코스는 패스했지만, 후에 해답을 보니 나와는 다르게 '오름차순'으로 했다. 3. 코드 - 초기 코드_(내림차순 구현) from collections import deque def make_group(n, input_ls): q = deque(sorted(inp..

오늘은 이코테 유형별 기출문제 중 "그리티" 파트의 문제 6가지를 풀어봤다. 초반 5문제의 경우 수월하게 풀었었는데, 마지막 "무지의 먹방 라이브" 문제의 경우 시간이 오래 걸렸다. 초반에는 for문으로 풀려다가 안되어서 deque를 이용해 풀었는데, 효율성 부분에서 못 넘어가서 끙끙대다가 결국 2시간 만에 검색을 했다. 방법은 의외로 간단하게 heapq를 사용하는 거였다. 역시 라이브러리를 반만 알고 있으니 몸이 고생하는 것 같다. 결국 이론이 잘 깔려 있어야 그 위에 다양한 것을 올려볼 수 있는 것 같다. 아직은 코테 준비가 초반이니까 너무 일희일비하지 말고 꾸준히 해야겠다. 그리고 그리디 파트 6문제 중 5문제의 경우 아직 해답을 보지 않아서 코드를 다듬지 못했는데, 오늘은 문제 푼 것으로 정리하고..

1. 문제 설명 N개의 강의 중 선수 강의가 있을 경우 특정 강의가 주어졌을 때, 해당 강의를 듣기 위해서 걸리는 최소한의 시간을 구하는 문제 - 위상정렬을 이용하는 문제로 위상정렬 이론에서는 리턴하는 값이 순서였다면, 이번에는 cost이다. 하지만 알고리즘 상에서 큰 변경점은 없다. 단지, 시간의 정보를 담은 리스트 변수가 하나 필요하다. 또한, 초기 input값 처리 부분을 고려하면 될 것으로 보인다. 2. 코드 from collections import deque import copy n = int(input()) indegree = [0]*(n+1) graph= [[] for _ in range(n+1)] time = [0]* (n+1) # 방향 그래프의 간선 정보 입력 받기 for i in ra..

1. 문제 설명 마을을 2개로 나누려고 하는데 가장 효율적으로 나눌 수 있는 방법을 찾는 문제 - 핵심 아이디어는 전체 그래프에서 2개의 최소 신장 트리를 만들어야 한다. - 마을을 2개로 나누는 방법은 모든 그래프를 다 잇고난 이후 비용이 가장 큰 간선을 제거해주면 된다. - 정리하자면 크루스칼 알고리즘으로 최소 신장 트리를 찾은 뒤에 최소 신장 트리를 구성하는 간선 중 가장 비용이 큰 간선을 제거하는 것이다. 2. 코드 def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] def union_parent(parent, a, b): a = find_parent(pare..

1. 문제 설명 팀을 결성하기 위해 학생과 학생을 묶고, 학생과 학생이 같은 팀인지 확인하는 문제. - 학생들을 같은 팀으로 묶는 함수가 존재하고(union_parent), 학생들이 같은 팀인지 확인하는 함수가 존재한다.(same_parent) 2. 코드 def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] def union_parent(parent, a, b): a = find_parent(parent, a) b = find_parent(parent, b) if a < b: parent[b] = a else: parent[a] = b def same_parent(pa..