구현문제를 잘 푸는 방법

구현문제를 잘 푸는 팁입니다.

디버깅을 할 때 굳이 메모장을 이용해서 풀 필요는 없습니다. 코드로 보여드리겠습니다.

백준의 14502 문제를 풀겠습니다.

이 문제는 세 가지의 큰 로직으로 구성되어 있습니다. 

첫 번째 로직은 벽을 세 개로 세운다는 로직 입니다. 그 다음 로직은 벽을 세운 다음에 바이러스를 퍼트리는 조직이 필요합니다.

벽이 있는 지점 까지는 바이러스가 가는데, 벽이 막혀져있으면 안전영역은 바이러스가 침투를 못하니까, 바이러스 스프레드라는 로직이 있겠죠.

세 번째 로직은 안전 영역을 count 하는 로직이 필요합니다.

여기서 하나 더 나아가서, 아까 벽을 세 개를 세운다고 했잖아요. 사실은 모든 경우의 수를 체크해야 합니다.

사실은 이 문제가 모든 경우의 수를 체크 하는 완탐이라는 것을 알려면 최대범위를 체크해가지고, 그걸 기반으로 시간복잡도를 계산해서 하는건데, 일단은 도식화에 초점을 맞출 거니까 이런식으로만 설명을 할게요.

 

이 문제는 이 세 개의 로직을 구현하기만 하면 되는 거예요.

벽을 세 개를 세운다는 건 모든 경우의 수니까, n * m C 3이 되는 거죠. 모든 맵에서 벽 3개를 세운다.

벽 3개를 세우고, 그때마다 바이러스를 퍼트리고 그때마다 안전 영역을 counting 하는, 이 세 개의 로직이 필요하다는 거예요. 이걸 잘 해야돼요. 여러분 이 문제를 보시고 이러한 조직들로 이루어져 있다는 걸 알아야 돼요. 

종이에다가 1번, 2번, 3번 이렇게 로직을 나누고 그림을 그려보셔야 돼요.

 

여러분이 구현 문제를 풀 때, 잘 안 돼서 계속 고쳐 보다가 시간이 모자라서 못 푸는 경우가 많은데,

그런 실수를 안하시려면 첫번째는 이런 식으로 도식화를 그려가지고 문제를 100% 이해해서 그걸 기반으로 '이러이러한 로직으로 문제를 푸는구나' 라고 감을 잡으셔야 됩니다.

 

문제를 풀 때 중요한 점은 처음부터 코딩을 하는 거예요.

굳이 메모장을 쓸 필요는 없습니다. 

열악하게 이렇게 준비하시고, 디버깅 툴을 사용할 수 없기 때문에 cout으로 디버깅하는 훈련도 해야합니다.

이게 기본꼴이죠. (6:30부터 구현문제 풀이 영상 보기 > https://www.youtube.com/watch?v=DBXEWJx2mIw&list=PLAH_MBit83J47GrRfyMiQzpbFBM0InGW9&index=1)

이렇게 벽을 세웠다면, 원복을 시켜야합니다.

이 경우의 수가 그 다음 경우의 수에 영향을 미치지 않도록, 원상복구를 시켜주는 거죠.

 

사실 저는 먼저 로직을 짜놓고, 그 다음에 변수를 만들 때가 많아요. 그게 더 빠르더라구요.

 

그리고 나서 go 함수도 만들기 ~ 이어서

---

쉬움2, 보통1은 구현문제를 실버 2문제, 골드 1문제씩 꾸준히 풀라는 것입니다. 

solved.ac에서 이렇게 검색하면 구현문제 중에서 실버문제를 볼 수 있습니다. 사람들이 가장 많이 푼 문제를 풉시다. 괜찮을 가능성이 높아요.

 

gold 같은 경우는 이렇게 검색하면 나오겠죠.

 

그리고 여러분, 삼성 SW 역량 테스트 기출 문제는 꼭 풀어주세요. 구현문제에서 시간을 많이 잡아먹는다고 하면 꼭 풀어서 연습하세요.\

 

쉬움2, 보통1 구현문제를 꾸준히 풀다보면 늘 수밖에 없습니다.

 

타자속도도 중요하고 자주 나오는 로직은 외워야됩니다.