2024년 알고리즘 스터디
2024년도가 되었습니다!!! 다들 새해 복 많이 받으세요~
작년 겨울부터 발을 동동 구르면서 친구와 24년도가 되면 1월 1일부터 당장 알고리즘 스터디를 시작하자!
라고 다짐했거든요. 그래서 진짜로 시작했고 제대로 한번 해보려고 합니다.
이전에도 몇번 대학 동기들과 알고리즘 스터디를 진행한 적이 있는데요?
좋게 말해 세미나 즉, 발표까지 한다고 해도 고작 내 코드 보여주면서 이렇게 하니까 되더라 식이었고
설명을 잘 하지는 못했던 것 같습니다.
또 기존에는 제가 파이썬을 썼는데, 최근에 조교 일을 하면서 알고리즘 수업을 수강하는 친구들 대부분이
c++을 사용하는 걸 보고 저도 c++을 써보려고 합니다.
물론, 문자열 문제를 제외하구요...
친구는 java 또는 javascript 언어로 푼다고 하고, 저는 c++에 도전하는 걸로 하였기 때문에
어짜피 코드를 보여주면서 하는 코드 리뷰 형식의 스터디는 불필요하다고 생각했어요.
대학원 생활을 할 때에도 내가 일한 내용을 설명할 때 코드를 보여주면서 여기를 보면... 이렇게 되는데...
식으로 설명하면 듣는 입장에서 정말 난해하다는 걸 많이 느꼈거든요.
그래서 원리를 이해하기 쉽게, 핵심적인 아이디어를 공유하는게 좋다고 생각했습니다.
저도 학부 시절 알고리즘 과목을 들은적이 있지만, 그 때도 아이디어를 잘 설명하고 싶었는데 막상 발표를 하려고 하니 잘 안되더라고요. 지금은 좀 괜찮아졌다고 생각합니다. 이번 스터디 1주차를 진행하고 정리를 해보는 시간을 가졌는데 저 스스로 발전했다고 느꼈거든요.
잡담은 여기까지하고 제목에 나와있는 백준 2167, 2669, 14719 문제의 핵심 아이디어를 정리한 노트를 공유하도록 하겠습니다.
백준 2167
기본적으로 알고리즘 문제를 풀 때 중요한 것은 시간이 어느 정도 소요될지를 파악해야합니다.
이 문제의 경우 (300, 300) 사이즈의 정사각형에서 특정 좌표 (i, j)와 (x, y)가 주어질 때, (i, j)를 왼쪽 위 점으로, (x, y)를 오른쪽 아래 점으로 하는 직사각형 구간의 배열 합을 구하는 문제입니다.
그래서 최초 사각형 크기가 90000이고, 배열 합을 구해야하는 부분이 최대 10000개이므로, 좌표를 받을 때마다 (1, 1)에서 (300, 300)까지 하나하나 탐색하면서 합을 구하면 시간이 상당히 많이 소요됩니다.
따라서 저는 DP와 같이 풀어야한다고 생각했습니다.
최초에 (300, 300) 사이즈의 배열의 값들을 입력받으면서 채워나갈 때, 사각형 내의 임의의 좌표 (tx, ty)는 (1, 1)부터 (tx, ty)까지의 합을 가지고 있으면 됩니다.
그러면 그림과 같이 생각하여 (i, j)부터 (x, y)까지의 합을 구할 수 있습니다.
백준 2669
앞선 문제와 대비하여 엄청나게 쉬운 문제입니다.
직사각형을 그릴 때마다 2차원 어레이에 카운팅을 하면서 표시를 하면 됩니다. 그러면 중첩된 부분은 1 이상의 값을 가질테고, 어느 만큼 중첩되었는지 알 수 있기 때문에, 그려진 모든 직사각형의 넓이에서 중첩된 만큼 빼주면 답을 구할 수 있습니다.
백준 14719
이 문제의 경우 조건만 잘 찾는다면 마찬가지로 쉽게 풀 수 있습니다.
먼저, 간단한 조건으로 물이 무조건 고일 수 없는 곳은 첫번째 칸과 마지막 칸입니다.
다음으로 물이 고이는 곳의 조건은 '나'를 기준으로 왼쪽과 오른쪽에 나보다 높은 벽이 존재해야됩니다. 이 때 물은 왼쪽 벽과 오른쪽 벽의 높이 중 낮은 곳의 높이까지 물이 쌓일 수 있게 됩니다. 실제로는 '나'의 높이도 고려해야하므로 '나'의 높이를 빼주면 됩니다.
예시는 그림과 같습니다. 배열이 0부터 시작한다고 할 때, 1부터 N-1까지 탐색하며 물이 얼마나 고이는지 카운팅하면 답을 구할 수 있습니다.
각 문제별 소스 코드
2주차 계획
1주차 때는 실버 2문제와 골드 1문제를 풀었습니다.
다행히도 쉽게 풀 수 있었기에, 난이도를 조금 조정하여 2주차부터는 실버 2문제와 골드 2문제를 풀기로 하였습니다.
또한, 트리 그리고 BFS, DFS에 대해 각자 조사하여 발표하는 시간을 가지게 될 것 같습니다. 문제 역시 해당 알고리즘과 관련된 문제 4개를 선정하였습니다.
