Algorithm/백준
-
[Python][백준] 9375번 패션왕 신해빈 문제 풀이Algorithm/백준 2022. 4. 14. 10:00
이 문제는 Python 딕셔너리(이하, dict) 자료구조와 조합론을 알면 쉽게 풀 수 있다. dict는 hashtable, hashmap 자료구조를 Python에서 구현한 것으로 {key: value}로 구성되어있다. dict를 이용하면 O(1) 시간복잡도로 데이터에 접근할 수 있어 매우매우 빠르다. 신해빈씨의 옷의 종류(c_type)를 key로 두고 옷의 이름(name)을 리스트로 만들어 value로 만들어 clothes를 정의하였다. 옷 입는 경우의 수를 구하자 옷의 종류에서 0개 혹은 1개를 선택해서 조합한 경우의 수를 구하고, 각 옷의 경우의 수를 모두 곱하면 된다. 아무것도 안 입는 경우 1을 빼고 출력하는 것을 잊지말자. # key0: [value0, value1...] # key1: [va..
-
[Python][백준] 문자열 탐색 알고리즘 공부하기 | 백준 5525번 50점Algorithm/백준 2022. 3. 26. 10:00
import sys def P5525(): n = int(input()) pn = 'I' + 'OI' * n length = int(input()) string = input().strip() sum, x = 0, 0 while x < length: if pn in string[x:]: x += 1 sum += 1 x += 1 print(sum) if __name__ == '__main__': input = sys.stdin.readline P5525() 내가 푼 문제이다. 50점 나왔다. 왜 50점 나왔나 했더니 시간 복잡도 문제란다. 3학년 때 피똥싸며 들은 알고리즘 강의에 나온 문자열 탐색 알고리즘을 사용할 때인가...! 문자열 탐색 알고리즘은 여러가지가 있다. 내가 짠 코드는 순차탐색이다. O(n..
-
[Python][백준] 17219번 비밀번호 찾기 문제 풀이Algorithm/백준 2022. 3. 19. 10:00
이 문제는 자료구조와 해시를 사용한 집합과 맵이 핵심 개념이다. 이 문제를 풀때, 일반적인 리스트로 풀면 시간초과의 늪에 빠질 것이다. 이 때 사용해야 할것이 Python의 dictionary 자료구조이다. (c++, java의 map) dictionary는 키(key)와 값(value)이 쌍을 이루는 자료구조로, 순서와 상관없이 키 값으로 한 번에 값을 불러올 수 있다. dictionary는 해시로 이루어져있기 때문에, 값을 불러 올 때의 시간복잡도는 O(1)이다. 이를 코드로 구현하면 다음과 같다. import sys def P17129(): n1, n2 = map(int, input().split()) # 사이트의 주소와 비밀번호 입력 sites = {} for _ in range(n1): s, p..
-
[Python][백준] 11723번 집합 문제 풀이 | 비트마스킹이 뭐여Algorithm/백준 2022. 3. 16. 10:00
https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 이 문제는 정말 어려웠다 이 문제는 '비트마스킹'이라는 것을 모르면 메모리 초과의 늪에 빠지는 문제이다. 다른 사람들은 Python의 set 자료구조를 이용하여 풀기도 하던데, 그것은 문제의 출제의도와 다른 것 같으니 배제하고 비트마스킹을 이용한 풀이를 소개하겠다. 비트마스킹이란? 비트마스킹(Bitmasking)은 비트, 즉 0과 1, True와 False를 이용하여 문제를 해결하는 것이다. 11723번 문제의 조건을 보면 공집합 ..
-
[Python][백준] 9095번 문제 1, 2, 3 더하기 해결 | DP는 어려워Algorithm/백준 2022. 3. 12. 10:00
동적 계획법(dynamic programming, DP) DP 큰 문제를 작은 문제로 나누어 푸는 알고리즘이다. DP의 핵심 작은 부분을 기억하는 것이다. 왜냐하면 Optimal Structure가 있는 문제를 풀 때 구조를 새로 구할 필요없이, 방금 전 기억한 작은 부분을 불러오면 더 빠르고, 효율적으로 구할 수 있기 때문이다. 오늘은 DP를 이용하여 푼 1, 2, 3 더하기 문제를 풀어보겠다. lines = int(input()) cases = list(int(input()) for _ in range(lines)) for c in cases: dp = [0, 1, 2, 4] + [0 for _ in range(c)] for i in range(4, c+1): dp[i] = dp[i-3] + dp[i..