취미가 알고리즘

https://www.acmicpc.net/problem/21923

상승 비행을 할 때 지나간 칸에 부여된 점수의 합 + 하강 비행을 할 때 지나간 칸에 부여된 점수의 합을 구합니다.

이 문제의 예제 입력 5번을 보시면 상승 비행과 하강 비행 시 좌표가 겹칠 수 있다는 것을 알 수 있습니다.

따라서 비행이 끝났다는 것은 "좌표가 맨 우측 아래이고, 하강 비행 중일 때"가 됩니다.

모든 좌표들을 대상으로 상승, 하강 비행을 해야하며, 기본적인 dfs에 중복 방문 체크를 위해 dp를 사용합니다.

dp[x][y][flag] : 좌표 (x, y)에 flag 상태로 도달했을 때 얻을 수 있는 최대 비행 점수

여기서 flag란 상승 비행인지, 하강 비행인지를 나타내며,

flag = 0이면 상승 비행, flag = 1이면 하강 비행입니다.

그리고 모든 좌표에 대해 상승, 하강 비행을 해야하므로 3차원 배열 dp를 사용합니다.

이 문제에서 입력은 음수도 주어지므로 dp를 최솟값으로 초기화해줍니다.

그리고 좌측 아래 좌표 (N - 1, 0)을 시작점으로 dfs 순회합니다.

현재 상승 비행 중이라면 현재 좌표에서 하강 비행으로 변경 후 최대 점수를 먼저 구해줍니다.

그 다음 현재 좌표에 대해 상승 / 하강 비행을 구분하여 다음 좌표로 진행해줍니다.

비행이 끝났을 때는 (N - 1, M - 1)에 하강 비행 중인 상태에 도달했을 때가 되겠고, 해당 좌표값인 list[x][y]를 리턴합니다.

다른 경우에는 ret의 max를 구한 후 자신의 좌표를 더한 값을 리턴합니다.

단순 상승만 하는 문제라면 간단하게 구할 수 있었지만 하강 비행이 추가되어 생각이 필요한 문제였습니다.

https://www.acmicpc.net/problem/12978

오랜만에 알고리즘 포스팅입니다.

N개의 도시와 N - 1개의 도로인 것으로 보아 트리 문제인 것으로 파악할 수 있으며,

최소 갯수의 경찰서를 세워 모든 도시, 도로를 감시해야 합니다.

모든 도시들 대상으로 경찰서를 세우는 경우, 세우지 않는 경우를 모두 구한다면 시간초과가 발생할 것입니다.

따라서 dp를 추가하여 treedp로 접근합니다.

dp[v][flag]: 현재 도시가 v이고, 상태가 flag일 때 세워야할 경찰서의 최소 갯수

여기서 상태란, 현재 도시에 경찰서를 세울지 결정하는 변수입니다.

flag = 1 일 때, 해당 도시에 경찰서를 세우고,

flag = 0 일 때, 해당 도시에 경찰서를 세우지 않는 경우입니다.

이러면 다음 도시부터는 계산하기 수월해집니다.

현재 도시에서 경찰서를 세웠더라면 다음 도시에서는 경찰서를 세워도 되고, 세우지 않아도 됩니다. 즉, 두 경우 모두 확인합니다.

현재 도시에서 경찰서를 세우지 않았더라면 다음 도시에서는 경찰서를 무조건 세워야 합니다. 즉, 하나의 경우만 확인합니다.

마지막으로 해당 경우의 합의 최솟값을 출력합니다.

알고리즘

1일 1알고리즘

자율 프로젝트

이번주 결선 발표회까지 모두 마무리되었다.

그리고 실습코치 업무도 종료되었다.

후기

이번주에 코치 업무도 마무리되었고, 집도 구했다!

연장 신청은 했지만 결과는 기다려야 하고, 다가오는 면접 준비에 집중할 것이다.

저번주 진행하지 않았던 Spring 스터디는 내일 진행할 예정이고, 준비는 내일 오전부터 마무리할 예정이다.

최근에 다른 사람이 내 블로그 글을 참고하여 문제를 풀거나 관련 레퍼런스로 소개를 한 것을 봤다.

혼자 공부하기 위해 포스팅하였지만 다른 사람의 도움이 되었다는 것, 누군가가 내 블로그를 소개한다는 것 자체가 신기하게 다가왔다.

다른 사람도 내 글을 본다는 사실을 깨달았고, 정확한 정보만 다루기 위해 더 열심히 해야겠다는 생각이 든다.

그럴려면 우선 글부터 올려야 하지 않을까? ^^

알고리즘

1일 1알고리즘 실천

자율 프로젝트

이번주에 지역 본선 발표회를 진행하였다.

나는 발표회 전 대체 업무를 담당했던 반에서 발표 피드백 진행하였다.

다음주면 결선 발표회고, 내 업무도 끝~

후기

이제 5월도 끝, 코치도 끝

이제 내가 할 일은 집 구하기, 면접 준비, 코치 연장 준비 정도가 될 것 같다.

