알고리즘
[BOJ / 그리디 선분교차] 25315 N수매화검법
https://www.acmicpc.net/problem/25315 25315번: N수매화검법 화산파의 장로 우경은 새로운 무공 N수매화검법을 창안했다. N수매화검법은 이십사수매화검법을 발전시킨 검법으로 총 $N$개의 베기(검으로 무언가를 베는 동작)로 이루어진다. N수매화검법은 2 www.acmicpc.net 25315 N수매화검법 알고리즘 : 그리디 / CCW(선분교차판정) 문제 티어 : 골드 II 2022 UCPC 예선에서 총 세 문제 풀이를 시도하였는데 솔브된 문제 중 유일하게 혼자 푼 문제이다. 여러번의 베기를 통해 이후 행할 겹치는 베기의 수만큼 추가 내공이 필요로 하기 때문에 그리디하게 작은 내공을 가진 베기부터 수행한다. (어차피 순서에 상관없이 겹치기 때문에) 선분 교차 판정은 CCW를 ..
[BOJ / 브루트포스] 15898 피아의 아틀리에 ~신비한 대회의 연금술사~
https://www.acmicpc.net/problem/15898 15898번: 피아의 아틀리에 ~신비한 대회의 연금술사~ "피아의 아틀리에 ~신비한 대회의 연금술사~"는 가난한 연금술사 피아의 성장스토리를 담은 게임이다. 이 게임의 가장 중요한 부분은 "대회"인데, 연금술로 높은 품질의 물건을 만들어 상금을 타 www.acmicpc.net 15898 피아의 아틀리에 ~신비한 대회의 연금술사 알고리즘 : 구현 / 브루트포스 문제 티어 : 골드 I UCPC 2018 예선 문제 중 하나인 문제이다. 배열돌리기와 순열을 이용한 간단한 구현 문제이다.. 그러나 배열돌리기를 다른데서 퍼왔다가 잘못된 코드인 바람에 디버깅이 오래걸렸다. (설마 여기서 났겠어 했다가.. ㅋㅋ) 골드1치고는 되게 쉬운 문제인 것 같다..
[BOJ / 구현] 1107 리모컨
https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 1107 리모컨 알고리즘 : 구현 반례가 상당히 많은 구현 문제입니다. 예외처리를 잘 해주어야하는데 그렇기 때문에 정답률 또한 낮은 문제입니다. 구현 난이도 자체는 낮은 편이라 코딩 테스트에 나온다면 킬러 문제가 될거라고 생각됩니다. 0에서 일어나는 버그가 많아 참고하시길 반례 남기겠습니다. 반례 1 9 0 1 2 3 4 5 6 7 8 9 0 4 0 1 2 3 5 ..
[BOJ / DP] 17069 파이프 옮기기 2
https://www.acmicpc.net/problem/17069 17069번: 파이프 옮기기 2 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 17069 파이프 옮기기 2 알고리즘 : 우선순위큐, DP, 메모이제이션 3가지 파이프 상태에서 갈 수 있는 경우를 저장해서 3 * n * n 크기의 DP 배열을 만들어서 풀이합니다. 시간 초과를 피하기 위해 모든 경우의 수를 하는 것이 아닌 같은 경우인 곳을 합산하여 처리하고 작은 인덱스부터 처리하기 위해 우선순위 큐를 사용합니다. #include #in..
[BOJ / 백트래킹] 1799 비숍
https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 1799 비숍 알고리즘 : DFS, 백트래킹, 아이디어 일반적인 백트래킹을 사용하면 시간초과를 겪게되고, 그리디로 풀면 무수한 틀렸습니다를 주는 문제이다. 체스판의 검은 판과 하얀 판에 있는 비숍끼리는 절대 만날 수 없다는 걸 전제로 두어 나눠서 계산하면 시간 초과를 벗어날 수 있다. 비숍을 둘 때 현 대각선에 비숍을 놓은 적이 있는 지를 O(1)에 확인하기 위해서 xCnt, yCnt를 이용하여 대각선에 ..
[BOJ / 트라이] 14725 개미굴
https://www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 www.acmicpc.net 14725 개미굴 알고리즘 : 자료구조, 트라이, 맵 맵은 레드블랙트리 기반으로 이루어진 자료구조이기에 자동으로 내부정렬이 됩니다. 이 문제에서는 정렬을 하여 자식들을 출력하여야 되는 트라이 구조이기 때문에 맵을 사용하여 자식들을 관리하면 됩니다. #include #include #include using namespace std; struct Node { strin..
[BOJ / BFS] 12851 숨바꼭질 2
https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 12851 숨바꼭질 2 알고리즘 : BFS / 메모이제이션 일반 BFS 문제에 최단경로의 개수를 추가하여 한 번 뒤섞은 문제입니다. 수빈이와 동생이 같은 자리일 경우도 한 가지의 경우로 치는 것과, 출력 사이에 '\n'이 있음을 유의하지 않아 정답률이 낮은 문제인 것 같습니다. ㅠㅠ 범위 초과에 유의하며 푸시면 좋습니다. #include #in..
[BOJ / BFS] 2638 치즈
https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 2638 치즈 알고리즘 : 플러드필, BFS, 메모이제이션 1,1은 무조건 바깥 공기이므로 1,1 공기로 플러드필을 통해 바깥 공기들을 구분합니다. 이 과정 중 다음 세대에 녹을 치즈를 판별하고, ( 녹을 치즈 구분 / 안쪽 공기 구분 )을 반복하며 문제를 해결합니다. #include #include #include using namespace std; #define ..