지난번 올린 상반기 회고( https://infikei.tistory.com/74 )에 이어서 하반기도 회고 글로 정리해보려고 한다. 7월 - 회사 생활의 시작한화시스템 ICT 부문에서 첫 회사 생활이 시작되었다.채용전환형 인턴으로 2개월 간 근무하며 과제를 수행해야 했다.AI랑 프롬프트에 대해 많이 배울 수 있었다. 요약 (기억에 남는 일들)입사 8월 - 채용전환형 인턴의 마무리매일 과제에 집중하며 살았던 것 같다.무엇보다 을지로까지 왕복 4시간에 달하는 통근 거리가 체력적으로 살짝 고비였던 기억이 난다. 결국 전환이 되지 않아서 회사를 나오게 되었다.아쉬움이 없다고 하면 거짓말이겠지만, 후련한 마음이 더 컸던 것 같다.상반기에 합격도 많이 했었기 때문에, '또 다른 곳 가서 열심히 하면 되지'라고 생..
분류 전체보기
인생을 살면서 이렇게 열심히 살았던 한 해가 또 있을까 싶다.1년동안 정말 많은 일이 일어났기 때문에 회고 글을 작성하면서 나의 2025년을 정리해보려고 한다. 1월 - 싸피 생활 마무리, 본격적인 취준 시작1월은 나에게 막막했던 달이었다.2024년 한 해동안의 싸피 생활을 마무리하고, 이제 나 혼자만의 취준 생활이 시작되는 기간이었다.많은 동기들은 취업에 성공해서 회사로 떠나갔기에 진짜 혼자 남겨진 기분이 들기도 했다.그래서 잠시 재정비하는 시간을 가졌다. 12월 말부터 1월 초까지 프로그래머스의 SQL 문제를 정주행했다.Lv.1부터 Lv.3까지 순서대로 거의 다 풀면서 앞으로 있을 코테의 SQL 문제를 시간 있을 때 미리미리 대비했다. 1월에는 잡 생각이 많이 들었다.혼자 집에 있는 시간이 길어지면 ..
1. 문제https://www.acmicpc.net/problem/1028입력으로 주어진 $R \times C$ 크기의 2차원 격자에서, 가장 큰 다이아몬드 광산의 크기를 구하는 문제이다. 2. 접근지난 번 해결한 백준 1641번과 접근이 비슷하다는 느낌을 받았다.따라서 풀이는 다음의 순서로 진행했다.격자의 각 칸마다 좌상-우하 대각선 방향으로 1이 얼마나 연속되는지 저장한다. 우상-좌하 대각선 방향에 대해서도 저장한다.격자의 모든 칸에 대해, 해당 칸이 다이아몬드 광산의 아래쪽 꼭짓점이 될 때 만들 수 있는 다이아몬드 광산의 최대 크기를 구한다. (1) 대각선 방향으로 연속한 1의 개수 세기1번 단계를 수행하기 위해 $R \times C$ 크기의 2차원 배열 lu 를 선언하여, lu[x][y] 를 $(..
1. 문제https://www.acmicpc.net/problem/1641알파벳 대문자로 이루어진 $N \times N$ 크기의 행렬이 주어지면, 직각 이등변 삼각형과 이등변 삼각형의 총 개수를 출력하는 문제이다. 2. 접근 1 - 이등변 삼각형 (a)의 개수(a) 모양에 해당하는 이등변 삼각형은 방향에 따라 다음 4가지로 구분할 수 있다. A A AAA AAA AA AA AA AA AAA AAA A A 이 중에서 첫 번째 모양을 어떻게 구할지 생각해보자.memo1[x][y] 를 $(x, y)$ 위치가 우하단 꼭짓점인 첫 번째 모양 삼각형의 개수로 정의하자. 간단한 예시들을 통해 살펴보면 다음과 같은 사실을 차례대로 발견할 수 있다.$(x, y)$ 위치, $(..
1. 문제https://www.acmicpc.net/problem/2673평면 위에 있는 원의 둘레에 100개의 점이 일정한 간격으로 존재한다. 각 점은 1번부터 100번까지 시계 방향으로 번호가 붙어 있다.이 점들을 끝점으로 하는 N개의 현이 주어질 때, 서로 교차하지 않는 것들을 최대한 많이 찾아서 그 개수를 출력해야 한다.단, 각 점은 많아야 한 현의 끝점이 될 수 있다. 2. 접근 및 풀이주어진 원에서 1번 점과 100번 점 사이를 잘라서 직선으로 평평하게 보니까, 문제를 해결하기가 더 쉬워졌다.결국 얼마 전에 올린 백준 3012번 올바른 괄호 문자열 문제와 접근법이 유사하다는 생각이 들었다. memo[j][i] 를 j 번부터 i 번까지의 구간에서 가능한 최대 개수로 정의한 다음, 길이가 짧은 구..
1. 문제https://www.acmicpc.net/problem/3012소괄호, 중괄호, 대괄호, 물음표로만 이루어진 문자열이 입력으로 주어진다. 이때 해당 문자열의 물음표를 괄호로 적절하게 바꿔서 만들 수 있는 올바른 괄호 문자열의 수를 출력해야 한다.단, 개수가 다섯 자리를 넘어가는 경우에는 마지막 다섯 자리만 출력해야 한다. 2. 접근가장 먼저 n 이 홀수라면 올바른 괄호 문자열을 만들 수 없으므로 이 경우에는 0을 출력하고 바로 종료해주었다.int main() { FASTIO; int n; string s; cin >> n >> s; if (n % 2 == 1) { cout 이제 모든 [시작 인덱스, 종료 인덱스] 구간에 대해 올바른 괄호 문자열의 개수를..
0. 들어가기 전에공부한 내용을 간략하게 정리하는 느낌으로 작성한 글이다. 1. 디닉 알고리즘 (Dinic's Algorithm)최대 유량 문제를 더 빠르게 해결하기 위해 등장한 알고리즘이다.에드몬드-카프 알고리즘의 시간 복잡도가 $O(VE^2)$이었다면, 디닉 알고리즘은 $O(V^2 E)$로 동작한다고 한다. 그러면 어떻게 더 빠르게 동작할 수 있었을까?핵심 아이디어는 다음과 같다.현재 그래프에서 BFS를 통해 각 정점의 레벨을 구한다. 이를 통해 레벨 그래프를 만들어서, 레벨이 증가하는 모든 흐름을 찾을 수 있게 한다.레벨이 증가하는 방향으로만 DFS를 수행하면서, 가능한 모든 유량을 추가한다. 에드몬드-카프 알고리즘에서는 증가 경로를 한 번 찾을 때마다 BFS를 수행한다. 반면 디닉 알고리즘에서는 ..
정수론 관련 주요 알고리즘을 어딘가에 기록해두면 좋을 거 같아서, 코드 위주로 한번 모아봤다. (알고리즘에 대한 설명은 거의 없음) 1. 최대공약수 (GCD, Greatest Common Divisor)(1) 유클리드 호제법 이용using ll = long long;ll get_gcd(ll a, ll b) { while (b != 0) { ll r = a % b; a = b; b = r; } return a;} 관련 게시글 (유클리드 호제법) : https://infikei.tistory.com/46 2. 최소공배수 (LCM, Largest Common Multiple)(1) 최대공약수 이용$a \times b = \operatorname{GCD}(a..
0. 들어가기 전에최대 유량 문제, 포드-풀커슨 알고리즘, 에드몬드-카프 알고리즘에 대해서는 이미 잘 설명된 글들이 많기 때문에, 공부한 내용을 간략하게 정리한다는 느낌으로 남겨보려고 한다. 1. 최대 유량 문제 (Maximum Flow Problem)소스 정점과 싱크 정점이 정해진 방향 그래프가 주어지는 상황에서, 소스 정점에서 싱크 정점으로 흐를 수 있는 최대 유량을 구하는 문제이다. 여기서 소스(source), 싱크(sink), 용량(capacity), 유량(flow)라는 개념이 등장한다.소스(source) 정점은 유량을 발생시킬 수 있는 정점이고, 싱크(sink) 정점은 유량을 흡수하는 정점을 의미한다. 그 외 정점들에서는 유량을 발생시키거나 흡수할 수 없으며, 자신이 받은 유량만큼 다시 흘려보내..
1. 파도반 수열 2 문제파도반 수열 2 문제는 다음의 링크에서 확인할 수 있다.https://www.acmicpc.net/problem/27435 파도반 수열 1 문제와 비교했을 때, 입력으로 주어지는 $N$의 최댓값이 $10^{18}$로 늘어났다는 차이가 있다. 제한이 커지면서 정답도 모듈러 연산을 적용하여 구하도록 변경되었다. 2. 문제 풀이(1) 파도반 수열의 점화식파도반 수열의 점화식은 다음과 같다.$P_i = P_{i - 2} + P_{i - 3}\ (i \ge 4),\ P_1 = P_2 = P_3 = 1$$P_i = P_{i - 1} + P_{i - 5}\ (i \ge 6),\ P_1 = P_2 = P_3 = 1,\ P_4 = P_5 = 2$ 이 두 점화식이 왜 같은지는 이전 글에서 간단하게..
