Algorithm
-
[C][백준] 1158번 요세푸스 문제 : C, 원형연결리스트로 해결Algorithm/백준 2022. 9. 1. 19:35
#include #include typedef struct _node { int data; struct _node *next; struct _node *prev; }node; int N,M; node *head; node *tail; node *cur; void init() { head = (node*)malloc(sizeof(node)); tail = (node*)malloc(sizeof(node)); head->data = 'H'; tail->data = 'T'; head->next = tail; head->prev = tail; tail->next = head; tail->prev = head; cur=head; } int main() { scanf("%d%d",&N,&M); printf(""); ..
-
[Python][백준] 누적 합 알고리즘 | 11659번 구간 합 구하기 4 시간초과 해결Algorithm/백준 2022. 4. 18. 10:00
누적 합(prefix sum)이란? 배열에서 특정 구간의 합을 구할 때 사용하는 방법이다. 만약 이때 일반적인 순회법을 사용하면 시간복잡도가 O(n^2)일 것이다. 하지만 누적 합을 사용하면 O(n)의 시간복잡도를 가진다. # 리스트를 슬라이싱하고, 합을 구하는 소스코드... 시간초과 import sys def P11659(): N, M = map(int, input().split()) numbers = [0] + list(map(int, input().split())) for _ in range(M): s, e = map(int, input().split()) print(sum(numbers[s-1:e])) if __name__ == '__main__': input = sys.stdin.readline..
-
[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..