본문 바로가기
반응형

알고리즘 풀이/백준125

[백준 7677] Fibonacci (python) https://www.acmicpc.net/problem/7677 7677번: Fibonacci For each test case, print the last four digits of Fn. If the last four digits of Fn are all zeros, print ‘0’; otherwise, omit any leading zeros (i.e., print Fn mod 10000). www.acmicpc.net Fibonacci 문제 -1을 받을 때까지 반복하고, 숫자의 마지막 4자리를 출력하는 문제 분할정복을 이용하여 해결할 수 있었다. 📌문제 접근 포인트 1. 먼저 피보나치수열을 구해보자. N의 크기가 매우 큰 숫자이기에 재귀 or DP로는 절대로 시간 안에 들어오기 어려운 구조다... 2023. 5. 4.
[백준 10026] 적록색약 (python) https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 적록색약 문제 RGB로 나누어진 영역의 개수와, 적록 색약이어서 RRB 혹은 GGB로만 볼 수 있을 때 나누어진 영역의 개수를 구하는 문제 BFS 개념을 이용해서 해결할 수 있었다. 📌 문제 접근 포인트 1. 나누어진 영역의 수를 구하기 위해서 BFS를 이용한 탐색을 진행해 주자, 진행 과정에서 방문 여부를 체크하기 위한 리스트를 하나 지정해 주자. 2. 처음 주어진 리스트를 이용해서 볼 .. 2023. 5. 2.
[백준 1461] 도서관(python) https://www.acmicpc.net/problem/1461 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net 도서관 문제 0의 위치에서 놓여있는 책들을 m개 들어서 꽂으러 이동할 때 걸리는 최소 시간을 구하는 문제 그리디 개념과 정렬 개념을 활용하여 해결할 수 있었다. 📌 문제 접근 포인트 1. 책을 들고 0의 지점에서 M개를 들고 꽂으러 이동하러 다녀야 한다. 즉, 책을 꽂고 다시 0으로 돌아와야 하니 2배의 거리만큼 이동해야 한다 단, 마지막 이동을 할 때는 제자리를 돌아올 필요가 없으니 1번만 이동해도 .. 2023. 5. 2.
[백준 1067] 이동 (python) https://www.acmicpc.net/problem/1067 1067번: 이동 N개의 수가 있는 X와 Y가 있다. 이때 X나 Y를 순환 이동시킬 수 있다. 순환 이동이란 마지막 원소를 제거하고 그 수를 맨 앞으로 다시 삽입하는 것을 말한다. 예를 들어, {1, 2, 3}을 순환 이동시키면 www.acmicpc.net 이동 문제 X와 Y의 모든 순환 이동 후에 점수 S가 X[0]Y[0] + X[1][Y[1] +... X[N-1]Y[N-1]의 최대 값을 구하는 문제 고속 푸리에 변환 (FFT)을 이용한 Convergence를 통해 해결할 수 있었다. ※ 고속 푸리에 변환 이론에 대한 간략한 설명 https://edder773.tistory.com/229 [알고리즘] 고속 푸리에 변환(FTT) 알고리즘 .. 2023. 4. 30.
[백준 17114] 하이퍼 토마토 (python) https://www.acmicpc.net/problem/17114 17114번: 하이퍼 토마토 첫 줄에는 문제의 설명에서 창고의 크기를 나타내는 자연수 m, n, o, p, q, r, s, t, u, v, w가 주어진다. 단, 1 ≤ mnopqrstuvw ≤ 106 이다. 둘째 줄부터는 창고에 저장된 토마토들의 정보가 주어진다. 창 www.acmicpc.net 하이퍼 토마토 문제 11차원 창고에서 토마토가 점점 익어갈 때의 최종적으로 토마토가 익는데 며칠이 걸리는지 계산하는 문제 11차원 리스트를 이용한 BFS를 통해 해결할 수 있었다. 📌문제 접근 포인트 1. 11차원으로 구성된 토마토 창고를 먼저 만들어주자. 입력받은 값들을 이용해서 만들 수 있다. 2. 주어진 요구조건대로 하나의 토마토가 인접한 .. 2023. 4. 30.
[백준 14890] 경사로(python) https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 경사로 문제 요구 조건에 맞게 경사로를 놓아서 지나갈 수 있는지 횟수 체크하는 구현 문제 📌 문제 접근 포인트 1. 문제 요구사항을 잘 따져주자. 요구사항이 많아서 헷갈릴 수 있다. 2. 가로 방향과 세로 방향을 모두 따져줘야 하고, 가로와 세로 둘 다 같은 방식으로 탐색을 하면 되니 함수를 만들어줘서 구성해 보자. 3. 요구 조건에 맞게 차이가 1보다 큰 경우와 왼쪽, 오른쪽이 더 클 경우로 나눠서, 각각 경사로를 설.. 2023. 4. 29.
반응형

티스토리툴바