Algorithm

[문제] 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의 소숫점 값이 ..

[문제] 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 리스트에 추가해..

[문제] https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net [풀이] 이 문제는 동적 프로그래밍으로 풀어야 하는 문제이다. 동적 프로그래밍의 개발절차는 문제의 사례에 대해 해답을 주는 재귀 관계식 정립 작은 사례를 먼저 해결하는 상향식 방법으로 문제의 사례 해결 개발절차에 따르면 재귀 관계식을 정립해야 하기 때문에 우선 숫자 사이에서 규칙을 찾아보기로 했다. 5까지 직접 계산해 규칙을 찾아보니 이전 3개의 결과를 더한 숫자가 해당 숫자의 답이 되는 것을 발견했다. 이를 이용해 검증하기 위해 문제 예제에서 나온 7을 위의 규칙으로 계산해보니 44가..

[문제] https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net [풀이] 수를 최솟값으로 만들기 위해서는 마이너스가 나왔을 때 가장 큰 수를 빼면 된다. 따라서 최초의 - 연산자가 나오기 전까지는 전부 더하고, - 엱산자가 나온 이후에는 전부 빼준다. '55 - 50 + 40 - 10 + 20' 을 입력으로 받았을 때 split() 함수를 통해 expression = sys.stdin.readline().strip().split('-') prin..