국문과 유목민

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다. 문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다. 소요시간: 20분 1. 문제 설명 - 0과 1로 이루어진 string에서 최소한의 뒤집기 연산을 수행해 모든 string을 0이나 1로 통일시켜라 2. 접근 방식 - for문을 한 번 돌아서 0인 경우와 1인 경우를 골라서 더 짧은 경우를 뒤집어주면 될 거 같다고 생각. 리스트에 인덱스를 기록했다. - 투포인터 알고리즘을 활용해봤다. ----- - 해답 코드의 경우 접근 방법은 나와 비슷했는데, 코드 상으로는 좀 달라져서 해당 코드도 확인해봤다. 3. 코드 - 내 코드 def changeString(x): global zero, one zero = 0 on..

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다. 문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다. 소요시간: 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..

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..