[BOJ] 백준 500 SOLVE 후기

안녕하세요. 저처럼 취업을 위해 코딩 테스트를 준비하시는 분들에게 제가 작년부터 올해 3월까지 PS공부를 하면서 느낀 점들을 포스팅하려고 합니다. (도움이 되셨으면 합니다 ㅎ)

 

 

<그동안의 여정>

사실상 2019년과 2020년 12월 전까지는 생각날 때 한 두 문제 풀고 며칠간 안 풀고 이런 식이였던 것 같습니다. 그러나 12월부터는 이제 곧 대학교 4학년 2학기 종강이고 취업을 준비해야 한다는 압박감에 PS 문제풀이에 집중했던 것 같습니다.

 

solved.ac 사이트에서는 제가 푼 문제들에 대한 통계들을 볼 수 있습니다. 여기에는 레이팅 시스템이 있고 알고리즘 문제를 풀 때마다 난이도에 따라서 경험치가 쌓이는데, 뭔가 RPG 게임하는 느낌으로 문제를 계속 풀게 하는 동기부여가 되었던 것 같습니다.

그리고 문제 분류 그래프를 보면 풀이수가 부족한 문제 유형을 볼 수 있었는데 현재는 문자열과 그리디에 관한 문제풀이가 좀 더 필요한 것 같습니다.

 

 

 

 

 

<PS풀이의 시작>

저의 ps풀이의 처음 시작은 백준 단계별로 풀어보기였습니다. 학교에서 배운 기초적인 내용(if, for, while만 대충 아는 정도)으로만 문제를 읽고 안 풀리면 구글링 해서 해설 보고 문법과 풀이를 익히는 식으로 공부를 했던 것 같습니다.

(처음에 하노이탑이랑 프랙탈 구조로 별 찍기 문제로 많이 고민하고 어려워했던 기억이 나네요.)

 

현재까지 풀이 진행상황

 

 

<PS 풀이 노하우>

저의 경우 아직 취준생이고 최근에 몇 군데에 신입 개발자 채용 코딩 테스트를 본 적이 있습니다. 저도 막상 코딩 테스트를 보면 DP문제를 이렇게 많이 풀었어도 못 푸는 문제가 많습니다. 백준 500문제를 풀었다고 해서 결코 남들보다 코딩을 잘한다거나 빠르다고 생각하지 않고, 아직도 많이 부족하다고 생각합니다. 그러나 문제를 많이 풀면서 생긴 노하우는 꼭 도움이 되실 것이라고 생각합니다.

 

 

1. 문제를 확실히 이해하고 키보드에 손을 대자

문제를 대충 읽어보고 "이거는 구현이 좀 어렵겠는데?" 하면서 오랫동안 고민하다가 다시 문제를 읽었는데 오히려 쉬운 문제였던 적이 많았습니다. 또한 문제를 읽자마자 키보드에 손대는 습관을 고치려고 했습니다. 코딩하기 앞서 노트에 그림을 그려가면서 손 코딩과 가상 시뮬레이션을 돌려보고 시간 복잡도는 얼마일지, 메모리가 초과될지, 여기서 무한루프를 돌진 않는지 따져가면서 알고리즘을 생각하고 완벽하다면 그때서야 키보드에 손을 대는 습관을 들이는 것이 중요하다고 생각합니다. 

 

2. 이해하기 쉬운 코드가 좋은 코드다 (feat. 주석)

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int N, M;
int map[9][9];
bool visit[9][9];
int virus, wall; // 바이러스, 벽
int ans;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
vector<pair<int, int>> way; // 좌표 저장
queue<pair<int, int>> q; // x, y좌표

int BFS()
{
	// 방문 초기화
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			visit[i][j] = false;

	int cnt = virus; // 오염된 영역 크기

	// 바이러스 좌표들 큐에 삽입
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			if (map[i][j] == 2) q.push({ i,j });

	while (!q.empty())
	{
		int now_x = q.front().first;
		int now_y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int next_x = now_x + dx[i];
			int next_y = now_y + dy[i];

			// 범위에서 벗어나면 pass
			if (next_x < 1 || next_x > N || next_y < 1 || next_y > M)
				continue;

			// 방문하지 않은 길이라면
			if (!visit[next_x][next_y] && map[next_x][next_y] == 0)
			{
				q.push({ next_x ,next_y });
				visit[next_x][next_y] = true;
				cnt++;
			}
		}
	}

	// 전체크기 - (오염된 영역 + 벽 개수 + 3)
	return N * M - (cnt + wall + 3);
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;

	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
		{
			cin >> map[i][j];
			switch (map[i][j]){
			case 0: way.push_back({i,j}); break;
			case 1: wall++; break;
			case 2: virus++; break;
			}
		}
			
	// 벽 3개 세우기 시뮬레이션
	for (int i = 0; i < way.size(); i++)
		for (int j = i + 1; j < way.size(); j++)
			for (int k = j + 1; k < way.size(); k++)
			{
				// 벽 세우기
				map[way[i].first][way[i].second] = 1;
				map[way[j].first][way[j].second] = 1;
				map[way[k].first][way[k].second] = 1;
				
				// 안전영역 최대크기 저장
				ans = max(ans, BFS()); 
				
				// 되돌려 놓기
				map[way[i].first][way[i].second] = 0;
				map[way[j].first][way[j].second] = 0;
				map[way[k].first][way[k].second] = 0;
			}

	cout << ans << '\n';
}

