오뚝이개발자

nums=[1,2,1], target=3일 때, nums에서 원소의 합이 target인 부분집합은 몇 개일까? 답은 (1,2), (2,1)로 2개이다. 그렇다면 이를 구하기 위한 알고리즘은 무엇일까? 이러한 문제를 counting subsets with given sum이라 한다. 다른 문제에도 자주 이용되니 알아두자! 가능한 모든 경우를 파악해보면 된다. 그런데 이 때, 각 숫자는 합에 포함되거나 안되거나 둘 중 하나의 선택지를 갖는다. 그림으로 나타내면 아래와 같다. 이를 풀기 위해선 dp를 사용하면 된다. 위와 같이 dp를 모두 채운 뒤 dp[-1][-1]이 답이 된다. 관련 문제 leetcode.com/problems/target-sum/ Target Sum - LeetCode Level up y..

"abc"와 "bca"는 Anagram이다. anagram이란 이처럼 size가 같고, 같은 알파벳으로 이루어진 문자열을 말한다. 그럼 이러한 anagram을 찾으려면 어떠한 알고리즘을 써야할까? 가령 s="abcdebacb", p="cab"일 때, s에서 p와 anagram인 문자열의 인덱스를 찾는다고 해보자. 그럼 어떠한 것이 같아야 anagram이라고 할 수 있을까? size - p의 사이즈만큼 s를 slicing하면 되므로 간단!! 사용하는 알파벳 종류 등장하는 알파벳의 빈도수 이 땐, 2와 3을 비교하기 위해선 비트마스크를 사용하면 된다. 알파벳은 총 26개이므로 26개의 array를 만들고 각 알파벳의 등장 빈도수만큼 + 해준다. p="cab"이므로 p의 비트마스크 p_mask=[1,1,1,0..

deque(double ended queue)는 양방향 연결리스트로 구현되어 있어 양 끝단에 접근이 가능하고 데이터의 삽입, 삭제가 용이하다.(단, 중간 데이터는 제외) 여기선 대표적으로 많이 쓰이는 5가지 operation에 대해 사용법을 정리하려고 한다. 아, 참고로 deque를 사용하려면 import collections.deque를 해주어야 한다. append(x), appendleft(x) append(x)는 오른쪽 끝에 데이터 x를 추가, appendleft(x)는 왼쪽 끝에 데이터 x를 추가한다. 리스트와 달리 deque는 doubly linked list라 둘의 시간복잡도는 모두 O(1)이다. pop(), popleft() pop()은 일반적으로 알고있는 그 pop 연산이 맞다. 즉, st..

시간복잡도 아래는 자주 등장하는 시간복잡도 표기들이다. 표에서 아래로 갈수록 수행시간이 오래 걸린다. list 리스트는 배열이다. 그렇기 때문에 사이즈가 커질수록 삽입과 삭제 연산이 비효율적으로 된다. 이럴 땐 차라리 deque를 쓰는 것이 효율적이다. Operation Average Worst Copy O(n) O(n) Append O(1) O(1) Pop last O(1) O(1) Pop intermediate O(k) O(k) Get item O(1) O(1) Set item O(1) O(1) Delete item O(n) O(n) sort O(nlogn) O(nlogn) min,max O(n) O(n) len O(1) O(1) collections.deque deque(double ended qu..

정렬 방법 중 가장 빠른 것은 O(nlogn)의 시간복잡도를 갖는다고 생각할 수 있다. 하지만 이보다 빠른 O(n)의 시간복잡도를 갖는 정렬방법도 있다. 바로 계수 정렬 다른 말로, 카운팅 정렬이다. 하지만 이러한 계수 정렬은 약간 제한된 조건 하에서 사용가능하다. 1 5 2 3 2 5 1 4 4 2 5 1 위와 같은 수가 나열되어있고 이를 정렬해보자. 그런데 자세히 보면, 위에서 등장하는 수의 범위가 1~5까지라는 것을 알 수 있다. 이처럼 수의 범위가 정해져 있는 경우 계수 정렬을 사용하면 효율적으로 정렬할 수 있다. 카운팅 정렬이란 말 그대로 수가 등장하는 횟수를 카운트 하는 것이다. 카운팅이 다 끝나면 크기 순서대로, 해당 수가 등장하는 횟수만큼 print해주면 된다. 위의 경우, 등장하는 수를 ..

파이썬에는 in 연산자가 있다. 보통 리스트, 튜플, 집합, 딕셔너리 같이 연속적인 자료구조에 속한 멤버를 확인하거나 순회할 때 사용한다. 그렇다면 in 연산자의 시간복잡도는 어떻게 될까? List l = [1, 2, 3, 4, 5] # 멤버 확인 if 1 in l : print("1 is in l") # 순회 for i in l : print(i) Tuple t = (1, 2, 3, 4, 5) # 멤버 확인 if 1 in t : print("1 is in t") # 순회 for i in t : print(i) Set s = {1, 2, 3, 4, 5} # 멤버 확인 if 1 in s : print("1 is in s") # 순회 for i in s : print(i) Dictionary d = {1: ..

뻔하지 않은 자기개발서이다. 끝까지 정말 재미있게 읽었던 것 같다. 저자는 여러 분야에서 큰 성공을 이룬 사람들을 인터뷰했고, 그들의 성공비결을 정리해 책으로 엮어낸 것이 바로 이 책이다. 저자는 그런 사람들을 특별한 힘을 가진 '타이탄'이라는 말로 지칭하고 그들이 가진 어떠한 도구들이 그들을 성공으로 이끌었는지에 대해 말해준다. 채 내용은 작은 절마다 한 명의 사람에 대한 이야기를 담고 있어, 전달하고 있는 내용이 정말 다양하다. 그러나 전체를 관통하는 핵심 내용은 성공한 타이탄들은 모두 자기만의 확실한 철학을 가지고 있다는 점이다. 그리고 그 철학은 정말 확고해서 좀처럼 굽히지 않고 꿋꿋하게 나아가 원하는 바를 성취한다는 것이다. 아무래도 자기개발서인지라... 이 책의 내용을 이렇다 저렇다 하게 요약..

DFS를 활용해 connected component의 갯수를 구하는 것이 필요할 때가 있다. 이럴 땐 탐색을 하면서 각 unit별로 구분을 해서 갯수를 카운트 해주면 된다. 정확히는 이를 union find 알고리즘이라고 한다. 예제를 통해 이해해보자. 아래 문제는 프로그래머스에 수록된 문제이다. programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr def dfs(start, n, visited, computers): fo..