선발대

프로그래머스: 가장 먼 노드 (링크)    from collections import dequedef solution(n, edge): A = [[] for _ in range(n+1)] # 그래프 데이터 visited = [-1] * (n+1) # 방문 거리 저장 리스트 answer = 0 # 최대 거리 노드 개수 # 그래프 데이터 저장 for line in edge: A[line[0]].append(line[1]) A[line[1]].append(line[0]) # 큐 자료구조에 시작 노드 삽입 queue = deque() queue.append(1) while queue: # 현재 노드 가져..

LeetCode: 1011. Capacity To Ship Packages Within D Days (링크)   class Solution: def shipWithinDays(self, weights: List[int], days: int) -> int: l, r = max(weights), sum(weights) res = r def canShip(cap): ships, currCap = 1, cap for w in weights: if currCap - w 참고한 풀이: https://www.youtube.com/watch?v=ER_oLmdc-nw

프로그래머스: 입국심사 (링크) # 풀이 참고def solution(n, times): left = 1 right = max(times) * n while left = n: break if people >= n: answer = mid right = mid - 1 else: left = mid + 1 return answer참고한 블로그: https://velog.io/@jqdjhy/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%9E%85%EA%B5%AD%EC%8B%AC%EC%82%AC..

Leetcode: 1277. Count Square Submatrices with All Ones (링크)  입력값으로 0, 1로 구성된 행렬이 주어지고 여기에서 모든 하위 사각형의 개수를 구하는 문제이다. 모든 행렬 요소를 for문으로 돌면서 처음에는 길이가 1인 사각형만 찾고 루프가 종료되면 다음에는 길이가 2인 사각형, 다음은 길이가 3인 사각형, ... 이런 식으로 루프를 더 이상 해당 길이의 사각형을 구하지 못할 때까지 계속 돌면 구할 수 있다. 그러나 시간이 오래 걸리고 비효율적인 방법이다. 따라서 기존 행렬을 for문으로 한 번만 돌면서 해당 위치에서 가능한 사각형 길이 개수를 갱신하는 방법으로 진행한다.  0번째 행과 열은 해당 위치에서 길이가 1인 사각형만 구할 수 있다. 그러므로 시작하..

LeetCode: 1043. Partition Array for Maximum Sum (링크)    class Solution: def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int: dp = [0] * k dp[0] = arr[0] for i in range(1, len(arr)): cur_max = 0 max_at_i = 0 for j in range(i, i-k, -1): if j 0 else dp[-1] max_at_i = max(max_at_i, cur_sum + sub_sum)..

Leetcode: 1641. Count Sorted Vowel Strings (링크)     class Solution: def countVowelStrings(self, n: int) -> int: return ((n+4)*(n+3)*(n+2)*(n+1))//24참고한 풀이: https://www.youtube.com/watch?v=tEWj6P-488M

Leetcode: 894. All Possible Full Binary Trees (링크)    # Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]: dp = { 0: [], 1: [TreeNode()] } def backtrack(n): ..

