[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..