✏️ 알고리즘

[CodeForces] #905 (Div.3) A~F 업솔빙

안녕하세요 Gliver 입니다. 이번 글은 코드포스 #905 (Div.3) 에 대해 업솔빙하는 글입니다. A. Morning 단순 구현 문제로, 버튼을 누르는 횟수와 이동하는 횟수를 구해서 출력하면 된다. A.cpp B. Chemistry 개인적으로 조금 복잡하게 생각한 문제이다. 팰린드롬을 만들 수 있는 경우는 다음 두 가지 상황으로 제한할 수 있다. 모든 문자의 개수가 짝수개인 경우 하나의 문자의 개수가 홀수개이고, 나머지 모든 문자의 개수가 짝수개인 경우 따라서, 문자열을 적절히 제거하여 홀수개인 문자가 1개 이하가 되도록 만들 수 있으면 된다. 이는, 홀수개인 문자의 개수에서 $k$를 뺀 값이 1 이하 이면 된다는 의미이다. B.cpp C. Raspberries 모든 원소의 곱이 $k$로 나누어 ..

[백준 27986번] 평범한 구성적 문제

27986번: 평범한 구성적 문제 정수 $N$과 $M$개의 정수 쌍 $(L_1, R_1), (L_2, R_2), \cdots (L_M, R_M) $이 주어진다. 이제 아래 조건을 만족하면서 값 $K$를 최대화시키는 수열 $X$를 찾아야 한다. $X$는 $K$ 이하의 양의 정수 $N$개로 구성되어 www.acmicpc.net 문제가 수학적인 표현이 많이 쓰여, 다소 이해하기 어렵다고 생각한다. 문제 설명 문제에서 요구하는 것은 배열 $X$를 구하는 것이며, 배열 $X$는 $1$부터 $K$이하의 수로 구성되어 있다. 문제의 입력으로 주어지는 것들은 조건이며, 조건들을 만족하면서 $K$가 최대가 되게 하는 배열 $X$를 구하는 문제이다. $K$의 최대값은 하나지만, 이때 배열 $X$는 여러 가지 경우가 나올 ..

[2023 하반기 ICT 인턴십] 코딩테스트 후기

안녕하세요 Gliver 입니다. 이번 글은 2023 하반기 ICT 인턴십 코딩테스트 후기입니다. 이번 코딩테스트는 (프로그래머스와 같은 국내 사이트가 아닌) 해커랭크라는 해외 사이트를 통해서 진행되었다. 해커랭크 문제 형식은 프로그래머스와 백준의 중간 형태를 띠고 있다. 만약, 해커랭크를 사용해보지 않았다면 테스트 사이트를 통해 사용법을 익혀두는 것을 추천한다. 문제 총평 코딩테스트는 총 6시간에 5문제가 출제되었다. 전체적인 문제 느낌이 구현력보다는 사고력을 요구하는 문제가 주로 나온 거 같다. 내가 느낀 이번 코딩테스트 문제의 대략적인 난이도는 다음과 같다. (문제에 대한 저작권이 있어 문제에 대한 난이도와 유형에 대해서만 정리하겠다) A번 - 실버 1 - 무작정 구현하면 시간초과가 발생할 수 있는 ..

[백준 10220번] Self Representing Seq

10220번: Self Representing Seq 두 번째 예제의 경우 가능한 A는 (2,1,2,0,0) 한 개만 존재한다. 세 번째 예제의 경우 가능한 A는 (2,0,2,0), (1,2,1,0) 두 개 존재한다. www.acmicpc.net 이번 포스팅은 바킹독님의 포스팅을 참고하여 작성하였습니다. 목차 문제 접근 문제 풀이 문제 접근 이 문제는 $\small{N}$이 주어졌을 때, 길이가 $\small{N}$이고 아래의 조건을 만족하는 수열 $\small{A}$의 개수를 구하는 것이다. ($\small{1 \leq N \leq 100}$) $\small{A_i}$ = 수열 $\small{A}$에서 $\small{i}$가 등장하는 횟수 ($\small{0 \leq i < N}$) 자명한 조건들 A[..

[백준 13275번] 가장 긴 팰린드롬 부분 문자열

13275번: 가장 긴 팰린드롬 부분 문자열 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있으며 길이는 1보다 크거나 같고, 100,000보다 작거나 같다. www.acmicpc.net 목차 관련 개념 문제 접근 풀이 관련 개념 팰린드롬 부분 문자열 DP 풀이 (링크) 팰린드롬 부분 문자열 Manacher 알고리즘 (링크) 팰린드롬 문자열의 성질 길이가 홀수인 경우에 가운데 문자가 중심이 된다. 길이가 짝수인 경우에 가운데 두 문자 사이가 중심 축이 된다. 팰린드롬 문자열은 앞 뒤에 같은 문자를 붙이면 계속 팰린드롬 문열이 된다. 문제 접근 문자열 $\small{S}$의 부분 문자열 중에서 가장 긴 팰린드롬 문자열의 길이를 출력하는 문제이다. ($\small{1 \leq |S| \l..

[백준 17425번] 약수의 합

17425번: 약수의 합 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 목차 사전 지식 문제 접근 풀이1 (Accepted) 풀이2 (Memory Limit Exceeded) 풀이3 (Accepted) 사전 지식 에라토스테네스의 체 알고리즘에 대해 알고 있어야 한다. (링크) 약수와 배수, 소수(prime number)에 대한 개념을 알고 있으면 이해하기 수월할 것이다. (링크) 문제 접근 자연수가 $\small{N}$ 주어지면 $\small{g(N) = f(1) + (2) + ..

[백준 1395번] 스위치

1395번: 스위치 첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O www.acmicpc.net 목차 사전 지식 문제 풀이 사전 지식 세그먼트 트리(Segment Tree)에 대한 기본 지식을 알고 있어야 한다. (링크) 느리게 갱신되는 세그먼트 트리(Segment Tree with Lazy Propagation)를 알고 있어야 한다. (링크) 문제 풀이 구간 단위로 업데이트가 일어나므로 느리게 갱신되는 세그먼트 트리를 이용하면 된다. 구간 단위로 업데이트할 때 대응하는 노드에는 어떤 변화가 일어나는가 어떤 노드는 해..

[백준 17353번] 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별

17353번: 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 욱제의 은밀한 취미 중 하나는 매일 밤하늘을 감상하는 것이다. 😓 욱제는 하늘의 별들이 다음과 같은 규칙들을 따르며 떨어지는 걸 관찰했다. 별이 떨어지는 위치는 N개의 점이다. 점은 순 www.acmicpc.net 목차 사전 지식 문제 풀이 사전 지식 세그먼트 트리(Segment Tree)에 대한 기본 지식을 알고 있어야 한다. (링크) 느리게 갱신되는 세그먼트 트리(Segment Tree with Lazy Propagation)를 알고 있어야 한다. (링크) 문제 풀이 문제 접근 과정 AC code