본문 바로가기

분류 전체보기

 (171)
[프로그래머스][Python] 기능개발 문제를 정리해보자. 1. 각 기능은 진도가 100%일 때, 서비스에 반영한다. 2. 각 기능의 개발 속도는 모두 다르다. 3. 뒤에 개발이 먼저 완료되어도, 앞에 기능이 배포될 때 함께 배포해야 한다. 배포 순서대로 작업 진도 적힌 배열 : progresses 각 작업의 개발 속도 적힌 배열 : speeds 문제는 '배포마다 몇 개의 기능이 배포되는지' 찾는 것이다. def solution(progresses, speeds): answer = [] while progresses: progresses = list(map(lambda x1, x2: x1 + x2, progresses, speeds)) result = 0 while progresses: if 100
[프로그래머스][Python] 베스트앨범 문제를 정리해보자. 노래를 수록해야 한다. 그 기준은 아래와 같다. 1. 속한 노래가 많이 재생된 장르를 먼저 수록한다. 2. 장르 내에서 많이 재생된 노래를 먼저 수록한다. (재생 횟수가 같다면? 고유 번호가 낮은 노래를 먼저 수록한다.) 1번과 2번을 위한 딕셔너리를 각각 만들었다. 전자는 genres_sum, 후자는 genres_two_plays. 1번은 각 장르의 노래 재생 수를 다 더하면 된다. 2번은 조건문을 이용했다. 아래 예시로 설명하겠다. classic은 500, 150, 800을 가지고 있다. 그리고 pop은 600, 2500을 가지고 있다. classic은 800, 500, 150 순서가 되어야하고, 2개만 선택해야 하니까 800, 500만 남아야 한다. 따라서 재생 수가 높은 순으로..
[프로그래머스][Python] 위장 조합을 이용했다. (조합은 서로 다른 n개에서 순서에 상관없이 r개를 선택하는 것이다.) 예를 들어보자. 2개의 모자 종류와 1개의 안경은 종류가 있다. 아래와 같이 경우의 수를 구할 수 있다. 문제에서 '스파이는 하루에 최소한 한 개의 의상은 입습니다'라고 했다. 따라서 아무것도 안 입는 경우를 제외시켜야 한다. 빨간색으로 표시한 부분이 그 부분이다. (Π (의상 종류 + 1)) - 1 식은 이와 같다. def solution(clothes): dic = {} for li in clothes: c, k = li if dic.get(k, 0): dic[k] += 1 else: dic[k] = 2 answer = 1 for val in dic: answer *= dic[val] return answer -..
[프로그래머스][Python] 전화번호 목록 백준에서 트라이로 푼 문제이다. 이번엔 다른 사람 풀이를 분석해보자. def solution(phoneBook): phoneBook = sorted(phoneBook) for p1, p2 in zip(phoneBook, phoneBook[1:]): print(p1, p2) if p2.startswith(p1): return False return True print(solution(["12", "1235", "567", "88"])) 내장 함수에 대해 알아보자. 1. zip 순회할 수 있는 객체들을 받는다. 각 객체가 가지고 있는 원소를 Tuple 형태로 차례로 접근할 수 있는 반복자를 반환한다. (반복자란 내부의 요소를 순회하는 객체이다.) 2. startswith(시작 문자, 시작 지점) 문자열이 특..
[프로그래머스][Python] 완주하지 못한 선수 완주자의 이름을 key로 인원수를 value로 잡고, c_dic에 저장했다. 그리고 참가자 이름을 하나씩 꺼내서 비교했다. key에 해당 참가자 이름이 없거나 value에 해당 참가자 수가 0명이면, 그 사람은 완주하지 못한 참가자이다. def solution(participant, completion): c_dic = {} for key in completion: if not c_dic.get(key, 0): c_dic[key] = 1 else: c_dic[key] += 1 for key in participant: if (not c_dic.get(key, 0)) or c_dic[key] == 0: return key else: c_dic[key] -= 1 입력으로 'Hello'가 들어왔을 때, 'H'..
[자료구조] 해시[Hash] 해시함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 해시함수는 단방향 암호화 기법으로 해시를 만든다. (단방향 암호화 기법은 암호화는 가능하지만 복호화는 불가능한 알고리즘이다.) 추가적인 개념에 대해서도 알아보자. 키[Key] : 매핑 전 데이터의 값 해싱[Hashing] : 매핑하는 과정 해시값[Hashing Value] : 매핑 후 데이터의 값 해시 테이블[Hash Table] : 해시값에 의해 직접 접극이 가능한 데이터 구조 슬롯[Slot] : 한 개의 데이터를 저장할 수 있는 공간 해시함수의 장점은 아래와 같다. 1. 접근/탐색 속도가 빠르다 2. 키에 대한 데이터의 중복확인이 쉽다. (같은 입력값에 대해서는 같은 출력값을 보장하기 때문이다.) 파이썬에서는 딕셔너리[Dic..
[BOJ] [Python] 5052 : 전화번호 목록 하나라도 문자열 전체가, 다른 문자열과 겹친다면 NO를 출력한다. (아니면 YES.) 트라이를 이용해서 해결했다. 주의해야 할 점은 '911', '91125426'과 같은 입력이 같이 들어올 때이다. 1. '91125426'이 먼저 들어오고 그 후에 '911'이 들어온다. search 함수에서, '911'이 트라이를 돌면서 문자열 전체가 겹친다면 True를 반환한다. 2. '911'이 먼저 들어오고 그 후에 '91125426'이 들어온다. search 함수에서, '91125426'이 트라이를 돌면서 data가 None이 아니라면 어떤 문자열과 겹치는 것이다. True를 반환한다. 1, 2가 모두 해당이 안 된다면 insert 함수를 실행시켜, 문자열을 트라이에 넣어준다. import sys class N..
[BOJ] [Python] 4358 : 생태학 트라이를 이용해 해결했다. 시간복잡도는 O(N * M)이다. (N : 최대 그루 수, M : 최대 이름 길이) 입력이 N은 1,000,000, M은 30이니까, 30,000,000으로 1초내 수행이 가능하다. (문자열 탐색 알고리즘을 사용하지 않으면 O(N * N * M)이라 시간 초과이다.) import sys class Node(object): def __init__(self, key, data=None): self.key = key self.data = data self.children = {} class Trie(object): def __init__(self): self.head = Node(None) def insert(self, string): curr_node = self.head for ..
[자료구조] 트라이[Trie] 문자열 탐색 알고리즘에 대해 알아보자. 트라이는 입력된 문자열을 트리 형식으로 만든 자료구조이다. 트라이를 이용하면 효율적 탐색이 가능하다. 만약 최대 N개의 문자열이 주어지고, 각 문자열은 최대 M의 길이를 갖는다고 해보자. 이때 특정 문자열의 개수를 구한다면 얼마나 걸릴까? 먼저 모든 문자열을 삽입하고, 특정 문자열과 동일한 문자열을 찾아야 한다. 1. 단순한 방법 모든 문자열을 삽입하는 시간복잡도는 O(N * M)이다. 특정 문자열을 탐색하는 시간복잡도는 O(N * M)이다. 2. 트라이 이용 모든 문자열을 삽입하는 시간 복잡도는 O(N * M)이다. 특정 문자열을 탐색하는 시간복잡도는 O(M)이다. class Node(object): def __init__(self, key, data=None):..
[자료구조] 트리[Tree] 먼저, 트리 관련 용어를 알아보자. (나동빈의 '이것이 취업을 위한 코딩 테스트다'를 참고했다.) 루트 노드: 부모가 없는 최상위 노드 단말 노드: 자식이 없는 노드 크기: 트리에 포한된 모든 노드의 개수 깊이: 루트 노드부터의 거리 ( 예) 노드 F의 깊이는 0이다. 예) 노드 A번의 깊이는 2이다. ) 레벨 : 특정 깊이를 가지는 노드의 집합 높이: 깊이 중 최댓값 차수: 각 노드의 (자식 방향) 간선 개수 1. 트리 트리는 자료구조의 일종이며, 1. 사이클이 없이 2. 모든 정점이 연걸되어 있는 그래프이다. 사이클이 없는 그래프이기 때문에, 트리의 크기가 N이면 간선의 개수는 N-1개이다. 조건 1, 2만 만족하면 트리이다. 따라서 루트 노드의 존재여부는 트리 여부의 영향을 미치지 않는다. 1) 루..

티스토리툴바