지금까지 했던 6기 코치 생활 돌아보면서 마무리 해야겠다!

알고리즘

1일 1알고리즘

자율 프로젝트

이번주 최종 발표가 끝났다.

반 1, 2등 팀이 정해졌고, 다음주는 본선 발표 진행될 예정이다.

나는 다음주에 마무리를 준비할 것 같다.

Spring 스터디

이번주로 1주차 스터디가 시작되었다.

전에 CS 스터디 했던 것과 비슷한 방식으로 진행했다.

새로운 개념들을 많이 알 수 있어서 유익한 시간이었다.

후기

1일 1알고리즘도 벌써 300일이 넘었다.

코치 생활은 거의 마무리되고 있고, 이사 준비를 하느라 시간이 바쁘게 흐르는 것 같다.

최근에 내가 잘 하고있는지 의심이 들 때가 있지만 상반기 안되면 하반기 올인하자는 생각으로 하는 중이다.

내가 부족한게 뭔지 잘 알고 있으니 스터디도 하는만큼 열심히 해야겠다.

https://www.acmicpc.net/problem/16946

값이 1인 칸을 0으로 변경했을 때 해당 칸에서 이동할 수 있는 칸의 수를 출력하는 문제입니다.

맵의 크기가 1000 * 1000이고, 모든 1의 칸을 대상으로 탐색하기에는 무조건 시간초과라는 생각이 들었고,

생각해낸 방법은 값이 0인 인접한 칸들에 넘버링을 부여한 후 넘버링의 크기를 더하는 방식입니다.

이것은 bfs를 통해 할 수 있습니다.

방문했던 모든 칸에 대해 넘버링과 카운팅을 합니다.

모든 인접한 칸들의 방문을 마쳤다면 해당 넘버링에 카운팅했던 수를 넣습니다.

그러면 남은 일은 값이 1인 칸에 대해 4방향 탐색하여 인접한 넘버링의 카운트를 모두 더하는 일입니다.

[boj 16932 모양만들기(링크)]에서 하나의 칸을 변경하여 만들 수 있는 모양의 최대 크기를 구한 적이 있습니다.

이 방식과 동일하게 접근하고, 중복된 칸을 예외처리 하기 위해 set을 사용합니다.

알고리즘

1일 1알고리즘 실천

자율 프로젝트

사실상 개발 마지막 주고, 다음주에 최종 발표가 있다.

지금까지 진행 상황을 알아봤을 때 전체적으로 규모가 작은 느낌이 있는 것 같지만 다들 열심히 하고 계신 것 같다.

코치도 이제 2주남았는데 마무리 잘해야겠다.

토이 프로젝트

기능 설계를 토대로 개발 진행 중이다.

웹 개발 감 찾기 위해 시작했지만 코치업무 + 취업준비 (핑계)로 진행 속도는 엄청 느리지만 개념을 알아가는 것이 중요하다고 생각한다.

후기

벌써 코치도 끝나가고, 취업은 못했고, 당분간은 백수로 취준을 해야할지도 모른다.

집도 슬슬 알아봐야하고 생각보다 할게 많으니 정신 차려야겠다.

https://www.acmicpc.net/problem/5547

위 그림의 좌표와 상관없이 저는 (1, 1) ~ (N, M)으로 입력을 받았습니다.

나중에 x의 좌표에 따라 인접하는 좌표들만 구분하면 되는 것입니다.

이 문제의 핵심은 건물 외부 체크를 어떻게 하느냐입니다.

왼쪽 건물들을 보시면 내부에도 흰색이 존재합니다. 이거를 잘 걸러내야 합니다.

저는 배열의 크기를 (N + 2, M + 2)로 설계하였고,

(1, 1) ~ (N, M)에 건물 정도를 입력 받아 가장자리에 있는 좌표에는 모두 건물 외부가 올 수 있게끔 하였습니다.

(0, 0)이나 (N + 1, M + 1)에 있는 것은 무조건 건물 외부 (흰색) 입니다.

그러면 무조건 흰색이 되는 (0, 0)을 시작으로 bfs를 돌려 건물 외부들을 모두 체크할 수있습니다.

이후 건물을 bfs로 순회하여 각 좌표에서 인접한 건물이 몇 개 있는지 세어 줍니다.

이 때, 건물 외부의 흰색은 카운팅을 하지 않으며, 건물 내부의 흰색은 카운팅을 합니다.

그래야 건물 내부에도 조명을 설치하지 않습니다. [위 사진 기준 (2, 3)이 예시입니다.]

카운팅이 완료되었으면 해당 좌표에서 조명을 설치할 벽면의 길이를 구합니다.

벽면의 길이는 인접한 건물이 0개 ~ 6개인 경우가 동일하므로 직접 그려보시면 알 수 있습니다.

https://www.acmicpc.net/problem/16932

정말 오랜만에 알고리즘 포스팅입니다.

이 문제는 배열의 값이 0인 한 칸을 1로 변경하여 만들 수 있는 모양의 최대 크기를 구하는 문제입니다.