프로그래머스: 구명보트 (링크) 우선 people 리스트를 오름차순으로 정렬해야 한다. 그리고 while문을 돌면서 deq의 0번째 인덱스와 마지막 인덱스의 요소를 더했을 때 limit보다 작은지 확인한다. 여기에서 작다면 pop(), popleft()로 둘을 제거하고 cnt += 1을 해준다. limit을 초과했을 경우는 제일 큰 수인 마지막 인덱스 요소만 pop()으로 제거해 준다. 모든 사람들의 각 몸무게는 보트의 한계를 넘지 않으므로 따로 if문 조건을 거치지 않고 pop()만 해주면 된다. 다만 여기 if문에서 0번째 인덱스와 마지막 인덱스 요소를 비교하기 때문에 deq에 1개의 요소만 남았을 때도 생각해 주면 된다. from collections import dequedef solution(p..

프로그래머스: 조이스틱 (링크) 상하 이동은 아스키 코드 계산해서 구했는데 좌우 이동을 어떻게 구해야 할지 감이 잘 잡히지 않았다. 처음에 참고했던 블로그에서는 좌우 이동을 아래 2가지 중의 최솟값을 구하는 방식으로 구했었다.  (1) 왼쪽에서 오른쪽으로 직선 이동 ( = 전체 길이 - 1)(2) 왼쪽부터 시작해서 A 만나면 다시 돌아가고 오른쪽부터 시작 그런데 이렇게 제출해보니 몇 개의 테스트를 통과하지 못했고, 다른 풀이도 찾아보니 오른쪽에서 시작하는 경우를 제외했었다는 것을 알게 되었다. 그래서 아래의 3가지 경우에서 좌우 이동의 최솟값을 찾아야 한다. (1) 왼쪽에서 오른쪽으로 직선 이동 ( = 전체 길이 - 1)(2) 왼쪽부터 시작해서 A 만나면 다시 돌아가고 오른쪽부터 시작(3) 오른쪽부터 시..

LeetCode: 2415. Reverse Odd Levels of Binary Tree  (링크) 백준에 너무 익숙해지다 보니 당연히 input으로 주어진 값이 리스트일 것이라고 당연하게 생각하고 풀이를 시작했다. 그래서 트리 노드의 특성을 전혀 살리지 못하고 2의 몇 승인지에 따라 리스트 슬라이싱을 계산했다. 그러나 실제 코드에서는 len(root) 자체가 불가능하여 풀이를 새로 작성해야 했다. 문제에 대해 설명한 유튜브를 봤는데 스위칭 방식이 간단해서 이를 참고하여 풀었다. 예를 들어 홀수 레벨의 노드가 [1, 2, 3, 4, 5, 6]이라면 최종적으로 [6, 5, 4, 3, 2, 1]로 변경되어야 하며, 각 노드의 위치가 항상 동일하게 대응된다. 즉, (1, 6), (2, 5), (3, 4)처럼 ..

LeetCode: 797. All Paths From Source to Target (링크) input 값이 2차원 배열로 주어져서 어떻게 해야 했는데 다른 분의 풀이를 참고해보니 path + [end] 로 매번 더할 수 있는 걸 알게 되었다. 예를 들어 path = [[0, 1], [0, 2]], end = 3 이라면 path + end = [[0, 1, 3], [0, 2, 3]] 이런 식으로 구할 수 있다. 그래서 queue에 시작점인 0을 넣어주고 for문을 돌면서 해당 인덱스와 연결된 요소들도 마지막 인덱스가 아니라면 queue에 새로 넣어준다. 이걸 while문으로 queue값이 전부 없어질 때까지 돌면 연결된 모든 경로를 구할 수 있게 된다. class Solution: def allPa..

LeetCode: 1302. Deepest Leaves Sum (링크) Leetcode 저번에 처음 풀어봤는데 아직도 사용법이 익숙해지지 않은 것 같다. 문제를 요약하자면 다음과 같다. root 변수에 리스트를 주고 이걸 트리 구조로 만든 후 제일 깊은 레벨의 노드들의 합을 구하는 문제였다.  당연히 입력값은 리스트만 주어지고 이걸 트리로 구현하는 것부터 시작이라고 생각했는데, 다른 사람의 풀이를 참고하니 이미 트리는 만들어진 상태였다. 그냥 노드들을 돌면서 왼쪽, 오른쪽 자식이 있는지 확인하고 있다면 next_nodes라는 빈 리스트에 다음에 확인할 노드들을 넣어주면 됐다. level_sum은 계속 초기화되니까 결국 마지막 출력값은 제일 깊은 레벨의 노드들을 더한 값과 같아진다. 다만 이해가 안 가는 ..

프로그래머스: 게임 맵 최단거리 (링크) 동, 서, 남, 북으로 1칸씩 이동하고 최단거리를 구하는 문제여서 바로 BFS로 풀었다. 다만 처음에 문제를 잘못 이해해서 n, m이 예시 문제에 있는 5로 고정되어 있는 줄 알았고 결국 다시 풀었다. 주어지는 건 2차원 배열인 maps 뿐이라 행과 열의 개수를 직접 구해야 했다. BFS 문제는 전형적인 틀이 있는데 거기에서 크게 벗어나는 부분이 없었다. 최단 거리를 구해야 하므로 그냥 바로 직전 지점의 +1 값을 계속 갱신하는 부분만 추가했다.  다른 사람들의 풀이를 보니까 다들 BFS로 거의 비슷하게 풀었는데 제일 상단에 이상한 코드가 하나 있었다. 무조건 프로그래머스의 모든 문제를 통과하게 만드는 코드라고 하는데 지금은 막힌 것 같지만 어떻게 알았는지 궁금하..

프로그래머스: 타겟 넘버 (링크) BFS 방식으로 어떻게 풀어야 할지 고민하다가 잘 모르겠어서 다른 분의 풀이를 참고했다. 생각보다 간단하게 풀 수 있는 문제였다. 큐에 매번 모든 수의 양수와 음수를 넣고 마지막에 모든 인덱스까지 돌았다면 큐에서 하나씩 꺼내서 타겟과 맞는지 확인하면 된다.  예시를 들어보자면 numbers = [4, 1, 2, 1], target = 4 일 때 제일 처음 큐에는 [4, 0], [-4, 0] (=numbers[0], 인덱스)가 들어가게 된다. 이후에 while문을 돌면서 다음 인덱스인 1의 양수, 음수 값도 큐에 넣는다. [5, 1], [3, 1] 이런 식으로 넣고 큐에 남아 있던 [-4, 0]도 꺼내서 [-3, 1], [-5, 1]을 다시 큐에 넣어준다. 이걸 인덱스 끝..

프로그래머스: 소수 찾기 (링크) 얼마 전 99클럽 1기에서 풀었던 문제라 이번에는 다른 분들의 풀이를 참고해서 다시 풀어봤다. 풀이 (1)는 set을 미리 정의해 두고 permutations으로 모든 조합을 넣은 후 다시 소수 판별을 하는 방식이었다. 풀이 (2)는 코드가 엄청 깔끔해 보여서 가져왔는데 makeCombinations 함수에서 재귀로 모든 경우의 수를 돌리는 게 신기했다. 만약 numbers에 '123'이 들어오게 되면 makeCombinations의 str1, str2에는 각각 ('', 123), (1, 23), (123, '') -> (13, 2), (132, '') -> (12, 3), (123, '') 이런 식으로 가능한 모든 조합이 생성된다. 이런 방법은 생각 못했는데 잘 기억해..