Algorithm
-
백준 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번 ..
-
[프로그래머스] Lv.3 단어 변환(DFS)Algorithm/대회 및 기타 2019. 10. 11. 23:48
문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 | 프로그래머스 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다. 예를 들어 begin이 hit, target가 cog, words가 [hot,dot,dog,lot,log,cog]라면 hit -> hot -> dot -> dog -> programmers.co.kr 문제 설명 두 개의 단어 begin, target과 단어의..