백준 알고리즘/Problems
-
[Trouble Shooting] AWS CloudFront(CDN)을 사용할 때 발생하는 CORS 문제 (헤더 포워딩)백준 알고리즘/Problems 2024. 7. 8. 16:48
오류 환경Chrome browserAWS CloudFrontSpring Boot(Spring Security)오류 내용 브라우저에서 서버로 요청을 보낼 때 CORS 오류 발생했다. (도메인 이름은 변경했다)Access to fetch at 'https://example.com/api/resource' from origin 'https://yourdomain.com' has been blocked by CORS policy: Response to preflight request doesn't pass access control check: No 'Access-Control-Allow-Headers' header is present on the requested resource. 기존 프로젝트에 Spri..
-
[BOJ/1719] 택배 - 풀이 및 코드백준 알고리즘/Problems 2024. 5. 9. 14:54
문제 링크https://www.acmicpc.net/problem/1719접근 방법다익스트라 알고리즘은 "어떤 노드까지의 최단거리를 알 때, 그 노드와 연결된 노드들의 최단 거리를 갱신"하며 정답을 구하는 알고리즘이다.그러한 알고리즘의 특징을 이용해서 다음과 같은 접근을 하였다.다익스트라 알고리즘을 진행할 때, 알고리즘의 효율성을 위해 우선순위 큐를 사용한다. 우선순위 큐에는 최단 거리가 갱신된 노드가 담긴다.우선순위 큐에서 어떤 노드 A가 나온다고 가정해보자. (우선순위 큐의 top이 노드 A)노드 A로 향하는 최단 거리는 확정되었다. (큐의 내용과 실제 노드 A의 최단 거리를 비교해야함)A 노드가 다익스트라 알고리즘을 실행한 루트 노드가 아니라면 루트 노드에서 A 노드로 향하는 이전 노드가 있을 것이..
-
[BOJ/9663] N-Queen - 풀이 및 코드백준 알고리즘/Problems 2023. 9. 23. 15:51
9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 N-Queen 문제는 체스 말 중 퀸 N개를 서로 공격할 수 없는 곳에 두는 문제입니다. 퀸은 수직, 수평, 대각 방향으로 공격을 할 수 있다는 특징이 있기 때문에 모든 경우의 수를 따져보면 됩니다. 다만, 주어지는 체스 보드의 크기가 최대 14*14로, 체계없이 퀸을 놓으며 가능성을 따지면 최대 (14 * 14)C14의 경우의 수를 따지게 되기 때문에 나름의 최적화를 해주어야 합니다. 우선, N의 값이 1부터 14로 동적으로 정해지기 때문에 일반적인 브루트 포스 알..
-
[BOJ/2579] 계단 오르기 - 풀이 및 코드백준 알고리즘/Problems 2023. 9. 17. 18:52
2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 풀이 계단 오르기 게임은 마지막(N번째) 계단까지 오르는 게임입니다. 단, 주어진 조건이 다음과 같이 존재합니다. 계단은 한 번에 한 개씩 또는 두 개씩 오를 수 있다. 연속된 세 개의 계단은 밟아선 안된다. 마지막 계단은 반드시 밟아야 한다. 이렇게 계단을 오를 때, 밟은 계단의 합의 최대값을 구해 출력하는 프로그램을 만들어야 합니다. 단순히 생각해서 현재 가장 좋은 후보를 고르는 탐욕법 알고리즘으로 해당 문제를 풀 수 있을까? 라는 생각이 들었지만, 다음과 같은 반..
-
[BOJ/1016] 제곱 ㄴㄴ 수 - 풀이 및 코드백준 알고리즘/Problems 2023. 9. 3. 20:43
1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 문제 풀이 "제곱 ㄴㄴ수"란, 정수 X의 약수 중 제곱수가 없는 수를 의미합니다. 어떤 수 K에 제곱수가 존재하는지 존재하지 않는지를 따지기 위해서는 소인수 분해를 진행하면 됩니다. 소인수 분해를 하고 2개 곱해진 소수가 존재하는가?를 확인하면 되기 때문이죠. 어떤 수 K를 나이브하게 소인수 분해하는데에는 O(K)의 시간복잡도가 소요된다고 알려져있습니다. 그러나 문제 조건 중 min값이 최악의 경우 1조이며, max값은 최악의 경우 min보다 백..
-
[BOJ/16236] 아기 상어 - 풀이 및 코드백준 알고리즘/Problems 2023. 8. 26. 00:41
16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 풀이 구현 문제로, 요구사항을 정리하면 다음과 같습니다. 아기 상어는 먹을 수 있는 물고기가 없으면 프로그램을 종료하고 정답을 출력한다. 정답은 아기 상어가 물고기를 먹으며 소모한 시간(초)이다. 아기 상어가 먹을 수 있는 물고기를 찾는 방법은 다음과 같다. 1. 현재 아기 상어의 위치에서 BFS를 진행한다. 2. BFS를 진행하며 아기 상어의 크기보다 큰 물고기는 통과할 수 없다. (큐에 삽입 X) 3. BFS를 진행하며 아기 상어의 크기보다 작거나..
-
[BOJ/1005] ACM Craft - 풀이 및 코드 (런타임 에러 해결법)백준 알고리즘/Problems 2023. 8. 22. 20:16
1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 문제 풀이 비슷한 문제인 게임 개발(https://highlaw00-dev.tistory.com/44) 문제를 이미 풀었습니다. 완전탐색의 시간복잡도와 사이클의 유무에 관해 포스팅해두었습니다. 이번 풀이에서는 파이썬의 특징으로 인해 발생하는 런타임 에러에 대해 간략히 다뤄보겠습니다. 재귀적으로 선행 건물의 비용을 구해야하기 때문에 재귀를 여러번 할 가능성이 존재합니다. 백준 채점 서버에서는 파이썬의 최대 재귀 횟수가 1000회로 지정되어 있습니다. 본 문제..
-
[BOJ/1504] 특정한 최단 경로 - 풀이 및 코드백준 알고리즘/Problems 2023. 8. 22. 20:07
1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 문제 풀이 1번 노드부터 N번 노드까지의 최단 경로를 구하는 문제입니다. 단, 주어지는 v1, v2 노드를 중간에 반드시 방문해야하는 문제입니다. 노드의 수가 800개 이하이기 때문에 O(N^2)의 알고리즘으로 풀 수 있습니다. 또, 주어지는 간선의 가중치들은 모두 1000 이하의 자연수 라는 조건이 존재합니다. 문제 조건 중, 한 번 지나간 간선이나 정점을 다시 방문할 수 있다는 조건이 있기 때문에 다음과 같이 접근..