본문 바로가기

알고리즘

[프로그래머스] 그리디 - 단속카메라, 파이썬 문제 프로그래머스 문제 링크 routes 배열에 각 차량의 진입, 진출 시점이 주어지는데 모든 차량을 감시할 수 있는 최소 카메라의 수를 리턴하는 문제 풀이 요구역량 레벨 3 그리디(아이디어) 프로그래머스에는 그리디 알고리즘 문제로 분류되어 있다. 그리디 알고리즘은 각 단계에서 최선의 선택(논리적으로 합당한)을 이어나가며 문제를 해결하는 방법인데 아이디어가 떠오르면 쉽게 풀리는 경우가 있다. 주어진 routes 배열을 진출시점(=진출 위치, 좌표로 판단)을 기준으로 정렬해 준 후 체크되지 않은 첫 번째 차량의 진출위치를 camera 변수에 담아준다. (모든 차량을 체크해야 하기 때문에 가능한 뒤쪽에 카메라를 설치하는 선택 = 그 시점에서의 최선의 선택) 해당 카메라 위치 전에 진입하는 차량들은 모두 패스..
[알고리즘]MST(Minimum Spanning Tree, 최소신장트리), 파이썬 최소신장트리(MST)란? 신장 트리(Spanning tree): 그래프 내의 모든 정점을 포함하는 트리 n개의 정점 가지는 그래프가 (n-1)개의 간선으로 연결되어 있는 트리 구조의상태 최소신장트리란 최소한의 비용으로 신장트리를 형성하는 것 MST 특징 : 간선의 가중치의 합이 최소, n개의 정점을 가지는 그래프는 반드시 (n-1)개의 간선 사용, 사이클 X 사용 예시 : 도로건설, 파이프, 전화, 배관 등 참고 자료구조(그래프와 노드) 그래프 : 노드와 간선으로 표현, 사이클 가능, 루트노드 개념 없음, 부모-자식 개념 없음, 네트워크 모델 트리 : 노드로 이루어진 자료구조, 사이클 불가능 루트노드 반드시 한 개, 모든 자식노드는 한 개의 부모노드를 가짐, 계층 모델 종류 Kruskal MST 알고리즘..
[프로그래머스] N으로 표현, 파이썬 문제 프로그래머스 링크 풀이 요구 능력 레벨 3 DP라고 하지만 아이디어, 구현 틀려서 답을 참조해서 다시 푼 문제이다. "최솟값이 8보다 크면 -1을 return 합니다" 라는 조건이 있기 때문에 모든 케이스를 고려할 수 있다는 힌트를 얻을 수 있다. 예시 "12 = 55 / 5 + 5 / 5" 에서 볼 수 있듯 사칙연산에 더해 고려해야 할 것은 55가 연속으로 쓰인 부분. N이 5라면 5, 55, 555, 5555, 55555 등을 중심으로 문제를 풀어나갈 수 있다. 따라서 아래 코드로 문제를 풀었다. 코드 def solution(N, number): # 만약 N이 5라면 case는 [{5}, {55}, {555}, {5555}, {55555}, {555555}, {5555555}, {55555555..
[프로그래머스] 해시 - 베스트앨범, 파이썬 문제 프로그래머스 링크 풀이 요구 능력 레벨 3 해시, 딕셔너리, 정렬 문제의 요구사항을 따라가다보면 그다지 어려운 문제는 아니다. 다만 주의해야할 점은 파이썬 딕셔너리에서 sort()를 제공하지 않아 정렬을 위해 내장함수인 sorted()를 사용해야한다. 왜지?? 라는 생각이 들텐데 위에 대한 내용은 시간여유가 있으면 정리해봐야겠다. (= 시간이 없어 대충 풀어제낌 ㅠ) 밑에 코드는 좀 더 깔끔하게 정리 가능하다.(= 지저분하단 소리) 코드 from collections import defaultdict def solution(genres, plays): answer = [] dic_lst = defaultdict(list) dic_n = defaultdict(int) arr = [] # dic_n 딕..
[프로그래머스] 그리디 - 큰 수 만들기, 파이썬 문제 문제 링크 number 문자열이 주어지고 자연수 k가 주어질 때 k 개의 문자를 제거한 가장 큰 수를 문자열로 리턴해야 하는 문제이다. 풀이 레벨 2 스택, 문자열 처리 어려운 편은 아니지만 시간초과가 나올 수 있으며 테스트케이스 12번이 틀릴 수 있다.(Part 2 참조)Part 1 우선 문자열을 arr 배열에 담아준다. 반복문을 돌며 만약 stack이 비어있지 않고 stack의 마지막 원소가 지금 문자열의 수보다 작으면 while문으로 들어간다. 이때 k가 0보다 크고(제거할 문자열이 있고) stack에 문자열이 있고 stack의 마지막 원소가 지금 문자열보다 작으면 stack의 마지막 원소를 제거해준다. 이렇게 할 때 k가 0보다 클 때 stack은 내림차순으로 정렬된다. 큰 수를 위해서는 높..
프로그래머스 - 순위, 파이썬 문제 프로그래머스 링크 풀이 그래프 문제에 속해있지만 해쉬로 풀 수 있는 문제 파이썬 내장모듈인 Collections 의 defaultdict 클래스를 활용하였다. 굳이 활용하지 않아도 되지만 파이썬의 딕셔너리의 경우 키 값이 없으면 에러가 나서 귀찮기 때문이다. defaultdict 클래스를 활용하면 defaultdict(set)의 경우 모든 키에 대해서 값이 없는 경우 자동으로 인자로 넘어온 함수를 호출하여 그 결과값으로 설정해준다. 순위를 정하는 문제이기 때문에 a에게 진 선수들, a를 이긴 선수들을 각각 딕셔너리로 저장해준다.(중복을 피하기 위해 set 자료형 활용 선수 수만큼 반복문을 돌면서 a에게 진 선수들은 a를 이긴 선수들에게도 모두 지고, a를 이긴 선수들은 a가 이긴 선수들을 모두 이긴..
2018 KAKAO BLIND RECRUITMENT - n진수 게임, 파이썬 문제 프로그래머스 n진수 게임 요구 능력 레벨 2 진수 변환에 대한 구현 풀이 그다지 어렵진 않았다고 하기엔 다른 풀이들이 너무 간단했다. 더 최적화가 가능할 것도 같다. 프로그래머스 문제는 2단계는 건너 뛰고 5단계는 제끼고(..) 3, 4 단계 문제만 풀도록 해야겠다. 코드는 읽어보면 어렵지 않게 이해할 수 있기 때문에 코드 설명은 생략 코드(파이썬) def change_base(n, base) : s = "0123456789ABCDEF" ans = '' while n // base > 0 : ans = s[n % base] + ans n = n // base ans = s[n % base] + ans return ans def solution(n, t, m, p): answer = &..
2018 KAKAO BLIND RECRUITMENT- 자동완성, 파이썬 문제 프로그래머스 링크 단어가 배열로 주어지고 각 단어 검색마다 최소한으로 몇 번의 알파벳을 입력해야하는지 구한 후 더해서 리턴하는 문제 풀이 다른 방법을 활용해 풀 수도 있지만(시간초과 주의) 예전 프로그래머스 가사검색 문제를 푼 기억이 있어서 트라이 구조를 활용했다. 트라이 자료구조의 대표적인 활용 예가 자동완성이다. 통과가 되긴 했는데 잘 맞게 쓴지는 모르겠다. 코드 class Node(): def __init__(self) : self.cnt = 0 self.dic = {} class Trie: def __init__(self): self.root = Node() def insert(self, word) : temp = self.root for w in word : if w not in temp...

티스토리툴바