Algorithm/BOJ(백준)
-
백준 4195 친구 네트워크(python, Union-Find)Algorithm/BOJ(백준) 2021. 8. 27. 17:00
* 문제 링크: https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net * 해결 방법: Union-find 1. 사람 수를 100,000명까지 입력 가능하지만, 완탐으로 풀면 시간초과. 따라서, 집합을 이용하여 해결 2. 비어있는 dict 하나를 구성 3. 입력받은 name1과 name2가 dict에 존재하지 않으면, 각 name을 key값으로 잡고 0번 인덱스부터 차근차근 저장 4. 집합을 구성할 arr=[-1] * (2*n+2) #사람 ..
-
백준 1717 집합의 표현(python, Union-Find)Algorithm/BOJ(백준) 2021. 8. 26. 23:06
* 문제 링크: https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net * 문제 해결방법: Union-Find 1. 입력이 100,000개까지 가능하므로, 완탐으로 풀면 무조건 시간초과 2. 0을 입력받는 족족 Union 3. 1을 입력받는 순간 Find(x) == Find(y): print("YES") import sys n, m = map(int, sys.stdin.readline().rstrip().spl..
-
백준 5568 카드 놓기(python, permutations)Algorithm/BOJ(백준) 2021. 8. 26. 21:09
* 문제 링크: https://www.acmicpc.net/problem/5568 5568번: 카드 놓기 예제 1의 경우 상근이는 11, 12, 21, 112, 121, 122, 212를 만들 수 있다. www.acmicpc.net * 문제 해결 방법: 순열의 조합 이용 1. itertools 라이브러리에 있는 permutations 함수 활용 2. 결과값을 저장할 set 생성 (이를 result로 명명) 3. 각 숫자를 문자로 입력받아, 각각을 리스트에 저장한 후 4. 저장된 리스트를 k개만큼 permutations(리스트, k) 실시 5. result.add("".join(per)) 6. result의 개수를 리턴 from itertools import permutations n, k = int(in..
-
백준 10814 나이순 정렬(python, lambda 사용)Algorithm/BOJ(백준) 2021. 8. 26. 03:46
* 문제 링크: https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net * 문제 해결방법: 정렬문제 1. 나이순으로 정렬하지만, 동일 나이는 이름 순 2. 따라서, sort의 key값을 lambda x:x[0]로 적용하여 정렬 실시 import sys n = int(sys.stdin.readline().rstrip()) info = [] for i in range(n): age, name = sys.stdin.readline().rstrip().split(..
-
백준 1593 문자 해독(python, 슬라이딩 윈도우)Algorithm/BOJ(백준) 2021. 8. 26. 02:27
취준 너무 싫다..... * 문제 링크: https://www.acmicpc.net/problem/1593 1593번: 문자 해독 첫째 줄에 고고학자들이 찾고자 하는 단어 W의 길이 g와 발굴된 벽화에서 추출한 문자열 S의 길이 |S|가 빈 칸을 사이에 두고 주어진다. (1≤g≤3000, g≤|S|≤3,000,000) 둘째 줄에 W, 셋째 줄에 S의 실 www.acmicpc.net * 해결과정: 슬라이딩 윈도우 방식 활용 1. 첫 번째 변수는 word, 두 번째 변수는 sentence로 정의 2. 소문자와 대문자의 개수(26 * 2)만큼의 크기를 가진 리스트 2개 생성 - 각각을 word_state, sentence_state로 정의 3. word의 각 문자를 소문자는 0~25번, 대문자는 26~51번 ..