1강과 2강이 많은 분들께서 좋아해 주셔서 감사합니다! 이 공부법이 처음에는 시간대비 더 적은 문제를 풀고 더 많은 알고리즘을 배울수는 없겠지만 여러분의 순수 실력은 정말 빠르게 늘게 되는 방법이니 따라 오시는 분들 모두 화이팅 입니다!
질문이나 알고리즘 외의 취업 질문들도 언제든지 가능합니다~
오늘은 지난강의에서 너무너무 중요해서 다루지 못했던 알고리즘 설계하기를 다뤄 보겠습니다.
왜 설계를 해야 할까?
1. 실력이 빠르게 상승한다.
새로운 알고리즘을 공부하시고 문제에 적용 해보려는 시점에서 직접 설계를 하다보면 이해가 가지 않던 부분들이나 시간 복잡도 알고리즘의 원리를 더 깊게 이해하거나 잘못된거를 바로잡게 되는 경우가 많습니다. 당장 쉬운 알고리즘을 공부하실 때는 크게 체감이 안갈 수도 있지만 순수하게 알고리즘 1개의 지식을 요구하는거보다는 서로가 공부할 때 얽혀있는 경우가 많기 때문에 하나의 개념을 확실하게 잡고 가실 수록 뒷부분에서 성장속도의 차이가 나게 됩니다.
2. 실수가 적어진다.
여러분이 문제를 푸시면서 하는 실수들이 있습니다.
문제를 잘못 읽기, 조건 잘못 보기, 설계 잘못하기, 타이핑 실수 이렇게 다양한 실수를 하시고 많이 겪게 되실 문제들입니다. 하나하나가 맞왜틀(맞는데 왜 틀려!!)를 유발하고 엄청난 스트레스를 발생 시키게 됩니다.
놀랍지만 설계를 하는게 위 4개의 실수들을 줄이는데 도움이 됩니다. 식당에 붙어있는 ~~재료의 효능 마냥 약파는게 아닙니다!
3. 오히려 문제를 푸는 속도가 빨라진다.
처음에는 못 느끼실수도 있지만 점점 어려운 문제를 푸실 수록 더 체감하게 되는 내용입니다.
다른 사람의 코드를 보다보면 코드가 엄청 짧다는 것을 알 수 있습니다. 즉 타이핑할 내용은 별로 없다는거고 문제를 푸는데 있어서 설계가 되었다면 코드를 치는 시간은 5분 ~ 10분이면 된다는 겁니다.
쉬운 문제는 머리로도 쉽게 설계를 할 수 있지만 골드 상위권 ~ 플레 하위권 (잘 안나오긴 하지만) 을 풀게 된다면 머리로 설계를 하는 것에는 한계가 있습니다. 이렇게 된다면 어쩔 수 없이 종이와 펜을 찾게 되는데
4. 틀린 부분을 찾기 쉽다.
제출 후 수정 작업이 코드에서 일어난다면 수정하기 전에 어떻게 되어있었는지 알기도 어렵고 어디를 내가 어떻게 바꿨었는지 까먹게 되고 코드가 점점 미궁으로 가게 됩니다. 하지만 설계 부분으로 돌악가서 다시 설계 했던 내용들을 복기 하면서 필기 부분을 고치고 코드를 고치거나 새로 친다면 훨씬 깔끔하게 찾을 수 있습니다.
설계를 한다는게 뭘까?
알고리즘을 어떻게 만들지를 적는거고 더 나아가면 코드를 어떻게 작성 할 것인지도 담기게 됩니다.
별찍기로 예시를 들어보겠습니다. 아니 뭐 이렇게 쉬운걸 풀어라고 생각하실 수도 있는데 한번 봐주세요!
2445번: 별 찍기 - 8
첫째 줄부터 2×N-1번째 줄까지 차례대로 별을 출력한다.
www.acmicpc.net
다음과 같은 모양이 나와야 하는 문제입니다. 이정도 문제는 껌이지 하고 코드를 완성 했습니다! 이제 출력을 해보니
아이고 가운데 줄을 출력하는걸 까먹었었네요 한줄을 추가하고 제출을 하였고 정답을 맞았습니다!
끝난걸까요? 아니요! 이렇게 풀면 다음에 비슷한 문제를 풀 때 똑같은 실수를 할 확률이 높고 얻어 가는게 없습니다.
우리의 목표는 설계도를 보고 바로 코드를 보고 칠 수 있도록 설계를 하는겁니다.
설계 순서
문제를 잘못 읽기, 조건 잘못 보기 실수를 하지 않기 위해 가장먼저 문제와 조건을 꼼꼼히 읽고 변수들을 보면서 제한 되는 시간 복잡도를 체크 합니다. ex) nlog n 까지 가능, n^2, n^3
이후 예제를 손으로 그리면서 문제 자체를 완벽히 이해 하시는게 가장 먼저 선행되어야 합니다.
이후 단계에서 알고리즘 공부용과 실전용으로 나뉘게 됩니다.
1. 알고리즘 공부용
- 어떤 알고리즘을 적용해야 하는지 알고 있으니 문제와 조건, 배웠던 알고리즘을 조합해서 설계를 들어가면 됩니다.
- 어떻게 적용을 해야 하는지 감이 안오면 완전탐색으로 문제를 설계해보고 알고리즘을 통해 시간 복잡도를 줄이는 방법으로 가면 됩니다. 이러기 위해선 해당 알고리즘을 언제 사용해야 되는지를 공부하면서 익혀야 합니다.
2. 실전용
- 어떤 알고리즘인지 모르기 때문에 조건과 문제를 더 꼼꼼히 읽은 뒤 가능한 시간 복잡도를 생각하고 적용 가능한 알고리즘들이 어떤게 있을지 생각을 합니다.'
- 문제와 조건만으로 감이 오지 않는다면 완전 탐색으로 문제를 설계 한뒤에 나오는 시간 복잡도를 보고 알고 있는 알고리즘들로 시간 복잡도를 최대한 줄여 조건을 만족하는 알고리즘을 찾습니다.( 결국 여러분이 그동안 공부 했던 알고리즘 중 하나 일겁니다. )
설계를 했다면 예제 등을 설계한 과정을 따라 돌려보면서 확인을 한 뒤에 타이핑을 하시면 됩니다.
예시 1 : 별찍기
가장 먼저 문제와 조건을 보고 중요한점을 캐치 해줍니다.
그래야 되는데 조건은 1초이니 1억번의 연산을 가정하고 풀면 되고 N이 나오는데 최대 100이니 3제곱 도 충분히 가능하겠네요 이후
문제를 읽어보니 예제를 보고 규칙을 유추하라고 합니다. 우선 예제 정도는 한번 그려줍니다.
보니까 별이 찍히고 공백이 나왔다가 다시 별이 나오는 구조이네요 대충 뭐 2중 for문으로 하면 될거 같긴하지만 참고 설계를 계속 이어가 봅니다.
처음 그릴때는 행의 시작을 국룰인 0부터 시작을 했지만 설계를 하려다보니 이번 문제는 1부터 하는게 더 편할거 같아서 1~5 와 1~4 로 두 부분으로 분리를 해줬습니다.
별이 찍히는걸 파랑으로 하고 공백을 빨강으로 하니까 좌우 대칭이고 빨강의 점이 찍히는게 ( 5 - (별의 수) ) x 2라는걸 알 수 있습니다.
그리고 다시 점을 찍는 걸 반목하면 되곘네요
0행붙터 4행까지 부분을 먼저 설계 한다면 위의 이미지와 같게 됩니다. 단순히 윗줄에서 말했던 것들을 for문으로 옮긴거라고 볼 수 있습니다. 이렇게 설계를 할 때 위의 내용들을 한글이나 영어로 쓰는게 아니라 간략화된 코드로 작성하는 것이죠 굳이 정형화된 수도 코드가 아니라 본인이 알아 볼 수 있음면 됩니다. 단 헷갈리지 않게 본인만의 규칙을 잘 정하는게 중요합니다.
이후 비슷한 아래 부분까지 설계를 해줍니다.
지금은 예제이기 때문에 N이 아니라 5로 되어 있는데 수정을 해주고 완성본을 봅니다.
짜잔~ 이제 우리는 이걸 보고 그대로 본인의 언어게 맞게 타이핑을 하면 됩니다.
여기서 궁금증이 있으실 수 있습니다.
"아니 이거 그냥 코드랑 똑같은거 아니야? 강의 3개를 봤는데 사기꾼이었나? "
그런 생각이 드시는게 이제 설계가 잘 된겁니다. 이런 부분까지 해야하나? 싶은 부분들 까지 (for 문 범위, 변수명, 조건들) 설계를 하실때 미리 하셔야 합니다.
다른 블로그들의 시간 복잡도 강의를 보셨다면 이제 대충 위의 코드는 O(N^2)라는 것을 알 수 있고 문제의 조건을 넘지 않는다는 것을 알 수 있습니다.
이제 알고리즘을 푸시는게 익숙해지시면 main부분은 건너 뛰시고 주요 함수 같은거만 설계를 하시고 본인에게 맞는 설계 방법을 찾아 가시면 됩니다. 단 보고 바로 코드를 쭉 쓸 수 있을 정도로는 해야됩니다.
다른 예시들
다른 문제들 예시들도 보여드리겠습니다. (지금 배우고 있는 친동생)
대략 문제만 읽어보시고 어떤 식으로 설계가 되는지 보시면 됩니다!
1493번: 박스 채우기
세준이는 length × width × height 크기의 박스를 가지고 있다. 그리고 세준이는 이 박스를 큐브를 이용해서 채우려고 한다. 큐브는 정육면체 모양이며, 한 변의 길이는 2의 제곱꼴이다. (1×1×1, 2×2×2,
www.acmicpc.net
해당 문제는 3D로 바로 넘어 가는게 어려워서 2D조건으로 문제를 바꿔서 푼 뒤에 3D로 확장 시켜서 문제를 풀었습니다.
https://www.acmicpc.net/problem/9663
9663번: N-Queen
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
약속과 달리 글이 늦어 졌네요
이제 여러분은 알고리즘을 새롭게 공부하는 법을 배우셨고 블로그와 백준이면 혼자 코테까지 뿌실수 있도록 성장 하실 수 있게 되었습니다.
하지만 "이딴 글만 읽고 내가?? " 라고 생각 하실 분들이 있을 수 있기 때문에 다음 4강에서는 완전 탐색에 대한 기본적인 설명 (많은 분들이 놓치시는 백트래킹) 에 대해 설명하고 문제 1~2개를 설계 하는 과정까지 담아보도록 하겠습니다 가능하다면 영상으로 찍어보겠습니다!
코테, 취준 관련 다양한 질문 주셔도 됩니다! 다들 화이팅
'취업 준비' 카테고리의 다른 글
| 🧑💻 개발자로 취업하기 위한 알고리즘 공부법 2강 공부방법 (0) | 2022.02.20 |
|---|---|
| 🧑💻 개발자로 취업하기 위한 알고리즘 공부법 1강 코딩테스트 (2) | 2022.02.20 |
| 21년 하반기 취업 도전기 + 카카오 인턴 (0) | 2021.10.01 |
| 코딩테스트 준비하기 (10) | 2021.06.25 |
| 21년 상반기 취업 도전기 (0) | 2021.06.23 |