백준 알고리즘
-
[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 노드로 향하는 이전 노드가 있을 것이..
-
[정수론] 분할 정복(재귀)를 이용한 거듭제곱 - 파이썬 코드 및 설명백준 알고리즘/Theories 2023. 9. 25. 18:50
목표 - 분할 정복(재귀)를 이용하여 어떤 수의 거듭제곱을 구하는 방법을 알아본다. 과정 어떤 수의 거듭제곱을 어떻게 구할 수 있을까요? 다른 말로, 어떤 수 A를 N번 곱한 수를 어떻게 구할 수 있을까요? 단순하게 생각하면 실제로 A라는 수를 N번 곱하여 얻을 수 있습니다. 허나, N이 너무 클 때는 그 수를 일일이 N번 곱해야하기 때문에 많은 양의 연산을 피할 수 없습니다. 분할 정복(재귀) 기법을 사용하면 연산의 횟수를 극단적으로 줄일 수 있는데요. 분할 정복(재귀) 기법을 이용해 N번의 연산을 logN번으로 줄이는 방법에 대해 알아보겠습니다. 이해를 위해 어떤 수 A를 2라고 가정해보겠습니다. 2의 N제곱 수는 다음과 같이 나타낼 수 있습니다. 2의 N제곱수는 위와 같이 짝수 홀수 여부에 따라 다..
-
[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번째) 계단까지 오르는 게임입니다. 단, 주어진 조건이 다음과 같이 존재합니다. 계단은 한 번에 한 개씩 또는 두 개씩 오를 수 있다. 연속된 세 개의 계단은 밟아선 안된다. 마지막 계단은 반드시 밟아야 한다. 이렇게 계단을 오를 때, 밟은 계단의 합의 최대값을 구해 출력하는 프로그램을 만들어야 합니다. 단순히 생각해서 현재 가장 좋은 후보를 고르는 탐욕법 알고리즘으로 해당 문제를 풀 수 있을까? 라는 생각이 들었지만, 다음과 같은 반..
-
[코드트리 챌린지] 코드트리로 코딩 테스트 준비하기 - 1백준 알고리즘/CodeTree Challenge 2023. 9. 11. 15:13
자주 사용하는 코딩 테스트 대비 학습 사이트 코드트리에서 블로그 챌린지를 시작했다! 평소에 혼자 공부하는 것을 잘 하지 못하는 나는 이 기회가 좋은 기회로 생각돼서 블로그 챌린지에 참가하게 됐다. 블로그 챌린지 참가 방법 및 보상은 다음과 같다! 코드트리 챌린지 소개 및 보상 지난 방학에 재학 중인 학교에서 코드트리 플랫폼을 활용해 특강과 알고리즘 캠프를 진행했었다. 캠프를 진행하며 전체적으로 느낀 것은 "알고리즘과 자료구조를 알고있다고 해서 코딩 테스트를 볼 수 있는게 아니다."라는 것을 뼈저리게 느꼈다. 코딩 테스트는 짧은 시간 안에 문제를 풀어내야하는 시험이기 때문에 꾸준한 연습이 필요한 시험이다. 많은 사람들이 그렇게 느낄지는 미지수이지만, 적어도 나는 그렇게 느꼈다. 단적인 예로 작년 겨울에 진..
-
[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를 진행하며 아기 상어의 크기보다 작거나..