컴공생 일상 블로그 컴공생 일상 블로그

https://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 어릴 때 학교 수학시간에 배웠었던, 최단거리 경우의수 문제이다. 아래 숫자들은 각 지점에 대한 최단거리로 도달가능한 경우의 수 개수이다. 1. 2차원 빈 리스트를 하나 만든다. 2. 시작점은 1로 한다. 3. 웅덩이는 0으로 한다. 4. 가로 첫번째 줄, 세로 첫번째 줄에 대해, 웅덩이를 만나기 전까지는 1, 웅덩이를 만난후에는 0으로 설정해준다. 5..

https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 처음에 아래와 같이 푸니까, 테스트케이스 5, 6, 7 다 틀려서 ..??? 했는데 이전 결과에 N연산만 하는 것이아니라, 숫자 4개의 조합의 경우 (3개로만들수있는경우 * 1개로만들수있는경우) , (2개로만들수있는경우 * 2개로만들수있는경우) 와 같이 모두 경우를 추가해줘야한다. - 코드 def solution(N, number): cases = {} if N==number: return 1 cases[1] = set({N}) for i in range(2, 9): temp = [int(str(N)*i)] for c_half in rang..

https://programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 문제를 잘읽자... (구명보트에 한 번에 최대 2명씩 밖에 탈 수 없다고 한다.) 몸무게 순으로 정렬하고, 양 끝에 포인터를 두어 풀면된다. def solution(people, limit): answer = 0 people.sort() left, right = 0, len(people)-1 while left

https://programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 뭔가 좋은 방법이 잘 생각안나서, 구글링의 도움을 받았다. 앞자릿수가 커야 큰 숫자가 된다는 것과 스택을 활용하면 된다. def solution(number, k): stack = [] for i in number: while stack and i > stack[-1]: #넣으려고 하는 값이 더 클 때 if k > 0: stack.pop() k -= 1 else: break stack.append(i) for i in range(k): stack.pop() return "".join(stack)

https://programmers.co.kr/learn/courses/30/lessons/42860 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 상하 조이스틱과 좌우 조이스틱을 따로 계산한다. 상하 횟수는 구하기 쉽고, 좌우의 경우는 그리디 알고리즘에 따라, 그 순간순간 가장 가까운 위치로 커서를 이동하면서 해를 구하면된다. def solution(name): answer = 0 name = list(name) a = 'ABCDEFGHIJKLM_ ZYXWVUTSRQPON' #상하 계산..

https://programmers.co.kr/learn/courses/30/lessons/42862 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr 문제를 꼼꼼히 안 읽어서 고생했다. def solution(n, lost, reserve): l = [i for i in lost if i not in reserve] r = [i for i in reserve if i not in lost] for i in sorted(r): if i-1 in l: l.remove(i-1) elif i+1 in l: l.remo..

https://programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr 이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다. I 숫자 큐에 주어진 숫자를 삽입합니다. D 1 큐에서 최댓값을 삭제합니다. D -1 큐에서 최솟값을 삭제합니다. heapqueue 알고리즘 - https://docs.python.org/ko/3/library/heapq.html heapq.heapify(x) 리스트 x를 선형 시간으로 제자리에서 힙으로 변환합니다. heapq.nlargest(n, iterable, key=None) iterable에 의해 정의된 데이터 집합에서 n 개의 가장 큰 요소로 구성된 리스트를 반환..

https://programmers.co.kr/learn/courses/30/lessons/86971?language=python3 코딩테스트 연습 - 9주차 9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1 programmers.co.kr 그래프 탐색 문제..? 아무튼 뭐 트리 그래프의 간선을 하나 지워서 두개의 트리를 만들때, 정점이 개수의 차의 최소값을 구하면된다. - 풀이 1. 일단 어떤 간선을 지우는 것이 답인지 모르니까, 하나의 간선을 지운 graph를 만든다. 2. search함수에 graph와, 시작점(삭제한 간선의 정점 중 하나)를 인자로 넘겨준다. 3. stack을 ..