Algorithm

    Coding Test(Priority Queue, Heap)

    Coding Test(Priority Queue, Heap)

    우선순위 큐(Priority Queue) 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 - list를 이용한 구현 - heap을 이용한 구현 단순히 N개의 데이터를 heap에 넣었다가 모두 깨내는 작업은 정렬과 동일 == Heap Sort =>O(NlogN) Heap - Max value or Min value을 찾아내는 연산을 빠르게 하기위해 완전 이진 트리를 기본으로한 자료구조 - heap에서는 항상 root node를 제거 최소 힙(min heap) - root node가 가장 작은 값을 가진다 - 값이 작은 데이터가 우선적으로 제거 최대 힙(max heap) - root node가 가장 큰 값을 가진다 - 값이 큰 데이터가우선적으로 제거 완전 이진 트리(Complete Binary T..

    프로그래머스 양궁대회(시뮬레이션, 그리디)

    프로그래머스 양궁대회(시뮬레이션, 그리디)

    https://programmers.co.kr/learn/courses/30/lessons/92342 코딩테스트 연습 - 양궁대회 문제 설명 카카오배 양궁대회가 열렸습니다. 라이언은 저번 카카오배 양궁대회 우승자이고 이번 대회에도 결승전까지 올라왔습니다. 결승전 상대는 어피치입니다. 카카오배 양궁대회 운영위원 programmers.co.kr #시뮬레이션 from itertools import combinations_with_replacement # a가 b보다 더 좋은 배치일 경우 true def cmp(a, b): return a[::-1] > b[::-1] def solution(n, info): # 라이언이 가장 큰 점수 차이로 우승할 수 있는 결과를 저장 # ret[0..10] : 10-i점에서 ..

    프로그래머스 쿼드압축 후 개수 새기(분할 정복)

    https://programmers.co.kr/learn/courses/30/lessons/68936 코딩테스트 연습 - 쿼드압축 후 개수 세기 [[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]] [4,9] [[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]] [10,15] programmers.co.kr 백준 1780 종이의 개수 와 동일한 분할 정복 문제 def solution(arr): import sys sys.setrecursionlimit(10 ** 6) data =..

    백준 18243 Small World Network(플로이드-와샬, BFS)

    https://www.acmicpc.net/problem/18243 18243번: Small World Network 첫 번째 줄에 지구에 있는 사람의 수 N과 친구 관계의 개수 K가 주어진다. 모든 사람은 1부터 N까지 번호가 매겨져 있다. (1 ≤ N ≤ 100, 0 ≤ K ≤ N×(N-1)/2) 두 번째 줄부터 K+1번째 줄까지 친구 www.acmicpc.net import sys n, k = list(map(int,input().split())) edges = [list(map(int,input().split())) for _ in range(k)] INF = sys.maxsize def make_graph(): graph = [[INF] * n for _ in range(n)] for frm, ..

    10816 숫자 카드 2(Hashmap, Counter)

    https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net #단순 리스트 탐색 n = int(input()) data1 = list(map(int,input().split())) m = int(input()) data2 = list(map(int,input().split())) for i in data2: temp = data1.count(i) print(temp, end=' ') N과 M이 500,000이기 때문에 단순..

    백준 1764 듣보잡(set() 자료형)

    그냥 단순하게 중복을 제외시키는 문제이지만 list를 이용하여 if - in 을 이용하면 시간초과가 난다. #시간초과 import sys input = sys.stdin.readline n,m = list(map(int,input().split())) data = [] data1 = [] for _ in range(n): data.append(input()) for _ in range(m): data1.append(input()) res = 0 ans = [] for i in data: if i in data1: res += 1 ans.append(i) print(res) ans.sort() for i in ans: print(i) 따라서 집합 자료형을 써서 교집합의 성질을 이용하면 쉽게 풀 수 있다. ..