https://www.acmicpc.net/problem/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이 www.acmicpc.net 해설 세그먼트 트리 문제입니다. 1. 자료의 수정이 많이 일어난다는 점 2. 요구되는 숫자가 매우 크다는 점 을 미루어 보어 세그먼트 트리임을 알 수 있습니다. 세그먼트 트리 정의하기 이 문제에서 요구하는 점은 2가지입니다. 바로 구간 합의 내용을 뭘로 정해야하냐 와 query 방법을 생각해내는 발상을 요구하고 있습니다. 일단 트리 자체는 사실 문제에서 요구하는 숫자의 ..
https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 해설 단순 세그먼트 트리의 구현 문제입니다. 다만 좀 주의할 점 몇가지가 있다면, 저같은 경우 query에서 범위를 벗어난 경우 -1을 반환하게 하고 아예 배제를 했는데, query 시 범위를 벗어날 경우 문제에서 요구하는 것이 구간의 곱이기 때문에 반환 값을 1로 설정해주시면 됩니다. 나머지 부분은 제 코드를 참고하시면 될 것 같습니..
https://boj.kr/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 서론 구현 문제를 보면 한숨부터 나오는 병이 있어요 보자마자 어떻게 구현하지라고 생각했다. 한숨부터 나왔는데, 의외로 정직하게 미로 문제를 풀듯이 찾아나가면 쉽습니다. 항상 생각해야하지만, 구현문제는 의외로 구현의 양보단 구현 이전에 생각을 많이 요구하는데, 그 생각이 필요한 부분은 대부분 자료구조 형태짜기에 있습니다. 보통 저희가 (자료구조 + 알고리즘) 이 동등하게 중요하다고 말하잖아요. 개인적으로 PS 문제 중에 구현 문제들은 알고리..
https://boj.kr/27115 27115번: 통신소 대한민국 공군은 비행하는 전투기와 지상에서 원활하게 통신하기 위하여 여러 위치에 통신소를 설치하였다. 지금까지 $K$개의 통신소를 배치하였는데, 각 통신소는 $\left(y_i,x_i\right)$의 위치에서 www.acmicpc.net 0. 서론 킹받는 asdarwin03님이 만든문제 BFS 문제였는데, 사실 BFS 하는 과정 자체에 집중하면 안됐었다. BFS의 과정을 자세히 보면 큐에 넣는 과정이 있는데, 이 큐에 무엇을 넣을지에 대한 생각을 좀 하지 못했던 것 같다. 큐에 넣는 과정을 조금만 비틀어도 복잡한 문제를 간단히 할 수 있음을 알 게 됐는데, 이는 우선순위 큐를 활용하는 방법에 대해 내가 생각하지 못했던 과정과 비슷했어서 좀 많이 ..
