CS
[Programmers] 베스트앨범
[Programmers] 베스트앨범 🎈문제 https://programmers.co.kr/learn/courses/30/lessons/42579 💬설명 조금의 생각이 필요한 문제였다. python의 sort함수를 잘 이용하면 쉽게 풀 수 있다. 간단하게 얘기하면 아래와 같다. 장르 이름을 key로 가지는 dictionary에 노래들을 [재생횟수, 고유 번호] 배열로 집어 넣는다. 장르별로 노래 총 재생횟수도 함께 세어준다. 노래가 많이 재생된 장르별로 정렬한다. 정렬된 장르별로 각 장르에 속하는 노래를 "재생횟수 -> 고유 번호" 순으로 정렬해서 최대 2개씩 answer 배열에 append 해준다. 👩💻코드 def solution(genres, plays): answer = [] songs = {} g..
[Programmers] 위장
[Programmers] 위장 🎈문제 https://programmers.co.kr/learn/courses/30/lessons/42578 💬설명 문제 자체는 어렵지 않았다. 우선 옷 종류별로 dictionary에 넣어서 개수를 센다. (ex) {"face": 2, "headgear": 1 } 각각의 옷 종류별로 (아무것도 선택 안함, 첫번째꺼 선택, 두번째꺼 선택, ... 마지막꺼 선택) 이렇게 선택이 가능하다. 즉, face가 2개가 있다면 (아무것도 선택 안하거나, 선글라스를 선택하거나, 마스크를 선택하거나) 이렇게 3가지의 선택지가 있다. 옷 종류별로 n + 1가지의 선택지가 있으므로 이것들을 전부 곱해준다. 중요한건 아무것도 입지 않는 경우는 없으므로 1을 빼줘야 한다는 것. 효율성 점수도 없고..
[Programmers] 전화번호 목록
[Programmers] 전화번호 목록 🎈문제 https://programmers.co.kr/learn/courses/30/lessons/42577?language=python3 💬설명 전화번호 목록이 있을 때 임의의 전화번호가 다른 전화번호의 접두어인 경우가 있는지 체크하는 문제 이중 for문을 이용해 풀어 줄 수도 있지만 "phone_book의 길이는 1 이상 1,000,000 이하입니다." 로 봐서 그렇게 하면 바로 효율성에서 틀릴 것 같았다. 따라서 모든 전화번호를 파이썬의 dictionary에 넣어두고(N) 전화번호 하나씩 돌아가면서(N) 처음-i번째까지가 dictionary에 있는지 체크(최대 20)하는 방식으로 풀어줬다. 이렇게 하면 dictionary는 찾는게 O(1)밖에 안걸리기 때문에 ..
[Programmers] 완주하지 못한 선수
[Programmers] 완주하지 못한 선수 🎈문제 https://programmers.co.kr/learn/courses/30/lessons/42576 💬설명 우선 문제 자체는 어려운 문제가 아니다. 다만 효율성을 따지면 조금 생각이 필요했다. 푸는 방식이 매우 다양한데, 그중 파이썬은 collections 모듈에 있는 Counter를 이용하면 아주 편하다. 공식 레퍼런스 사이트는 여기서 보면 된다. 재밌는 모듈을 하나 알아가서 좋았다:) 👩💻코드 from collections import Counter def solution(participant, completion): # 각각에 대해 정렬 participant.sort() completion.sort() # 개수만큼 빼준다. 없는 사람이 있으면 ..
[BaekJoon] 백준 17471번 게리맨더링
[BaekJoon] 백준 17471번 게리맨더링 🎈문제 https://www.acmicpc.net/problem/17471 💬설명 2 ≤ N ≤ 10 , 1 ≤ 구역의 인구 수 ≤ 100 제한사항이 위와 같아 0.5초에도 충분이 돌릴 수 있는 양이라고 생각했기 때문에 조합 -> bfs를 이용해 풀어줬다. 문제 풀이 순서 1-N/2만큼의 조합을 구한다. (ex. N=4일때, 길이 1 + 길이 3, 길이 2 + 길이 2의 조합) 구한 조합을 가지고 각각에 대해, 총 2번 bfs를 돌린다. bfs를 돌았을 때 모든 노드가 2개의 선거구로 나뉠 수 있다면(연결되어 있다면) 인구수 차이의 최소값을 update한다. 👩💻코드 # BaekJoon17471.py from collections import deque ..
[BaekJoon] 백준 1949번 우수마을
[BaekJoon] 백준 1949번 우수마을 🎈문제 https://www.acmicpc.net/problem/1949 💬설명 이차원 배열로 dp를 짜는건 아직 어려운 것 같다ㅜ dfs + dp로 풀어주면 되는 문제 파이썬에서는 재귀 함수 깊이에 제한이 있어서 sys.setrecursionlimit()을 통해 이를 풀어줘야 한다. 👩💻코드 # BaekJoon 1949.py import sys sys.setrecursionlimit(20000) N = int(input()) people = [0] + list(map(int, input().split())) visited = [False for _ in range(N + 1)] # 방문여부 저장 s = [[] for _ in range(N + 1)] # 연..
[BaekJoon] 백준 2352번 반도체 설계
[BaekJoon] 백준 2352번 반도체 설계 🎈문제 https://www.acmicpc.net/problem/2352 💬설명 LIS 문제인데 DP로 풀게되면 시간초과가 난다. 이분탐색으로 문제를 풀어줘야 한다. 👩💻코드 # BaekJoon 2352.py N = int(input()) arr = list(map(int, input().split())) lst = [] # 이분 탐색으로 lower bound 찾아주기 def find(s, e, v): global lst while s < e: m = (s + e) // 2 if lst[m] < v: s = m + 1 else: e = m return e for i in range(N): # 첫번째 숫자인 경우 if i == 0: lst.append(ar..
[Algorithm] 최장 증가 수열 (LIS)
최장 증가 수열(LIS) 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 한다. 푸는 방법 DP dp[x] : x번째 수를 마지막 원소로 가지는 list의 길이 라고 점화식을 두면 O(N^2)의 시간복잡도로 구현할 수 있음 하지만 N이 10만이 넘으면 이걸로 풀수 없음 -> 이분탐색으로 시간을 단축시키자 for (int k = 0; k < n; k++){ length[k] = 1; for (int i = 0; i < k; i++){ if(arr[i] < arr[k]){ length[k] = max(length[k], length[i] + 1); } } } 이분탐색 시간 복잡도: O(..