본문 바로가기
반응형

알고리즘 풀이164

[백준 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.
[알고리즘] 고속 푸리에 변환(FFT) 알고리즘 정리 (python) ※ 시작하기 전내가 찾는 고속 푸리에 변환(FFT)은 알고리즘 문제 풀이를 해결하기 위한 FFT인데, 찾아보는 자료마다 이것 저것 푸리에 변환에 대한 공식이 적혀있고, Numpy를 이용해서 FFT 그래프를 그리고 해석하는 등 데이터 분석에 필요한 FFT 구현을 위주로 설명이 되어 있었다.그런 FFT 그래프 구현 등은 다른 블로그 등에서 매우 잘 다룬 자료들이 많으므로 다루지 않을 거고, 내가 다룰 내용은 FFT 알고리즘을 구현하여 문제를 풀 수 있도록 (백준 등) 고속 푸리에 변환 (FFT)과 고속 푸리에 역변환 (IFFT)를 내용으로 작성함 (코드 첨부)고속 푸리에 변환(FFT)📌고속 푸리에 변환?고속 푸리에 변환(FFT)란 이산 푸리에 변환(DFT)을 빠르게 진행하기 위해 만들어낸 알고리즘DFT는 .. 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.
[백준 21610] 마법사 상어와 비바라기 (python) https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 마법사 상어와 비바라기 문제 주어진 많은 요구사항을 따라 구현하는 문제 📌문제 접근 포인트 1. 조건이 생각보다 많다. 조건을 빼먹지 않도록 하나하나 구성해 주자. 2. 방향 d와 거리 s에 대해서 각각 체크를 해줄 수 있도록 for문을 이용해서 하나씩 탐색해 나가자 3. 중간에 visited를 사용하지 않고 리스트를 하나 더 만들어서 거기다 현재 좌표를 넣어 나중에 체크하는 식으로 구성하.. 2023. 4. 29.
[백준 2448] 별 찍기 - 11 (python) https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수)www.acmicpc.net별 찍기 - 11 문제별을 규칙에 맞게 찍도록 구현하는 문제재귀를 활용하여 해결할 수 있었다.📌문제 접근 포인트1. 별을 찍어보자. 별은 가운데가 비어있는 삼각형 모양으로 찍혀나간다.2. 3*2^n꼴로 숫자가 주어진다. 즉 n=3 일 때 해당하는 모양을 만들어주고 n/2를 진행하면서 재귀를 통해 탐색해 주자.3. 왼쪽 오른쪽 공백 구성에 맞게 출력해 주면 완성⚙️ 내가 푼 정답 코드 1# 위와 아래로 나눠서 별을 늘려나가는 방식def star(n): .. 2023. 4. 27.
반응형

티스토리툴바