✏️ 알고리즘

2022 ICPC Seoul Regional 후기

안녕하세요 Gliver 입니다. 이번 글은 2022.11.19 에 있었던 2022 ICPC Seoul Regional에 대한 글입니다. 운이 좋게 본선을 나갈 수 있게 되어 지난 예선 글에 이어서 본선 관련한 글을 써볼까 한다. 대회가 끝난 직후부터 시험과 프로젝트 때문에 거의 한 달이 지난 지금에야 글을 쓸 수 있게 되었다.. 이번 대회 또한 예선과 비슷한 전략으로 진행하게 되었다. (나와 α가 주로 키보드를 잡았으며 β는 보조를 주로 하였다) 이번 대회에서는 내가 E, I를 풀었고, α가 F, J를 풀었다. (참고로, 대회 문제는 여기에서 풀어볼 수 있다) J. Parentheses Tree (00:37) [+1] 처음에 나는 β와 I를 풀고, α는 J를 풀기로 했다. α가 J를 처음 제출했을 때 틀..

[11강] 이분 탐색 알고리즘

안녕하세요 Gliver 입니다. 이번 글에서는 이분 탐색 알고리즘에 대해 알아보겠습니다. 목차 이분 탐색 알고리즘 파라매트릭 서치 알고리즘 실제 문제에서 이분 탐색 알고리즘 1. 이분 탐색 알고리즘 이분 탐색 알고리즘은 정렬된 배열에서 특정한 원소를 찾는 알고리즘이다. 정렬된 배열이 아니라면 이분 탐색을 시행할 수 없음. 이분 탐색(binary search)은 범위를 반으로 줄여가며 특정 원소를 찾는 알고리즘으로 예시를 통해서 어떻게 동작하는지 살펴보자. 아래와 같이 정렬된 배열이 있을 때 이분 탐색 알고리즘을 통하여 10을 찾아보자. 방법1 [1단계] left = 0, right = 11 처음에는 배열의 첫 인덱스를 left(0), 끝 인덱스를 right(11)로 지정하고 시작한다. mid = (lef..

2022 ICPC Seoul Regional 예선 후기

안녕하세요 Gliver 입니다. 이번 글은 2022.10.08 에 있었던 2022 ICPC Seoul Regional 예선에 대한 글입니다. 이번 대회는 같은 학과 사람들과 함께 나가게 되었다. (편의상 α, β로 칭하겠다) 이번 대회에서 내가 푼 문제는 C, E, F이고, α가 A, K를 풀었다. 이번 대회에서 주로 α와 내가 키보드를 잡고 진행하게 되었다. 그리고 β는 문제에 대한 설명과 조언을 해주었는데 도움이 많이 됐던 것 같다. E. Gift Discount (00:17) 개발환경 세팅을 마치자마자 β가 나에게 설명해 준 문제이다. 보자마자 떠오른 아이디어는 '가장 싼 물건들을 사야겠네'와 '산 물건들 중에서 가장 비싼 물건 $a$개를 할인하면 되겠네' 였다. 이를 prefix sum을 이용하여..

[CodeForces] #819 (Div.2) A~D 업솔빙

안녕하세요 Gliver 입니다. 이번 글은 코드포스 #819 (Div.2) 에 대해 업솔빙하는 글입니다. 이번 대회는 20분 늦게 시작했는데 의외로 잘 한 것 같다..? A번 - 사고력이 조금 필요한 문제이다. B번 - 답이 여러가지 나올 수 있으니 아무거나 출력하면 되는 문제이다. - 이런 문제는 가장 간단한 경우를 기준으로 생각하는 것이 중요하다. C번 - 문제 지문이 무슨 소린지 이해를 못했다. - 대충 테스트케이스를 보고 파악한 뒤, "이렇게 하면 되겠는데?" 했는데 맞았다. D번 - 대회 도중에 문제의 핵심을 파악하지 못했다. - 끝나고 풀어보니, 정말 좋은 문제인 것 같았다. A. Mainak and Array 배열 $a$에 대해 어떠한 operation을 진행할 수 있고, 이를 1번 진행했을..

[CodeForces] #818 (Div.2) A~C 업솔빙

안녕하세요 Gliver 입니다. 이번 글은 코드포스 #818 (Div.2) 에 대해 업솔빙하는 글입니다. 이번 대회는 망했다.. C번을 풀다가 대회가 끝나 버렸다. A번 - GCD와 LCM을 잘 알고 있다면 빠르게 풀 수 있는 문제이다. - 처음에 접근을 잘 못해서 A번부터 말렸었다. B번 - 테스트케이스가 친절해서 쉽게 풀 수 있었다. - 하지만, 증명은 꽤 어려운 문제인 것 같다. C번 - 처음에 잘못된 아이디어를 떠올려서 말린 문제이다. - 결국 끝나고 1분 후에 코드를 완성하였는데 그때는 이미 늦었다. 사실, C번까지 풀었다 해도 잘한 라운드는 아닌듯 하다. A. Madoka and Strange Thoughts $\frac{lcm(a,b)}{gcd(a,b)} \leq 3$ 의미를 어떻게 해석하는..

[CodeForces] ECR 134 (Div.2) A~D 업솔빙

안녕하세요 Gliver 입니다. 이번 글은 코드포스 ECR 134 (Div.2) 에 대해 업솔빙하는 글입니다. 이번 대회는 처음 1시간 10분 정도 A~C를 풀었고, 마지막에 D번을 구현하던 중에 대회가 끝나 버렸다.. A번 - Div.2 A 에서 보기 드문 단순 구현 문제라는 생각이 든다. B번 - Div.2 B 치고는 쉬운 문제였으나, 역시나 효율성을 생각해야 하는 문제였다. C번 - Div.2 C 에 맞는 문제인 거 같았고, 개인적으로 어렵게 푼 거 같다. D번 - Div2.D 에 맞는 문제인 거 같았다. - 핵심적인 로직은 빠르게 파악했는데.. 구현을 잘 못해서 망했다. A. Image $2 \times 2$ 행렬이 주어지고 모든 색이 같아지게 만들 때 드는 최소 시행 횟수를 구하는 문제이다. $..

[10강] DP 알고리즘

안녕하세요 Gliver 입니다. 이번 글에서는 DP 알고리즘에 대해 알아보겠습니다. 목차 DP 알고리즘 실제 문제에서 DP 알고리즘 접근 방식과 알고리즘 접근 방식과 알고리즘 내용은 브루트 포스 알고리즘, 그리디 알고리즘, DP 알고리즘 글에 동일하게 존재합니다. 접근 방식은 문제의 핵심 아이디어를 찾는 것을 도와주는 방법론이고 알고리즘은 문제를 해결하는 과정을 일련의 순차적인 절차로 만들어놓은 방법론입니다. 구체적인 예를 들어 설명해보겠습니다. 에라토스테네스의 체 알고리즘은 소수(prime number)를 판별하는 알고리즘이고 그리디 알고리즘은 매 순간에서 가장 최선의 선택을 하여 답을 구해내는 알고리즘입니다. 에라토스테네스의 체 알고리즘은 언제 쓰면 될까요? → 소수(prime number)를 판별할..

[09강] 그리디 알고리즘

안녕하세요 Gliver 입니다. 이번 글에서는 그리디 알고리즘에 대해 알아보겠습니다. 목차 그리디 알고리즘 실제 문제에서 그리디 알고리즘 접근 방식과 알고리즘 접근 방식과 알고리즘 내용은 브루트 포스 알고리즘, 그리디 알고리즘, DP 알고리즘 글에 동일하게 존재합니다. 접근 방식은 문제의 핵심 아이디어를 찾는 것을 도와주는 방법론이고 알고리즘은 문제를 해결하는 과정을 일련의 순차적인 절차로 만들어놓은 방법론입니다. 구체적인 예를 들어 설명해보겠습니다. 에라토스테네스의 체 알고리즘은 소수(prime number)를 판별하는 알고리즘이고 그리디 알고리즘은 매 순간에서 가장 최선의 선택을 하여 답을 구해내는 알고리즘입니다. 에라토스테네스의 체 알고리즘은 언제 쓰면 될까요? → 소수(prime number)를 ..