본문 바로가기

알고리즘

[프로그래머스] Summer/Winter Coding(~2018) - 기지국 설치, 파이썬 문제 프로그래머스 기지국 설치 링크 풀이 레벨 3 예전에 나온 문제들은 확실히 쉬운 편이다. 점점 문제도 길어지고 시간이 걸리는 문제가 나오는 것 같다. 컨디션 난조로 집중이 안돼서 그냥 대충 풀었다. 좀 더 고민하면 깔끔한 코드를 구현할 수 있을 것이다. 코드 def solution(n, stations, w): prev = 0 ans = 0 for i, station in enumerate(stations) : pos = station - w - prev - 1 prev = station + w num = 2*w + 1 if pos % num == 0 : ans += pos//num else : ans += pos//num + 1 if i == len(stations) - 1 and station +..
[프로그래머스]Summer/Winter Coding(~2018)- 숫자 게임, 파이썬 문제 프로그래머스 숫자 게임 문제 링크 풀이 레벨 3 풀이법은 간단하다. 두 배열 모두 정렬을 한 후 A의 가장 큰 값보다 B의 가장 큰 값이 크면 둘다 배열에서 없애주고 ans에 1을 더해준다. 반대로 A의 가장 큰값보다 B에 큰 값이 없다면 점수를 얻을 수 없으므로 B의 가장 작은 값을 날려준다.(그리디) 끝까지 반복하여 ans 리턴 코드 from collections import deque def solution(A, B): ans = 0 A.sort(reverse = True) B.sort(reverse = True) a = deque(A) b = deque(B) for i in range(len(A)) : if a[0] < b[0] : ans += 1 a.popleft() b.popleft() ..
[프로그래머스] 징검다리 건너기- 파이썬, O(n), 모노톤큐 문제 2019 카카오 개발자 겨울 인턴십 문제 링크 풀이 문제 풀이의 핵심은 구간(k)에서의 최대값 중 최소값을 구하는 것 밑에 1번 코드로 짜고 장렬히 효율성에서 털림 이분탐색을 써야하나 싶었는데 왠지 O(n)에 풀릴 것 같았음 결국 검색 후 Monotone Queue 를 찾아내 적용시켜 풀었음 본 문제같은 케이스를 "Maximum window sliding" 문제라고 한다고 한다(추가 정보 필요시 키워드로 검색) 추후에 모노톤 큐에 대한 내용을 정리하기로 하고 일단 간단하게 풀이를 아래 코드에 작성해 놓음 코드 효율성 틀린 초기 코드 k개 연속으로 0이 되면 더이상 건널 수 없음에서 착안 시간 복잡도는 O(k) * O(len(stones) - k) 인데 stones 길이 최대값은 200,000, k도..
[프로그래머스]월간 코드 챌린지 시즌1- 풍선 터트리기, 파이썬 문제 프로그래머스 문제 링크 풀이 시간초과를 생각하지 않고 짜다 오래걸렸다(문제를 잘 읽고 풀자 ㅠ) 양 끝은 최후까지 남기는 것이 가능하다([1, 2] 라 했을 때 한 번 작은걸 터트릴 수 있는 기회로 1을 날려버리면 됨) 위 가정을 하기 위해서는 2개 남기기 전까지는 무조건 큰 수를 제거해야 함을 알 수 있다. 예시로 주어진 [-16, 27, 65, -2, 58, -92, -71, -68, -61, -33] 을 보자 따라서 27은 제거되어야 하기 때문에 양 극단이 될 수 없다 = -16보다 작은 수가 왼쪽 끝이 될 자격이 있고 오른쪽도 마찬가지 논리로 적용 [-16, ~], [-92, ~], [~, -92], [~, -71], [~, -68], [~, -61], [~, -33] 이 가능하다. 양쪽 방..
[알고리즘]비트마스크(BitMask), 비트조작 - 파이썬 비트마스크란? 비트마스크는 알고리즘이라기 보다는 알고리즘보다는 테크닉 중 하나 정수의 이진수 표현(비트, 0과 1의 binary digits)을 활용한 기법 states = [True, False, False, True, True, False, False, False, True, True] 등으로 상태 표현 가능# 길이가 5인 집합 { 0, 1, 2, 3, 4 } 있다고 하자 arr = [1, 1, 1, 1, 0] # 배열로 표현하면 비효율 { 1, 2, 3, 4 } => 11110 # 메모리 적게 차이하고 효율적 { 1, 2, 3, 4 } => 11110 => (2^4 * 1) + (2^3 * 1) + (2^2 * 1) + (2^1 * 1) = 30 # 10진수 표현 가능 코드를 간결하게 작성 가능하며..
[leetcode]140. Word Break II, 파이썬 문제 릿코드 문제 링크 풀이 난이도 : hard 풀이, dfs 주어진 wordDict을 돌며 해당 단어로 시작하면 재귀로 돌려줌 s가 빈 채로 인자로 넘어왔다는 뜻은 주어진 wordDict 배열 원소로 문장 s가 완성 가능하다는 뜻이므로 ret에 words 리스트를 더해줌 문제 조건에 맞춰 리턴 코드 class Solution: def wordBreak(self, s, wordDict): ret = [] self.dfs(s, wordDict, ret, []) for i, e in enumerate(ret) : ret[i] = &#39; &#39;.join(e) return ret def dfs(self, s, wordDict, ret, words): if not s: ret.append(words) fo..
2020 KAKAO 코딩테스트- 외벽 점검, 파이썬 문제 프로그래머스 문제 링크 풀이 필요역량 레벨 3 Brute force, permutation 정렬하고 간격으로 어떻게 풀어보려다 결국 테스트케이스에 실패, 다른 코드를 참고했다. weak 배열 크기도 작고, dist 배열 크기도 작기 때문에 완전탐색으로 문제를 풀 수 있다 (=쉽게 푼다고 머리만 쓰고 틀리지 마라) 파이썬 순열 : from itertools import permutations 파이썬 순열 라이브러리 몰라서 새로 짜서 썼다. (= 어리석음) 배워가야할 부분은 1. 완전탐색이 가능하면 단순하게 완전탐색으로 일단 풀자. 2. 원형으로 주어진 자료를 선형으로 풀자. 코드 풀이는 아래 주석으로 달아놓았다. 코드 from itertools import permutations def solutio..
124. Binary Tree Maximum Path Sum - 파이썬 문제 [릿코드 링크](https://leetcode.com/problems/binary-tree-maximum-path-sum/_ 이진트리의 각 노드를 한 번만 지날 수 있을 때 path의 최대값을 구하는 문제 풀이 난이도 hard 처음 풀었을 때 틀려서 다시 풀었다. 한 번만 지날 수 있기 때문에 결국 어느 노드에서 left와 right를 모두 포함할지 결정해야 한다.(어느 노드를 root 노드로 할지) path를 이어나가기 위해서는 왼쪽 혹은 오른쪽 중 하나만 선택해야 한다. 따라서 아래 코드를 실행하면 가장 밑에 level부터 cur_max를 갱신하게 된다. 밑에 있는 노드부터 차례로 path값을 계산한 후 path를 잇는 것이 더 값이 크면 이어나간다. 코드 class Solution: def m..

티스토리툴바