본문 바로가기

알고리즘

 (368)
[Python] 28303번 자석 https://www.acmicpc.net/problem/28303 28303번: 자석 예제 1의 경우 N극이 3번 칸에 놓이고 S극이 5번 칸에 놓이도록 자석을 설치할 때 1번 현상으로 $a_3=22$의 에너지가 충전되며, 2번 현상으로 $a_5=4$의 에너지가 소모되고, 3번 현상으로 $(5-3)\times 2=4$ www.acmicpc.net 24/02/24 누적 합 응용으로, 아이디어를 떠올리니 쉽게 해결할 수 있었던 문제였다. 문제 접근 방식: 문제를 잘 읽고 분석을 해보았다. 배열을 $A$라고 하고, 배열의 $i$번째 원소를 $a_i$라고 한다면, 문제에서 요구하는 것은 $a_i - a_j - |i-j|K$의 값을 최대화시키는 것이다. $N$의 최댓값이 $500,000$이기 때문에, $\mat..
[Python] 18116번 로봇 조립 https://www.acmicpc.net/problem/18116 18116번: 로봇 조립 성규는 로봇을 조립해야 한다. 상자 안에는 여러 로봇의 부품들이 섞여 있다. 그런데 어떤 부품이 어느 로봇의 부품인지 표시가 되어있지 않다. 호재는 전자과라서 두 부품을 보면 같은 로봇의 www.acmicpc.net 24/02/21 분리 집합 문제로, 집합의 크기를 바로 내보내는 쿼리를 어떻게 구현해야 할 지 집중해야 해결할 수 있는 문제다. 문제 접근 방식: 결론부터 말하면, 집합의 크기를 바로 내보내는 리스트를 따로 관리해주면 된다. 기존 분리 집합 코드에서는 배열의 인덱스는 해당 노드의 값, 배열의 값은 해당 노드를 자식 노드로 가지는 노드의 값, 즉, 부모 노드의 값을 저장한다. 나는 여기에서 집합의 개수..
[Python] 5588번 별자리 찾기 https://www.acmicpc.net/problem/5588 5588번: 별자리 찾기 상근이는 밤하늘 사진에서 별자리를 찾고 있다. 사진에는 꼭 찾고 싶은 별자리와 같은 형태, 방향, 크기의 도형이 한 개가 포함되어 있다. 하지만, 상근이가 가지고 있는 사진 속에는 별자리를 www.acmicpc.net 24/02/01 간단한 브루트포스 문제로, 집합을 사용해 적절히 구현하면 쉽게 해결할 수 있는 문제이다. 문제 접근 방식: 별자리를 구성하는 별들은 리스트로 받고, 사진 속 별 들의 위치는 집합에 넣어주었다. 이후 사진 속의 모든 별들 마다 그 별이 옮겨진 별자리의 중심이 된다고 가정하고 이동량을 구해주었다. 옮기기 전 별자리에 있는 모든 별 마다 그 이동량을 적용해 주었다. 즉, 옮겨진 별의 좌표를..
[Python] 23309번 철도 공사 https://www.acmicpc.net/problem/23309 23309번: 철도 공사 첫 번째 줄에 공사를 시작하기 이전에 있는 역의 개수를 나타내는 양의 정수 $N$과 공사 횟수를 나타내는 양의 정수 $M$이 주어진다. ($1 \le N \le 500\,000$, $1 \le M \le 1\,500\,000$) 두 번째 줄에는 공사 www.acmicpc.net 24/02/13 파이썬으로 해결하기 정말 힘든 문제로, C++을 사용할 수 있는 사람이라면 웬만해서는 C++로 해결하기를 권장하는 문제다. 주어진 그대로 잘 구현을 했음에도 불구하고 여러 기술들을 활용해야만 시간 초과를 면할 수 있다. Python3로는 통과한 사람이 없는 것으로 보아, Pypy를 사용해야만 풀 수 있는 문제로 보인다. 문..
[Python] 14925번 목장 건설하기 https://www.acmicpc.net/problem/14925 14925번: 목장 건설하기 랜드 씨는 퇴직금으로 땅을 사서 목장을 지으려 한다. 그가 사려고 소개받은 땅은 직사각형이고 대부분 들판이지만, 여기저기에 베기 어려운 나무와 치울 수 없는 바위가 있다. 그는 목장을 하 www.acmicpc.net 24/01/29 2차원 DP문제로, 이전에 어떤 선배로부터 1915번 문제에 대한 풀이를 들은 적이 있었다.(물론 이 문제는 아직 해결하지 못한 상태다.) 그 접근 방법이 얼핏 생각이 나서 그 방식대로 접근을 했고, 맞았습니다를 받을 수 있었다. 문제 접근 방식: DP테이블을 다음과 같이 정의했다. $$DP[N][M] = N\textrm{행 }M\textrm{열을 오른쪽 아래 꼭짓점으로 가지는 정..
[Python] 11688번 최소공배수 찾기 https://www.acmicpc.net/problem/11688 11688번: 최소공배수 찾기 세 정수 a, b, L이 주어졌을 때, LCM(a, b, c) = L을 만족하는 가장 작은 c를 찾는 프로그램을 작성하시오. LCM(a, b, c)는 a, b, c의 최소공배수이다. www.acmicpc.net 24/01/25 단순한 정수론 문제로, 소인수 분해 코드를 효율적으로 작성한다면 쉽게 풀 수 있는 문제이다. 문제 접근 방식: $a, b, L$의 값이 주어질 때, $\mathrm{lcm}(a, b, c) = L$을 만족시키는 가장 작은 $c$의 값을 구하는 것이 문제의 의도이다. $\mathrm{lcm}(a, b, c) = \mathrm{lcm}(\mathrm{lcm}(a, b), c)$가 성립하므..
[Python] 17504번 제리와 톰 2 https://www.acmicpc.net/problem/17504 17504번: 제리와 톰 2 $$ 1 - \cfrac{1}{2 + \cfrac{1}{7 + \cfrac{1}{1 + \cfrac{1}{8}}}} = 1 - \cfrac{1}{2 + \cfrac{1}{7 + \cfrac{8}{9}}} = 1 - \cfrac{1}{2 + \cfrac{9}{71}} = 1 - \cfrac{71}{151} = \cfrac{80}{151} $$ www.acmicpc.net 24/01/24 수학에 구현을 덧붙인 재미있는 문제다. 말로는 설명하기 힘들어 예시를 하나 직접 따라가 보면 쉽게 이해할 수 있다. 문제 접근 방식: 제리가 훔쳐간 치즈의 무게만 구하면 톰이 가지고 있는 치즈의 무게를 구할 수 있다. $a_1,..
[Python] 10407번 2 타워 https://www.acmicpc.net/problem/10407 10407번: 2 타워 2 타워의 높이 H는\[2^{2^{2^{\cdot^{\cdot^{\cdot 2}}}}}\]에서 숫자 2가 나타나는 횟수로 정의된다. 2 타워의 값은 해당 표현식의 값으로 정의된다. 예를 들어, 높이 1의 2 타워 값은 2이고, 높이 2의 2 타워 www.acmicpc.net 24/01/20 수학 문제로, 찍어서 맞출 수도 있으나 여기서는 증명을 소개하도록 하겠다. 문제 접근 방식: 결론만 이야기 하자면, $H = 1$일 때는 나머지가 $2$이고, 그 외에는 $1$이다. 일단 $H=1$일 때는 2타워의 값은 $2$이므로, $3$으로 나눈 나머지가 $2$이다. $2$를 짝수 번 곱하면 그 숫자를 $3$으로 나눈 나머지..

티스토리툴바