알고리즘
[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를 ..
![[Software Maestro 13기] 소프트웨어 마에스트로 2차 코딩테스트 후기](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fcb9MC8%2FbtrwpuWUX3o%2Fi3L2lQDhdtW4Ep656uOdKK%2Fimg.png)
[Software Maestro 13기] 소프트웨어 마에스트로 2차 코딩테스트 후기
2022.03.19 14:00 ~ 16:00 소프트웨어 마에스트로 13기의 두번째 코딩테스트가 진행되었습니다. 알고리즘 3개, SQL 1개, 웹 1개 문제가 나왔으며 푼 문제 수를 늘리기 위해 비교적 빨리 풀 수 있는 SQL 문제를 먼저 풀었습니다. 알고리즘 문제들은 1차 테스트보다 난이도가 조금 올라갔으며, 웹은 저번 테스트와 마찬가지로 풀지 않았습니다. 부분 점수가 있다곤 하는데 제 생각에 통과 커트라인이 2~3문제 아닐까 싶습니다. 풀이 순서 : 문제 4 => 문제 1 => 문제 2 => 문제 3 문제 1 (알고리즘) : 조합(비트마스크) 원래대로 푼다면 시간초과가 나올 방법으로 풀었습니다. 최대 체크 개수가 16개이므로 비트마스크를 활용해서 풀이하였습니다. 비트마스크를 사용하지 않아도 풀 수 있지..
[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 ..
![[Software Maestro 13기] 소프트웨어 마에스트로 1차 코딩테스트 후기](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FlRex6%2Fbtru7rBGPQk%2FxegR3Tk2ejc23GWpK9kNP1%2Fimg.png)
[Software Maestro 13기] 소프트웨어 마에스트로 1차 코딩테스트 후기
2022. 03. 05 14:00 ~ 16:00 소프트웨어 마에스트로 13기의 첫번째 코딩테스트가 진행되었습니다. 알고리즘 6개, SQL 1개, 웹 1개의 문제가 나왔으며 알고리즘 5문제 SQL 1문제가 풀었는데, 짧은 테스트 시간동안 많은 문제를 풀기 위해서 문제를 살펴본 후 빨리 해결되지 않을 것 같으면 넘어가고 다른 문제로 시도하였습니다. 문제 자체는 제출해도 정답인지가 나오지 않아 몇 문제를 맞췄는지는 모르겠지만 풀이시간이 부족하여 예외만 몇 가지 확인해본 후 제출하여 조금이나마 예외를 제외하였습니다. 풀이 순서 : 문제 1 => 문제 3 => 문제 7 => 문제 4 => 문제 5(포기) => 문제 6 => 문제 2 문제 1 (알고리즘) : 단순 문자열 구현 처음에 보았을 때 트라이 문제인가? 싶..
[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..