저 같은 경우에는 문제를 풀 때 주석을 적는 습관을 들이고 있습니다. 위의 코드는 아까 풀었던 백준 - 14502번: 연구소 문제 풀이인데,  모든 부분에 주석을 적진 않지만 중요한 부분에는 주석을 적고 있습니다. 물론 코딩 테스트 상황에서는 일일이 주석을 적지는 않지만 복잡한 문제의 경우 주석을 적어가면서 풀면 잘 풀릴 때가 많았던 것 같습니다. 그리고 변수명을 설정할 때도 막 짓기보다는 누구나 쉽게 이해할 수 있는 변수명으로 만드는 것이 좋습니다. 심플하고 이해하기 쉽게 코딩하는 것을 좋아하는 성격이라 그럴 수도 있지만, 저는 남들도 이해하기 쉬운 코드가 좋은 코드라고 생각합니다.

 

3. 정 안 풀린다면 다른 사람 풀이를 참고하자

수업시간에 stack이 뭔지 어떠한 구조를 가지고 어떻게 동작하는지는 이론적으로 배웠으며, 지금 아주 간단한 스택 문제를 푼다고 가정하겠습니다. 하지만 이론적으로 완벽히 알고 있더라도 실전에서 어떻게 쓰이는지 알지 못한다면 무용지물이라고 생각합니다.(물론 이론 공부는 항상 중요합니다.)

즉, C언어로 설명드리자면 스택을 사용하기 위해서는  #include<stack> 부터 시작해서 stack<int> s; 로 스택 선언 push(), pop()함수를 써야 하며, iterator가 존재하지 않기 때문에 접근 혹은 탐색이 불가능하며, 스택이 비어있을 때 top() 함수를 쓰면 오류가 발생한다,,, 등등을 알아야 할 필요가 있습니다. 한마디로 다른 사람의 풀이를 참고하면서 자신이 부족한 부분을 인지하고 그 코드의 좋은 점을 가져오는 것이 중요하다고 생각합니다.

또한, 자신의 능력을 넘어서는 문제라고 생각되면 하루 종일 풀이에 매진하는 것보다 다른 사람의 코드와 알고리즘을 공부하고 다른 날에 다시 혼자서 풀어보면서 자신의 것으로 만들어야 합니다. 예시로 문자열 찾기 문제에서 꼭 KMP 알고리즘을 써야 통과가 되는데 이 알고리즘을 모르고 있다면 그 문제를 계속 붙잡고 있는 것은 시간낭비일 것입니다. 풀이 해설을 보고 문제 정답을 맞히는 게 중요한 게 아닌, 아무것도 없는 백지상태에서 풀이를 보지 않고 다시 문제를 풀 수 있는 것이 중요한 것 같습니다.

 

4. 단기적인 목표를 세우고 문제를 풀자

제가 RPG 게임을 좋아하는 이유는 제 캐릭터가 강해지고 성장하는 것이 눈에 즉각적으로 보이기 때문입니다.

solve.ac 사이트는 저에게 그러한 재미를 주어 동기부여가 되었습니다. (처음 사이트에 접속했을 때가 실버 IV)

티어가 상승할 때마다 블로그에 기록해두었고 장기적으로는 "플래티넘 달성", 단기적으로는 "티어 한 단계 상승 달성" 혹은 "이번 주 까지 총 풀이 문제수 300 달성" 등등 크고 작은 목표들을 설정하면서 지금까지 온 것 같습니다.

처음부터 "나는 이번 주 동안 100문제를 풀 거야"와 같이 달성하기 어려운 목표들을 설정하면 시도도 안 하고 포기할 가능성이 높다고 생각합니다. 달성하기 쉬운 목표들을 설정하면서 점점 난이도를 높여가는 게 좋다고 생각합니다.

 

5. 복잡하고 어려운 문제일수록 테스트 코드를 만들어보자

