BOJ

[문제] https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net [풀이] 2021.08.18 - [BOJ] - [Python] BOJ/백준 1389번 케빈 베이컨의 6단계 법칙 [Python] BOJ/백준 1389번 케빈 베이컨의 6단계 법칙 [문제] https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 ..

[문제] https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net [풀이] 이전 글의 최소 힙과 같이 파이썬의 heapq 모듈을 사용하나, 해당 모듈은 최소 힙 기능만 동작하기 때문에 최대 힙으로 활용하기 위해서는 조금의 조작이 추가로 필요하다. 2021.08.28 - [BOJ] - [Python] BOJ/백준 1927번 최소 힙 [Python] BOJ/백준 1927번 최소 힙 [문제] https://www.acmicpc.net/pr..

[문제] https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net [풀이] 힙(Heap)? 힙은 완전 이진트리로 수의 집합에서 가장 작은 수나 가장 큰 수만을 자주 꺼내올 때 유용한 자료구조이다. 항상 자식은 두개밖에 없으며, leaf의 가장 왼쪽부터 값을 채운다. 힙은 크게 최소힙과 최대 힙 두 가지가 있다. 최소 힙은 가장 작은 값이 루트이고, 최대 힙은 가장 큰 값이 루트이다. 힙은 완전 이진트리이지만 코드를 구현하기 위해서는 ..

[문제] 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/18110 18110번: solved.ac 5명의 15%는 0.75명으로, 이를 반올림하면 1명이다. 따라서 solved.ac는 가장 높은 난이도 의견과 가장 낮은 난이도 의견을 하나씩 제외하고, {5, 5, 7}에 대한 평균으로 문제 난이도를 결정한다. www.acmicpc.net [풀이] 백준 게시판에서 solvedac 계정을 발견했는데 유일하게 제출한 문제가 이거 한개라 궁금해서 풀어봤다. 왜케 쉬워?!?! 하고 풀었는데 런타임 에러가 나서 당황;; 파이썬 내장함수인 round가 생각보다 시간을 많이 잡아먹나보다 따라서 이번 문제는 round 함수를 직접 구현하는 문제이다. 그냥 반올림의 개념을 생각하면 쉽다. num의 소숫점 값이 ..