이 문제에서 모양이란 배열 내에서 1로 이루어진 연결 요소입니다.

저는 bfs를 통해 1로 이루어진 모양들을 넘버링하여 해당 넘버링의 크기를 vector에 넣어주었고,

브루트포스를 통해 값이 0인 칸들의 인접한 칸들의 크기 합을 구해 max를 구하였습니다.

이 때, 인접한 칸에서 같은 넘버링이 나올 수 있으므로 중복체크를 위해 set을 사용하였습니다.

넘버링했다는 것은

0 1 1
0 0 1
0 1 0

이렇게 되어있는 배열을

0 1 1
0 0 1
0 2 0

이렇게 모양별로 구분할 수 있도록 변경하였습니다.

이 상태에서 브루트포스로 모양들을 연결해주는 것입니다.

여기서 인접한 칸에서 같은 넘버링이 나오는 경우는 좌표 (1, 1)을 보시면 이해하실 수 있습니다.

0 1 1
0 0 1
0 2 0
(1, 1)을 1로 변경한다고 했을 때 위(0, 1)와 오른쪽(1, 2)은 같은 넘버링을 가진 모양입니다.
이미 같은 모양에 속하므로 이를 중복으로 더해서는 안됩니다.
따라서 중복체크를 위해 set을 사용하였습니다.

알고리즘

1일 1알고리즘 실천

자율 프로젝트

교육생분들은 프로젝트 진행 중, 나는 각 반 돌아다니는 중

미팅 요청이나 질문은 없는걸로 봐서 잘 진행 되고 있는것 같다.

아니면 내가 있는걸 모르는건가..? ㅎ

다음주도 대체업무 예정되어 있다.

Spring 스터디

CS 스터디가 끝나고 바로 다른 멤버와 Spring 스터디를 시작하였다.

아직은 스터디 진행 회의만 진행하였고, 다음주부터 본격적으로 스터디 진행할 예정이다.

후기

휴일이 겹쳐서 그런지 시간이 더 빨리 지나간 것 같다.

벌써 5월이고, 실습코치로의 마지막 달이니 마무리 잘해야겠다는 생각이 들고,

코치가 끝나게 된다면 앞으로의 계획을 잘 세워서 부족한부분 빠르게 채워야겠다.

알고리즘

1일 1알고리즘 실천

자율 프로젝트

반 하나씩 돌아다니면서 각 팀의 진행상황 파악을 했다.

다 확인한건 아니지만 대체업무도 수행하면서 더 알아볼 예정이다.

토이 프로젝트

설계가 얼추 마무리 되면서 개발도 시작하려고 한다.

DB 설계는 마무리되어 Entity와 초기 데이터 생성부터 하려고 한다.

CS 스터디

이번주로 CS 스터디는 마무리되었다.

예정되어 있진 않았지만 준비했던 모든 파트가 끝났고, 스터디원들과 한 바퀴 더 돌지, 끝낼지에 대해 회의를 하였고, 마무리하기로 했다.

재정비의 시간을 갖고, 2기를 하자는 의견도 나왔어서 생각이 필요할 것 같다.

후기

벌써 5월이다. 시간 너무 빠르다.

취업 준비를 위해 CS 스터디를 했었고, 개발 역량을 키우기 위해 Spring 스터디를 하려고 한다.

함께할 스터디원은 모두 구했고, 조만간 진행 방향에 대해 회의를 하려고 한다.

CS도 복습 해가면서 준비 잘해야겠다.

알고리즘

1일 1알고리즘 실천

저거 스트릭 컬러를 랜덤으로 변경할 수 있는 컨텐츠가 생겼다.

다이아 티어 색으로 변경하고 싶어서 별조각 1만개를 썼는데..

맨 밑에 티어 색상은 해당 티어를 달성하지 못하면 못 받는다고 하는걸 뒤늦게 봐버렸다.

아 내 별조각 ㅠ

문제 더 풀어서 채워야겠다.

자율 프로젝트

이번주 중간 발표를 진행했다.

각 팀에서 기획 발표를 하는 것을 보았지만 다른 반의 진행 상황을 파악하기 힘들어 이 부분을 생각해봐야 할 것 같다.

토이 프로젝트

웹 개발한지 너무 오래됐는지 기술적인 부분들을 많이 잊어버려서 뭔가 해야할 것 같은 생각이 들었다.

마침 뜻이 맞는 분이 있어 같이 진행하게 되었고, 기획, 설계 진행했다.

다음주에는 설계 마무리, 개발 진행될 것 같다.

후기

코치 생활 남은기간 1달, 내 남은 취업 현황 0 ㅠ

내 부족한 부분을 보완하기 위해 웹 개발, CS 공부를 집중적으로 하려고 한다.

최근에 나도 모르게 번아웃이 왔는지 의욕이 떨어진 느낌이 좀 있어서 이번 주말은 푹 쉬었으니 다음주에는 열심히 해야겠다.