자료구조&알고리즘/알고리즘 - 대회 알고리즘
-
[알고리즘 문제 풀이][조합] 백준 17205번 - 진우의 비밀번호자료구조&알고리즘/알고리즘 - 대회 알고리즘 2022. 1. 19. 00:10
백준 17205번 진우의 비밀번호 문제입니다. (조합론) - 문제 설명: https://www.acmicpc.net/problem/17205 - 문제 풀이: 가능한 비밀번호가 최대 3자리라면 a, aa, aaa, aab, aac, ..., azy, azz, b, ba 이런 식으로 나타나게 됩니다. 그러면 매 자리마다 가능한 경우의 수를 합해주면 됩니다. a b ... z ===> 여기가 총 26개 a a a b a c a ... a z ====> 여기는 a~z * a~z 를 생각하면 총 26 * 26개 a a a a a b a a c a a ... a a z ======> 여기는 a~z * a~z * a~z 를 생각하면 총 26 * 26 * 26개가 됩니다. 그렇다면 만일 최대 길이가 3이고, 문제에서 ..
-
[알고리즘 문제 풀이][슬라이딩 윈도우] 백준 15961번 - 회전 초밥자료구조&알고리즘/알고리즘 - 대회 알고리즘 2022. 1. 5. 00:02
백준 15961번 회전 초밥 문제입니다. (투 포인터 & 슬라이딩 윈도우) - 문제 설명: https://www.acmicpc.net/problem/15961 - 문제 풀이: 회전 초밥 접시들을 연속해서 k 개씩 먹고, c 라는 초밥을 하나 먹을 수 있는 쿠폰이 있을 때, 최대의 가짓수를 찾아야합니다. 최대의 가짓수를 위해서는 일반적으로 k 개 먹은 초밥 중에 같은 번호의 초밥이 하나도 없어야합니다. 또한 c 쿠폰을 사용할 수 있도록 c 라는 번호의 초밥도 없어야합니다. sliding window 라는 방법으로, k 개 범위를 한칸씩 이동하면서 해당 범위 안에 초밥 가짓수가 줄어들었는지, 증가했는지를 체크합니다. - 코드: N, d, k, c = map(int, input().split()) dish =..
-
[알고리즘 문제 풀이][탐욕] 백준 2109번 - 순회강연자료구조&알고리즘/알고리즘 - 대회 알고리즘 2021. 12. 6. 22:54
백준 2109번 순회강연 문제입니다. (탐욕 알고리즘 or 우선순위 큐) - 문제 설명: https://www.acmicpc.net/problem/2109 - 문제 풀이: 본 문제는 탐욕 알고리즘 혹은 우선순위 큐로 풀이 가능합니다. (시간이 2초이고, 입력 크기가 10,000 이므로 N^2 알고리즘 가능) 탐욕 알고리즘을 쓰는 경우에는 pay 가 큰 값부터 작은 값으로 정렬해주고 (d일 이내에 와야한다는 조건 때문에 오름차순이 아닌 내림차순으로 풀이하게 됩니다), pay 가 큰 값부터 우선적으로 day 에 지정해줍니다. 그런데, day 값을 그 기간 안에 오기만 하면 되는 것이기 때문에 1일차부터 주어진 day 까지 다 확인하면서 지정해줍니다. (자세한 설명: https://steady-coding.t..
-
[알고리즘 문제 풀이][위상 정렬] 백준 2252번 - 줄 세우기자료구조&알고리즘/알고리즘 - 대회 알고리즘 2021. 10. 31. 21:45
백준 2252번 줄 세우기 문제입니다. (위상 정렬 문제 = Topological Sort) - 문제 설명: https://www.acmicpc.net/problem/2252 - 문제 풀이: BFS, DFS 같은 그래프를 배운 후에, 그래프를 이용한 정렬 문제를 공부해보게 됩니다. 방향성이 있는 그래프를 이용한 정렬을 위상 정렬, Topological 이라고 부릅니다. 문제를 보면, 항상 선후 관계를 줍니다. (줄 세울 때 A가 B보다 먼저 나와야하는 조건이 있다거나, 대학교에서 과목을 듣는데 A 과목이 B 과목의 선수 과목이거나...) 백준 문제에 있는 제일 첫번째 예제를 그래프로 표현하면 다음과 같습니다. 1이 3보다 먼저 와야하고, 2가 3보다 먼저 와야합니다. 그러면 1이나 2가 가장 먼저 나오면..
-
[알고리즘 연습] 2021년도 10월 셋째주 학습 (D번 문제 풀이)자료구조&알고리즘/알고리즘 - 대회 알고리즘 2021. 10. 22. 00:17
AtCoder Beginner Contest 222 (D번 문제): DP Codeforces Round #748 (Div.3) (D1번 문제): 유클리드 호제법 대회를 진행하면 항상 A, B, C번을 풀고 D 번에서 막히기 때문에 시간을 내서 D번 정식 풀이를 학습해보았다. 1. AtCoder Beginner Contest 222 (D번 문제) 문제 https://atcoder.jp/contests/abc222/tasks/abc222_d 풀이 조건이 복잡하기 때문에 모든 경우의 수를 단순히 곱해서 구할 수 없다. 재귀함수를 통해 일일히 가능한 경우를 세면 엄청나게 많은 가짓수가 있기 때문에 시간 초과가 난다. 이미 구한 값을 이용하여 다음 값을 계산하는 DP 접근 방식이 필요하다. 직접 예시를 만들어보면..
-
[알고리즘 문제 풀이][DP] 백준 9095번 - 1, 2, 3 더하기자료구조&알고리즘/알고리즘 - 대회 알고리즘 2021. 10. 16. 19:26
백준 10989번 1, 2, 3 더하기 문제입니다. (DP 문제) - 문제 설명: https://www.acmicpc.net/problem/9095 - 문제 풀이: 정수를 1과 2와 3의 합으로 나타내야합니다. 본 문제에서 4를 나타내는 방법을 표현한 것을 보면 순서가 상관 있는 것을 볼 수 있습니다. (1 + 3 과 3 + 1 을 따로 침) 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 저는 이 문제를 DP를 공부하기 위해서 풀었기 때문에, 큰 범위부터 작은 범위로 줄여나가려고 했습니다. 예를 들어, 위에 주어진 값을 끝에가 1이 더해진 것과, 2가 더해진 것과 3이 더해진 것으로 묶을 수 있습니다. 그러면 이 문제는 4를 표현하는 방법을 구하는 것은 3을 표현하는 방법 (여기에 ..
-
[알고리즘 문제 풀이][정렬] 백준 10989번 - 수 정렬하기 3자료구조&알고리즘/알고리즘 - 대회 알고리즘 2021. 10. 11. 23:11
백준 10989번 수 정렬하기3 문제입니다. (정렬 문제) - 문제 설명: https://www.acmicpc.net/problem/10989 - 문제 풀이: 본 문제를 풀 때 중요한 것은 입력 제한을 보고 가능한 정렬 방법을 떠올리는 것입니다. 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 본 문제의 메모리 제한은 8MB 입니다. 그런데 들어오는 수의 개수가 10,000,000 개이기 때문에 이걸로 배열을 만든다고 하면 4 byte * 10000000 = 40 MB 가 필요합니다. 그래서 들어오는 수를 정렬하는 방식으로는 풀 수가 없습니다. 대신 들어오는 수가 10000 보다 무조건 ..
-
[알고리즘 문제 풀이][확장유클리드] 백준 14565번 - 역원(Inverse) 구하기자료구조&알고리즘/알고리즘 - 대회 알고리즘 2021. 10. 4. 14:02
백준 14565번 역원(Inverse) 구하기 문제입니다. (유클리드 호제법 + 확장된 유클리드 호제법 문제 Extended Euclidean Algorithm) ※ 본 게시글에는 확장된 유클리드 호제법의 원리에 대한 설명은 포함되어있지 않습니다. 문제 풀이에 대한 내용만 정리되어있습니다. - 문제 설명: https://www.acmicpc.net/problem/14565 - 문제 풀이: 본 문제는 덧셈역과 곱셈역을 출력하는 문제입니다. (1) 덧셈역 (a+b) mod n = 0 이 나오는데, 첫번째 입력인 N 26과 A 11을 넣어보면 (11 + b) mod 26 = 0 이 나오는 것을 찾는 것입니다. 그러면 당연히 26 % 26 을 하면 0이 나오므로 b는 26 - 11 로 쉽게 15를 구할 수 있습..