🐢 알고리즘 강의
유튜브
바킹독의 실전 알고리즘강의를 듣고 내용을 정리합니다.
🍀 대회 종류들
-
ICPC: 가장 큰 대회. 서울 리저널, 하노이 리저널, 다낭 리저널 등 다양함. -
SCPC: 삼성에서 주최하는 프로그래밍 대회 -
카카오 코드페스티벌 -
SCTF: 삼성전자에서 주최하는 대회
🍀 각종 알고리즘 사이트
-
Codeforces: 온라인으로 사용자들끼리 알고리즘 역량을 겨룰 수 있는 사이트 -
백준 온라인 저지: 어떤 테스트 케이스에서 틀렸는지는 알려주지 않음. -
프로그래머스: 여기는 각 테스트 케이스에 대한 결과를 다 알려줌.
단, 테스트 케이스가 많이 빈약해서 잘못된 코드임에도 불구하고 통과될 수 있음. -
구름: 여기도 각 테스트 케이스에 대한 결과를 다 알려줌. -
SW Expert Academy: 삼성에서 직접 운영하는 플랫폼. 삼성 sw 역량테스트가 동일한 플랫폼에서 진행되기 때문에 삼성 sw 역량테스트를 응시하기 전에 여기를 한 번은 써볼 필요가 있음.
여기서는 번호를 알려주는 대신 몇 개를 맞았는지 알려줌. 그런데 꼭 주의해야 할 점은, 실제 시험장에서는 제출했을 때 시간초과가 났는지 여부만 알려주고, 시간초과가 나지 않았다면 그냥 제출이 되었다는 안내만 나옴. 설령 테스트케이스에서 틀린 것이 있다고 해도 알려주지 않고 그냥 제출이 됨. 그래서 실제 시험장에서는 제출이 되길래 그 문제를 맞은 줄 알았는데 막상 알고 봤더니 그 문제를 틀려서 불합격하는 경우 종종 발생.
이런 일을 최대한 줄이려면 주어진 예제들에 대해서 올바른 답이 나온다고 그냥 제출을 해버리는게 아니라, 자기가 직접 다양한 테스트 케이스들을 생각해서 그것들에 대해 올바른 답이 나오는지를 꼼꼼하게 확인한 후에 제출해야 함.
🍀 강의 소개
✔️ 강의 대상
C/C++ 언어를 알고 있지만 자료구조/알고리즘은 약한 취준생, 학부생, 비전공자를 대상으로 하는 강의.
✔️ C++ 언어
C++ 공부를 안 했을 경우 생소할 수 있는 C++문법들에 대해서는 설명을 해주기 때문에 강의와 함께 C++ 공부도 병행하면 됨.
코딩테스트는 C/C++로 보는게 좋음. 기본적으로 자바/파이썬은 동작 속도가 느려 전수조사 문제에서 손해를 보고, 인터넷 상의 자료도 C/C++에 비해 많이 부족하기 때문.
✔️ 강의 내용
자료구조/알고리즘이 실제 어떤 문제들에서 쓰이는지, 그리고 어떻게 구현을 효율적으로 할 수 있는지를 깊게 다룸.
해쉬와 같이 현실적으로 코딩테스트에 나올 가능성은 0에 가깝지만 그냥 넘어가기엔 아쉬운 개념들은 "면접에는 충분히 물어볼 수 있지만 코딩테스트를 대비할 땐 필요가 없다"와 같은 설명을 덧붙여 놓음.
✔️ 강의 목표
강의의 목표는 삼성전자 SW Test A형과 B형 중간 수준의 코딩테스트를 통과할 수 있게끔 하는 것. 이 정도 난이도면 어떤 기업의 코딩테스트를 준비하더라도 다 커버 가능.
✔️ 연습문제와 공부방법
각 단원에는 연관이 있는 연습문제들이 매우 많이 제공됨. 적어도 세 문제에서 다섯 문제 정도는 푼 후에 다음 강의로 넘어갈 것. 모든 강의를 다 듣고 나면 산더미같이 쌓인 문제들을 주구장창 풀면 됨. 자기가 많이 짜봐야 느니까 꼭 많이 짜보기!
주말 없이 알고리즘만 하루 8시간 이상 공부하면 2~4개월 안에 끝낼 수 있고, 다른 활동과 병행할 경우 넉넉하게 적당히 4~6개월 정도 걸림.
0x12강 이후의 내용들도 코딩테스트에 충분히 나올 수 있지만 보통은 대부분의 문제들이 0x11강 이전의 내용들 정도로 나오는 경우가 많고 특히 삼성 A형 같은 경우도 대놓고 출제 범위를 알려 주는건 아니지만 일단 지금까지는 전부 BFS/DFS/백트래킹/시뮬레이션 문제였기 때문에 시간이 부족하다면 0x11강까지만 마스터하기.
🍀 코딩 테스트란?
✔️ 코딩테스트란?
코딩테스트란, 주어진 문제를 정해진 시간 제한과 메모리 제한 내로 해결할 수 있는 능력을 측정하는 테스트.
✔️ 코딩테스트 채점 방식
코드를 채점한다는 것은 누군가가 수동으로 코드를 하는게 아니라, 숨겨져 있던 수많은 입력 데이터들에 대해 프로그램의 출력이 올바른지 확인한다는 의미.
이 때 이 입력 데이터는 문제에서 주어진 입력의 제한 조건을 만족한다는 것이 보장됨.
예를 들어 문제에서 두 수가 10 이하라는 조건이 있으면, 주어진 입력이 진짜 그 조건을 만족하는지 따로 if문으로 확인할 필요 없이 10 이하가 맞다고 생각하고 코드를 짜면 됨.
코드의 채점을 진행하는 입력 데이터를 테스트 케이스(Test Case)나 줄여서 TC라고 부름. 대부분의 경우 단 한 개의 테스트케이스라도 통과하지 못한다면 그냥 그 문제를 틀린 것이고 부분점수 없이 아무런 점수도 획득 못함.
채점이 종료된 후에 플랫폼에 따라 단순히 틀렸다는 것만 알려주거나 몇 번째 테스트 케이스에서 틀렸는지와 같은 추가 정보를 더 주기도 함. 단, 착각하면 안되는 것은 그 어떤 코딩테스트에서도 실제 어떤 입력에 대해 오답을 내었는지는 절대 알려주지 않음.
그렇기 때문에 내 코드가 틀렸을 때 어떤 반례가 존재하는지 찾는게 꽤 어렵지만 정말 필요한 능력이며 꼼꼼하게 코딩하는 습관을 길러야 함. 이건 하다 보면 늘 것임!
🍀 코딩 테스트에서 좋은 성적을 내기 위해 필요한 능력
✔️ 1. 배경지식
다양한 알고리즘, 자료구조, 기타 테크닉 등과 같이 문제를 해결하기 위해 필요한 지식을 의미.
강의를 잘 따라가면 무난하게 잘 습득할 수 있음.
✔️ 2. 문제 해결 능력
배경지식을 지금 당면한 문제에 맞게 잘 변형해서 적용시키는 능력을 의미.
각 단원에서는 대표적인 몇 개의 문제만 같이 고민하고 넘어가기 때문에 전형적인 문제의 풀이는 떠올릴 수 있을테지만, 문제가 변형이 되었을 때에도 이 문제에서 요구하는 알고리즘이 무엇인지를 알아내는 능력이 필요함.
이건 각자 해당 단원의 주제에 맞는 다양한 문제를 접해보면서 조금씩 성장할 능력. 즉 문제해결능력은 강의만 본다고 해서 크게 늘지 않고 스스로의 노력이 많이 요구됨.
✔️ 3. 구현력
본인이 생각한 풀이를 코드로 잘 옮겨낼 수 있는 능력을 의미.
분명히 풀이는 알겠는데 막상 코드를 짜보니까 답이 안 나온다, 혹은 짜다가 꼬였다 하는 경우가 많음.
이런 상황을 막기 위해 문제를 많이 풀어야 하는 것은 물론이고, 특히 입문 단계에서는 내가 맞은 문제도 다른 사람이 어떻게 구현했는지를 살펴봐서 좋은 코드는 흡수하며 자신에게 최적화된 코딩 스타일을 계속 구축해가는게 좋음.
참고 링크
