![]()
[문제] https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net [풀이] 힙(Heap)? 힙은 완전 이진트리로 수의 집합에서 가장 작은 수나 가장 큰 수만을 자주 꺼내올 때 유용한 자료구조이다. 항상 자식은 두개밖에 없으며, leaf의 가장 왼쪽부터 값을 채운다. 힙은 크게 최소힙과 최대 힙 두 가지가 있다. 최소 힙은 가장 작은 값이 루트이고, 최대 힙은 가장 큰 값이 루트이다. 힙은 완전 이진트리이지만 코드를 구현하기 위해서는 ..
![]()
[문제] 개발자가 사용하는 언어와 언어 선호도를 입력하면 그에 맞는 직업군을 추천해주는 알고리즘을 개발하려고 합니다. 아래 표는 5개 직업군 별로 많이 사용하는 5개 언어에 직업군 언어 점수를 부여한 표입니다. 예를 들면, SQL의 SI 직업군 언어 점수는 3점이지만 CONTENTS 직업군 언어 점수는 2점입니다. SQL의 HARDWARE, PORTAL, GAME 직업군 언어 점수는 0점입니다. 직업군 언어 점수를 정리한 문자열 배열 table, 개발자가 사용하는 언어를 담은 문자열 배열 languages, 언어 선호도를 담은 정수 배열 preference가 매개변수로 주어집니다. 개발자가 사용하는 언어의 언어 선호도 x 직업군 언어 점수의 총합이 가장 높은 직업군을 return 하도록 solution ..
![]()
[문제] 대학 교수인 당신은, 상호평가를 통하여 학생들이 제출한 과제물에 학점을 부여하려고 합니다. 아래는 0번부터 4번까지 번호가 매겨진 5명의 학생들이 자신과 다른 학생의 과제를 평가한 점수표입니다. 위의 점수표에서, i행 j열의 값은 i번 학생이 평가한 j번 학생의 과제 점수입니다. 0번 학생이 평가한 점수는 0번 행에 담긴 [100, 90, 98, 88, 65]입니다. - 0번 학생은 자기 자신에게 100점, 1번 학생에게 90점, 2번 학생에게 98점, 3번 학생에게 88점, 4번 학생에게 65점을 부여했습니다. 2번 학생이 평가한 점수는 2번 행에담긴 [47, 88, 95, 80, 67]입니다. - 2번 학생은 0번 학생에게 47점, 1번 학생에게 88점, 자기 자신에게 95점, 3번 학생에게..
![]()
[문제] https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net [풀이] 연결요소(Connected Component)란? 그래프는 위의 그림처럼 간선이 존재하지 않아 여러 개로 나누어 있을 수 있다. 이것을 두 개의 그래프로도 볼 수 있지만, 하나의 그리프에 두 개의 연결 요소를 가진다고 볼 수도 있다. 나누어진 각각의 그래프를 연결 요소라고 한다. 연결 요소가 될 조건은 아래와 같다. ..
![]()
[문제] https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net [풀이] 좌표 압축이란? 좌표 압축이란 간단하게 데이터를 정렬한 후 순서를 다시 부여하는 것이다. x, y의 범위가 (-10억~10억) 일 경우 20억의 구간에 업데이트를 해야 하는데 이는 불가능하다. 따라서 이를 해결하기 위해서는 문제에 등장하는 좌표는 많지 않기 때문에 등장한 수만을 이용해 좌표를 압축해야 한다. 이를 좌표 압축이라고 ..
![]()
[문제] https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net [풀이] 입력받은 회의 시간들을 정렬할 때 시작시간과 종료시간이 같을 수 있어 lambda를 이용해 시작시간으로 정렬해준 뒤, 종료시간으로 한번 더 정렬해준다. 5 3 5 1 4 8 11 4 4 2 2 # 시작시간을 기준으로 정렬했을 경우 [[1, 4], [2, 2], [3, 5], [4, 4], [8, 11]] # 시작시간 기준 정렬 후 종료시간 기준으로 정렬했을 경우 [[2, 2], [1, 4], [4, 4], [3, 5], [8, 11]] 가능한 회의 개수를 세는 부분은 고민을 많이 했다.. 현재 ..
![]()
[문제] https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net [풀이] 처음 각 사람이 돈 인출에 걸리는 시간을 리스트에 넣을 때 sorted() 함수를 이용해 오름차순으로 리스트를 정렬해 저장한다. temp와 res를 0으로 초기화한다. temp에는 for문을 돌 때마다 위 첨부사진의 두 번째 줄 숫자가 저장된다. res는 temp 값을 더한다. (3번째 줄) [코드] import sys if __name__ == '__main__': n = int(sys.stdin.readl..
![]()
[문제] https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net [풀이] 입력값을 memo 딕셔너리에 저장한 후 Key를 이용해 Value를 찾는다. 파이썬이라 가능한 간단한 문제인듯하다.. [코드] import sys if __name__ == '__main__': n, m = map(int, sys.stdin.readline().split()) memo = {} for _ in range(n): site, pw = s..
![]()
[문제] https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net [풀이] if kinds in closet.keys(): closet[kinds].append(costume) else: closet[kinds] = [] closet[kinds].append(costume) 의상 종류가 closet 딕셔너리에 있다면 의상을 종류에 맞게 value 리스트에 추가해..
