본문 바로가기

(441)
[Python] 7538번 Incomplete chess boards (추후 보강 예정) https://www.acmicpc.net/problem/7538 25/06/09 유명한 퍼즐 문제이다. 간단하게 구현만 하면 되는 문제로, 이걸 정당화하는데에는 조금 어려운 내용이 들어간다. 문제 접근 방식: 주어진 요구 사항은, $8 \times 8$크기의 체스판이 주어지는데, 이 체스판의 두 곳에 구멍을 뚫어놓고, 남은 칸들을 $2 \times 1$크기의 도미노 타일로 전부 매울 수 있는지의 여부를 각 테스트 케이스마다 판단하는 것이다. 이 문제는 Mutilated chessboard problem이라는 이름으로 검색하면 위키에 잘 나와있다.https://en.wikipedia.org/wiki/Mutilated_chessboard_problem Mutilated chessboard proble..
[Python] 34019번 [G] Grounded Number https://www.acmicpc.net/problem/34019 25/06/05 찍어서 맞추기는 쉽지만 증명하기 어려운 애드 혹 문제다. 문제 접근 방식: 그냥 작은 케이스에 대해 나열 해보면, 짝수일때는 가능하고 홀수일때는 불가능하다는 걸 확인할 수 있다. 실제로 그렇게 제출하면 맞을 수 있는데, 이를 증명하는 건 쉽지 않다. 증명 과정은 다음과 같다. $i$번째 연산 과정 전의 수를 $n_i$라고 하자. $n_i - i = d_i$라고 정의하자. 만약 $n_i$에서 연산을 한 결과가 $+1$인 경우, 즉, $n_i$가 $i$의 배수인 경우, 다시 말해, $i$가 $n_i$를 나눌 때, 같은 이야기로, $i$가 $d_i + i$를 나눌때, 즉, $i$가 $d_i$를 나눌 때, $d_{i+1} =..
[Python] 1459번 걷기 https://www.acmicpc.net/problem/1459 25/06/13 무난 무난한 기하학 + 애드 혹 문제이다. 약간의 케이스워크가 있는데, 잘 정리하면 케이스워크도 쉽게 정리할 수 있다. 문제 접근 방식: 문제는 가로, 세로로 가는 데 걸리는 시간과 대각선으로 가는데 걸리는 시간이 따로 주어지고, 양수 좌표 $x, y$가 따로 주어질 때 $(0, 0)$에서 해당 좌표로 갈 수 있는 최단 시간을 출력하는 것이다. 결국 세가지 경우로 나뉜다. 1. 가로, 세로 움직임만 사용하여 가는 경우 2. $x = x_0, y = y_0$를 벗어나지 않는 선에서 대각선 움직임을 최대한 사용한 후 가로, 세로 움직임을 사용하여 가는 경우 3. 벗어나도 상관없이, 대각선 움직임을 최대한 사용하여 가는 경우..
[Python] 10435번 만칼라 https://www.acmicpc.net/problem/10435 25/06/14 개인적으로 현재 난이도보다 한단계 높은 플레티넘 5정도의 난이도로 느껴진 문제였다. 이전에 북마크에 담아두고 고민하다가 못풀었던 문제인데, 다른 블로그 글을 확인해서 힌트를 얻고 해결했다. 게임 이론과 해 구성하기가 담겨있는 좋은 문제인 것 같다. 문제 접근 방식: 문제를 해결하기 위해서는 2가지 핵심 아이디어를 알아야 한다. 1. 구슬이 $N$개일 때 이기는 상태에서 어떤 "액션"을 취하면 구슬이 $N-1$개일 때 이기는 상태로 바뀐다. 2. "액션"을 취하면 $k$번째에 있던 $k$개의 돌들은 모두 없어지고, $1$번째부터 $k-1$번째의 돌 개수는 한 개씩 증가한다. 어떤 "액션"을 취한 뒤에도 턴을 이어나가려..
[25/06/12] 오랜만에 쓰는 회고록 + 취준 후기 오랜만에 회고록을 써봅니다. 좋은 소식이 있어서 한결 편안하게 작성할 수 있게 되었습니다.이번년도 상반기를 시작으로 첫 취업 준비를 하게 되었습니다. 6개월 만에 삼성이라는 좋은 결과를 얻을 수 있어서 감사하다고 생각합니다. 저 같은 경우는 Samsung Convergence Software Academy(이하 SCSA)라는 조금 특수한 전형으로 썼습니다.뭐 찾아보면 많이 나오겠지만, SCSA는 비전공자(공대가 아닌, 즉, 자연대와 인문대)를 대상으로 6개월동안 SW와 관련된 내용들을 빠르게 가르친 후, 해당 부문에 속하는 직무로 삼성 측에서 배정해주는 전형입니다. 저 같은 경우, 자연대(수학과)를 나왔기 때문에 해당 전형을 쓸 수 있었습니다. 6개월 교육 이후에 100% 배정받는 건 아니지만, 전환률이..
[C++] 2370번 시장 선거 포스터 https://www.acmicpc.net/problem/2370 25/03/18 이전에 해결했던 좋은 문제인데, 복습할 겸 다시 적어본다. 문제 접근 방식: 일단 이 문제에는 아주 간단하고 나이브한 솔루션이 존재한다. 그 전에 내가 먼저 해결했던 방법을 소개하고자 한다. 문제를 요약하자면 다음과 같다. 1. 포스터를 순서대로 붙임.2. 즉, 포스터가 시작하는 지점 $l$과 끝나는 지점 $r$이 쿼리로 주어짐.3. 쿼리가 다 끝난 뒤에 보이는 서로 다른 포스터의 개수를 구하는 것이 우리의 목적. 포스터가 위치할 수 있는 범위는 $1$부터 $100 \ 000 \ 000$ ($1$억)까지이다. 또한 쿼리의 개수는 최대 $10 \ 000$($1$만)까지이다. 가장 단순한 방법은, $1$억짜리 배열을 하나 ..
[C++] 11440번 피보나치 수의 제곱의 합 / 28749번 Квадраты Фибоначчи https://www.acmicpc.net/problem/11440https://www.acmicpc.net/problem/28749 25/03/04 25/03/09  두 문제는 인덱스만 다르고 동일한 문제이므로, 같은 풀이 방법으로 설명하겠다. 문제 접근 방식:  피보나치 수의 거듭 제곱의 합을 구하는 문제이다. $F_{n} = F_{n-1} + F_{n-2}$를 생각해보자. 제곱을 하면 다음과 같다. $$\begin{align}{F_{n}}^{2} &= (F_{n-1} + F_{n-2})^{2} \\ &= {F_{n-1}}^{2} + {F_{n-2}}^{2} + 2F_{n-1}F_{n-2}\end{align}$$ 제곱 항은 공통이 되는데, 뒤에 붙은 $2F_{n-1}F_{n-2}$항이 공통이 되지 않..
[25/04/12] 오랜만에 쓰는 회고록 4달만에 회고록을 작성한다.졸업하고 나서 처음으로 작성하는 것 같은데... 요즘 나의 근황이 궁금할 것 같은 사람들이 있어서 작성해본다.먼저 SSAFY(삼성 청년 SW 아카데미)에 합격을 해서 13기에 다니고 있다.다니면서 취업 준비를 하고 있고, 이곳 저곳의 회사에 지원서를 넣고 있다. SSAFY는 뭐냐, 일종의 부트캠프인데, 삼성과 노동부측에서 협약을 해서 만든 일종의 사회 공헌 프로그램이다.과정은 1년동안 진행되고, 전공과 관련 없이 이 곳에서 같이 배우고 프로젝트를 진행하면서 개발자로서 능력을 길러주도록 하는 곳이다.커리큘럼은 검색하면 나오는데, 현재 나는 임베디드 커리큘럼을 밟고 있는 중이다. 목표는 1학기에 싸탈.취업에 성공하면 중도 퇴소를 하게 되는데, 이걸 싸탈이라고 부른다. 결국 싸피도 ..