자료구조&알고리즘
-
[알고리즘 문제 풀이][위상 정렬] 백준 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을 표현하는 방법 (여기에 ..
-
[알고리즘] 백준 폰으로도 풀 수 있는 문제 모음자료구조&알고리즘/알고리즘 - 언어 기초 2021. 10. 14. 23:51
solve.ac 최대 연속 문제 풀이를 위하여폰으로도 간단히 코드를 써서 제출할 수 있는 문제 모음 ※ 간단한 입,출력 등 문제 리스트(1) 백준 단계별로 풀어보기https://www.acmicpc.net/step(2) Solve.ac 단계별로 풀어보기https://solved.ac/class(3) 각종 대회 A 번 문제(전체) https://www.acmicpc.net/category(Olympiad) https://www.acmicpc.net/category/2 ※ 그 외 폰으로 간단히 제출 가능했던 문제들(확인하는 대로 추가할 예정) 1. 백준 24262 알고리즘 수업 - 알고리즘의 수행 시간 1https://www.acmicpc.net/problem/24262 24262번: 알고리즘 수업 - 알..
-
[알고리즘 문제 풀이][정렬] 백준 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 보다 무조건 ..
-
[알고리즘 문제 풀이][DFS] 백준 1012번 - 유기농 배추자료구조&알고리즘/알고리즘 - 기업 코딩 테스트 2021. 10. 9. 16:24
백준 1012번 유기농 배추입니다. (삼성 SW 코딩 테스트 유형 - DFS) - 문제 설명: https://www.acmicpc.net/problem/1012 - 문제 풀이: 본 문제는 기업 코딩 테스트 유형에서 많이 보이는 가벼운 함정이 있으므로, 문제 풀이를 보기 전에 먼저 문제를 풀어볼 것을 추천드립니다. 아래와 같은 배추밭이 있을 때, 배추 (1) 가 연속된 곳에는 지렁이를 하나만 두면 됩니다. 그래서 아래 예시의 경우, 뭉쳐있는 1이 5군데가 있으므로 5마리의 지렁이가 필요하게 됩니다. 1100000000 0100000000 0000100000 0000100000 0011000111 0000100111 연속된 배추를 구해야하기 때문에 본 문제는 DFS 로 풀이하면 됩니다. 왼쪽 위에서부터 탐색..
-
[알고리즘 문제 풀이][정렬] 백준 1026번 - 보물 (*)자료구조&알고리즘/알고리즘 - 언어 기초 2021. 10. 6. 14:47
백준 1026번 보물 문제입니다. (기초 수학 & 정렬 문제) - 문제 설명: https://www.acmicpc.net/problem/1026 - 문제 풀이: A 배열과 B 배열의 요소를 곱해서 합했을 때 결과가 최솟값이 나오도록 하는 문제입니다. 입력 // A 배열 1 1 1 6 0 // B 배열 2 7 8 3 1 출력 18 // = 1 1 0 1 6 // x 2 7 8 3 1 의 곱의 합 결과가 최소값이 되려면 곱셈은 큰 수를 곱하면 너무 커져버리기 때문에 가장 큰 수는 가장 작은 수와 곱해야합니다. 전체 합에서 가장 큰 수는 최대한 적게 포함시키고 가장 작은 수는 최대한 많이 포함시켜야합니다. 따라서 A 배열의 가장 큰 수는 B 배열의 가장 작은 수와 매칭되어야하고, A 배열의 가장 작은 수는 B..
-
[알고리즘 문제 풀이][확장유클리드] 백준 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를 구할 수 있습..