현업에서는 실제로 테스트 코드로 초기에 예상치 못한 버그들을 잡아 프로그램의 효용성과 안정성을 높인다고 합니다. 물론 고작 알고리즘 문제 하나 푸는데 테스트 코드를 만드는 것은 배보다 배꼽이 더 큰 상황이 될 수도 있습니다. 그러나 어렵고 복잡한 문제라면 테스트 코드로 답들을 출력해보면서 "여기서 인덱스가 배열의 범위를 넘어서는구나",  "입력이 이렇게 되었을 때 여기서 무한루프가 발생하네", "if문 조건이 잘못됐어" 등등 코드의 문제점이 가시적으로 보이기 때문에 추천드립니다.

 

6. 유형별로 정복하자

백준 100 solve 까지는 DP문제가 매우 어렵게 느껴졌고 손도 못 대는 경우가 많았습니다. 그러나 해당 유형의 여러 문제들을 풀어보면서 DP는 점화식을 세우는 것이 중요하다는 것을 감각적으로 익혀갔고, 문제의 입력의 개수를 봤을 때 DP로 푸는 것 외엔 시간 초과가 발생하겠다 라는 것을 감으로 알게 되었습니다. 즉, 무작위로 문제를 푸는 것이 아닌 하나의 유형에 능숙해질 때까지 풀어보는 게 좋습니다. 

백준에 알고리즘 유형별로 문제를 분류해놓았으니 자신이 부족한 유형을 공부하는 것을 추천드립니다. 

 

7. 시간이 많다면 백준을, 부족하다면 프로그래머스를

요즘은 프로그래머스로 코딩 테스트를 보는 회사가 많습니다. 따라서 프로그래머스의 환경에서 코딩해보는 것이 아주 중요합니다. 물론 백준 문제를 푸는 것도 실력 향상에 도움이 되지만 시간이 없다면 프로그래머스에 있는 문제를 풀어보는 것이 오히려 코딩 테스트에 도움이 될 것이라고 생각됩니다. (코딩 테스트를 볼 때 안 풀렸던 문제가 알고 보니 프로그래머스에 있는 문제여서 "프로그래머스 문제들 모두 풀어볼걸...." 하면서 아쉬워했던 적이 있습니다.)

또한 코딩 환경에 익숙해지는 게 중요하니 아직 프로그래머스를 사용해보시지 않으신 분들을 꼭 프로그래머스로 문제들을 푸는 걸 추천드립니다.

프로그래머스에 카카오 문제들 풀어보는 것 추천!

 

 

 

<앞으로의 여정>

사실 500문제를 푼 것도 플래티넘 달성이라는 목표 때문에 이룰 수 있었다고 생각합니다(사실 코딩 테스트보다는 자기만족 때문... 하하..). 3월 22일에 플래티넘을 달성하고 나서는 다이아를 찍고 싶은 마음이 생겼지만 접어두고 이제는 PS에 할애하는 시간보다는 취업 포트폴리오를 위한 토이 프로젝트에 신경을 써야 하는 것이 맞다고 생각됩니다. 자소서에 어필할 내용도 별로 없고 뭔가 성과가 없어서 저라도 이력서를 보고 저 자신을 뽑지 않을 것 같습니다.

 

2~3월 동안 프로그래머스로 53곳 정도 신입으로 지원서를 제출했는데 다행히도 3군데나 연락이 왔습니다. 두 곳은 코딩 테스트를 봤고 한 군데는 어제 화상 인터뷰를 진행했습니다. 코딩 테스트는 무난하게 봤던 것 같고 인터뷰는 자기소개, cs지식 등등 물어봤는데 많이 부족했던 것 같습니다. 

앞으로 할 것을 나열해보자면

- 면접 cs 예상 질문 공부하기

- 간단한 토이 프로젝트 여러 개 해보기 (FrontEnd : HTTP+CSS+JS, BackEnd : Node.js+MongoDB)
1. 회원가입, 로그인 서비스 
2. 버스정보조회
3. 채팅 프로그램

- 토이 프로젝트하면서 프레임 워크 사용해보기

- 깃허브에 익숙해지기 (토이 프로젝트하면서 버전 관리해보기)

- 백준보다 프로그래머스 문제들을 풀어보기

- (그리고 먼 훗날 백준 다이아 찍는 그날까지...)

 

등등이 있고 제일 중요한 건 역시나 프로젝트라고 생각합니다.

 

 

<마무리>

저보다 잘하시는 분들도 많으실 테지만 코딩 테스트를 준비하고 어려워하시는 분들에게 도움이 되었으면 하는 마음에 서투른 필력으로 후기를 적어보았습니다. 다들 코로나로 힘드실 텐데 모두 취뽀합시다!