알고리즘 코테 공부펌

 

코딩테스트 준비방법 및 알고리즘 공부

Flourish 090k 2020. 10. 5. 17:11

090k.tistory.com/32

코딩테스트 준비방법 및 알고리즘 공부

 

 

알고리즘을 공부하여 코딩 테스트를 통과하여 카카오, 삼성, 네이버 등 기업에 취직하고 싶은 사람들을 위해 조금이라도

도움이 되고자 글을 씁니다.

목차는 크게

1. 알고리즘을 공부해본 나의 경험과 느낀 점

2. 알고리즘을 공부하기 위해서 필요한 것들

3. 도움되는 사이트

3가지로 말하겠습니다.

 

실질적인 도움이 되는 부분을 알고 싶다면 목차 2부터 읽으시면 될 겁니다. 하지만 목차 1에는 저의 그 매애애애애애애애애애애우 답답했던 심정과 힘듬과 고난과 해결 과정을 적어 보려고 하니 읽어보면 재밌을 거라고 생각합니다

 

1. 알고리즘을 공부해본 나의 경험과 느낀 점

우선 저는 알고리즘을 1년 동안 공부해봤습니다. 

www.boj.kr 

이라는 사이트에서 플레 5를 찍고 

 

 

www.codeforces.com 

라는 사이트에서 민트,,,,(군 복무 중이기 때문에 대회를 못 나가고 있어요,,,ㅠㅠㅠㅠㅠㅠ 파란색 가즈아~~..)라는 랭크의 아이디를 보유하고 있습니다.

 

 

때문에 코드 포스 파랑 이상이거나 알고리즘 좀 한다는 분을 제외한 초심자들을 대상으로 얘기하겠습니다.

알고리즘? 내가 봤을 땐 요놈은 사람 심보를 터트리는 신기한 녀석이다. 이 놈하고 싸우려면 맘고생 씨게 할 각오를 하고 공부해야 하는데 왜냐하면 분명 내 풀이는 맞다고 생각하는데 컴퓨터에 제출하면 틀렸다 하고 아니 내 풀이가 맞다고 생각할깡이라도 있으면 알고리즘을 잘하는 것이다. 문제는 어떤 문제를 봤을 때 어떤 식으로 해결해야겠다는 생각이 하나도 안 드는 문제들 투성이다. 아마 알고리즘 공부를 조금 해본 사람이라면 알 것이다. 한 문제를 몇 시간 정도 붙들고 있어도 안 풀리는 문제가 있고 이제 막 for문과 while 문 등 기초적인걸 해결해도 다이내믹 프로그래밍, bfs, dfs 등등 공부해야 할 알고리즘은 계속 있는데 그 알고리즘을 이해하기도 힘든데 응용하기란 정말 힘듬의 연속이다.....

 

독한 마음으로 방학 때는 알고리즘만 하루 종일 붙들고 싸매어서 대학교 동아리실에서 하루 종일 코딩만 해서 백준 solved.ac에서 실버 1까지 만든 기억이 있는데 이제 와서 생각해보면 나는 그 힘듦 자체를 즐겼지만 역시나 문제를 1시간 동안 생각해도 답이 안 나오는 건 정말 멘탈 바사삭 의 연속이라고 생각한다.

그럼에도 알고리즘을 한 4개월 정도 했을 때 삼성 sw 기출문제들은 ' 아 이문제들은 완전 탐색과 귀찮은 구현만 잘하면 풀 수 있겠구나', '동적 프로그래밍은 결국 반복되는 부분을 다시 사용하면서 시간 복잡도를 줄일 수 있겠구나' 등등 기초적인 알고리즘은 이해하여 활용할 수 있는 수준이 되었고 그때부터 자신감이 들어 문제들이 하나하나 풀리고 이제야 노력한 것들이 조금씩 가치를 매겨지는구나 하면서 좋아했었다.

그러다 codeforces라는 대회 사이트를 알게 되었는데 보통 2시간 동안 문제를 풀어서 많이 풀수록 랭크가 높아지는 프로그래밍 대회이다. 나는 이때쯤 '아 알고리즘도 한지 오래됐는데 대회나 한번 해볼까' 하고 자신감 풀파워인 상태로 대회를 참가한 후 2시간 동안 1문제도 풀지 못한 그때의 나를 보면서 한 4시간 동안은 현자 타임에 빠져있었다.

지금 와서 보면 그때의 내가 1문제도 풀지 못한 이유는 그냥 실력이 부족해서였다. 그때 당시엔 내가 4개월이나 공부했는데 이거 1문제를 못 푼다고,,? 하면서 큰 상실감에 빠졌는데 결국 노력하면 문제들은 풀리게 되어 있는데 그 노력의 시간이 얼마나 걸리느냐는 사람마다 다르기에 알고리즘을 공부할 때 후회 없이 이 길을 택할지는 본인의 몫이라고 생각한다.

 

2020 3.2 일 군입대를 하고 현재 2020.10.4 일까지 꾸준히 매일 알고리즘 공부를 하여 나름 회사 대기업 문제도 거의 다 풀어봤고 대회도 가끔씩 codeforces라는 사이트에서 2시간이 주어지면 3~4개까지 풀 수 있는 실력과 내 생각에 나름 중급 알고리즘인 세그먼트 트리 등 다양한 알고리즘도 공부해봤다.

 

 

 

카카오 기출문제 경우 5시간 동안 7문제 중에 4문제를 풀면 통과라고 돼있었는데 3시간 동안 6문제를 풀었으며,

나름 나의 실력 향상을 위해 내가 생각하기에 꼭 필요한 것들을 적어보기로 맘먹었다.

 

 

2. 알고리즘을 공부하기 위해서 필요한 것들

- 문제를 풀기 위한 언어 선택(c++, java, python)

 현재 알고리즘 공부를 위해서 가장 많이 쓰이는 3가지 언어는 c++, java, python이다. 많은 자료들이 이 3가지 언어로

되어있으므로 이 3가지 중 한 개 혹은 2개를 골라서 공부를 시작하는 걸 추천한다. 

이때 공부는 개념서 한 권을 사서 컴퓨터로 타자도 쳐보면서 이해도 하면서 그개념서 한권을 다 이해한다는 목표로 공부하면 된다.

- 자료구조

 알고리즘과 땔 수 없는 관계인 자료구조는 꼭 알고리즘이 아니더라도 코딩을 하는 개발자라면 꼭 필수로 배워야 한다고 생각한다. 자료구조를 공부할 땐 c++, java,python에서 고른 언어로 된 책 한 권을 사서 시간 복잡도 가 무엇인지 stack, queue, 우선순위 큐, 어레이 리스트, 링크드 리스트, 트리 , 해쉬 맵 등등 개념들을 이해하면 된다.

여기서 자료구조가 중요한 이유는 

컴퓨터는 1초에 대략 1억 번 연산을 할 수 있다.

for(int i=0;i <100000000;i++){

} 이 for문이 실행하는데 보통 1초 정도 걸린다고 볼 수 있다.

 

 

 코딩 테스나 알고리즘 문제의 경우 시간제한이 있는데 이는 이문제를 풀기위해서 연산을 1초면 1억번 미만으로 쓰세요 와 같은 의미이며 연산을 더 조금 쓰기위해서 어떤 문제에는 어떤 자료구조를 써야하는지와 시간 제한이 1초이면 O(1), O(n), O(n^2), O(nlogn) 등의 시간 복잡도 중 어느 것까지 쓸 수 있을지를 알기 위해 자료구조를 배워야 한다.

-알고리즘

 알고리즘이라고 크게 어려워할 것 없이 대학교 학부 수준에서 필요한 알고리즘은 그렇게 많지 않다.

1). 문자열

2). 완전 탐색 (순수 완전 탐색, 백트래킹 등)

3). 수학(정수론, 조합론, 수학적 사고력 등)

4). 이분 탐색

5). DP

6). 그래프이론(dfs, bfs)

7). 탐욕 법

8). 재귀 (재귀, 분할정복 등)

9). 정렬 

10). 자료구조

정도만 해도 코딩 테스트를 합격하기에 충분하고

필요하다면 트리나 다른 알고리즘도 공부하면 될 것이다.

 

 

3. 도움되는 사이트 및 사용방법

- www.boj.kr  

Baekjoon Online Judge

 보통 이 사이트에서 solved.ac를 통한 문제 난이도를 보았을 때 골드 문제들 까지는 풀 수 있다면 한국에서 코딩 테스는 통과할 수 있다고 한다.

- www.codefoces.com

Codeforces

이 사이트에서는 색깔별로 레드-오렌지-보라-블루-민트-그린-회색이 있는데

블루는 한국기업 코딩 테스트는 무난히 합격할 수 있다고 한다.

이 두 사이트의경우 구글링을 해보면 사용법들이 자세하게 나와있다.

 

여러분 모두가 알고리즘을 공부해서 재밌다고 느끼며 행복한 결과를 얻을 수 있었으면 합니다.

 

gravekper-algo.tistory.com/2알고리즘 문제 풀이: 자주 묻는 질문들 Top 10

 

 

알고리즘 문제 풀이: 자주 묻는 질문들 Top 10

문제풀이 

by Gravekper 2020. 11. 8. 07:39

본문

좋아요 -

댓글달기 1

 

 

 

알고리즘 공부에 대해 자주 받는 질문들을 정리해 보았습니다.

공부를 시작하기 전에 프로그래밍 언어를 얼마나 잘 다뤄야 하나요?

정확한 기준은 없지만, 이런 것들을 할 수 있으면 특별히 더 필요한 건 없습니다.

• 정수나 문자열 입력받아 처리하기
• 조건문과 반복문
• 함수 정의해 사용하기
• 라이브러리 함수 사용하기

언어의 기능들을 이것들만 사용하는 건 아니지만, 이것들 이외에는 앞으로 필요할 때 공부해도 충분합니다.

각 기능들을 연습할 때에는 백준 온라인 저지의 단계별로 풀어보기(https://www.acmicpc.net/step)를 추천합니다.

뭘 보고 공부하면 좋을까요?

처음 공부를 시작한다면 백준 온라인 저지의 '단계별로 풀어보기'에 있는 주제들을 순서대로 공부하는 것이 좋습니다. 이 때 잘 모르는 주제는 웹에서 검색하거나 문제를 해결한 다른 사람들이 작성한 글을 보면 도움이 됩니다.

관련 서적은 '알고리즘 문제 해결 전략'을 추천합니다. 그 외에도 좋은 책이 많이 나왔지만 아직 제가 다 읽지 못해 늘 보던 책만 추천하는 부분은 양해 바랍니다.

저도 이 질문의 답이 될만한 튜토리얼 문서들을 천천히 준비하고 있습니다. 내용이 충분히 갖춰지면 이 항목 밑에 링크가 들어갈 겁니다.

좋은 문제는 어떻게 찾나요?

특정 난이도나 분류에 해당하는 문제를 풀고 싶다면 백준 온라인 저지나 Codeforces에서 난이도나 분류로 검색하세요. 백준 온라인 저지의 난이도와 문제 카테고리 기능은 solved.ac에서 제공합니다.

특정 대회의 기출문제를 찾는다면 백준 온라인 저지의 대회 카테고리에서 찾아보세요. 개인 연습용으로는 올림피아드, 팀 연습용으로는 ICPC 세트를 많이 이용합니다. Codeforces의 Virtual Contest 기능을 사용하는 것도 좋습니다.

문제를 선택할 때는 이미 많은 사람들이 해결한 문제를 골라서 푸는 것이 좋습니다. 해결한 사람이 많으면 문제 지문과 데이터에 문제가 없고 난이도에 많은 사람들의 의견이 반영되어 있으리라 기대할 수 있습니다. 그리고 그런 문제들은 인터넷 검색을 통해 다른 사람들의 해법을 찾기도 쉽습니다.

얼마나 고민한 후에 해답을 보는 게 좋을까요?

오래 공부한 사람들 사이에서도 의견이 많이 갈리는 주제입니다. 공부하는 목적에 따라서도 많이 다릅니다.

일반적으로 문제를 읽자마자 해답을 찾거나 풀리지 않는 문제를 너무 오래 고민하는 건 좋지 않습니다. 특히 너무 오랫동안 풀리지 않는 문제에 대해 고민하는 것보다 새로운 문제들을 여러 개 접하는 것이 실력 향상에 큰 도움이 됩니다. 개인의 취향에 따라 30분에서 두 시간정도 시간을 정해두고 그만큼 생각해도 풀이가 떠오르지 않는다면 해답을 찾는 것을 권장합니다.

코딩 테스트를 준비하는 것과 대회를 준비하는 것은 어떻게 다른가요?

코딩 테스트에는 일반적으로 기반 지식이 많이 필요하지 않은 문제들이 출제됩니다. 기반 지식으로는 보통 기초적인 조합론, 자료 구조, 그래프 이론이 필요합니다. 고난이도 문제도 노린다면 최단 경로 알고리즘이나 DP를 연습하는 것도 좋습니다.

경시대회에는 프로그래밍을 통해 풀 수 있는 건 거의 뭐든지 출제됩니다. 복잡한 자료구조와 알고리즘을 많이 알수록 도움이 됩니다. 처음 공부하는 분들 관점에서 보면 절대 시간 내에 결과가 나오지 않을 것같은 문제들을 해결하는 방법들을 공부하게 됩니다.

코딩 테스트를 준비하는 데에 얼마나 걸리나요?

평소에 얼마나 코드를 작성하거나 수학 공부를 했는지에 따라 많이 다릅니다.

저는 대학교 3학년 전공과목 2~3개 정도 좋은 성적을 받을 정도 시간을 투자하면 충분히 좋은 점수를 받을 정도로 준비할 수 있다고 생각합니다.

코드포스가 뭐죠? 꼭 해야 하나요?

코드포스는 알고리즘 대회가 자주 열리는 사이트입니다. 주로 한국 시간으로 자정 전후에 대회가 열리고 제한 시간동안 푼 문제 수에 따라 참가자의 레이팅이 매겨집니다.

저는 코드포스 대회가 끝난 뒤에 문제에 대해 설명하는 방송을 진행합니다. 제 유튜브 채널에는 지난 코드포스 대회 풀이 영상이 올라옵니다.

코드포스는 프로그래밍 대회에 관심이 있고 경쟁을 좋아하는 분들에게 추천합니다. 코드포스에 최근에 출제된 문제는 최근에 많은 사람이 접근한 문제이기 때문에 공부 과정에서 커뮤니티에 문제에 대해 질문하기 좋습니다.

코딩 테스트에 주로 나오는 유형과는 많이 다르기 때문에 코딩 테스트를 목적으로 공부하는 분들은 경쟁에 관심이 있는 분들에게만 권합니다. 알고리즘 대회를 준비하는 분들도 준비하는 대회 유형에 따라 필요한 능력이 다르기 때문에 반드시 코드포스에서 공부해야 하는 것은 아닙니다.

지금 공부 시작해서 코드포스 xxxx점 찍으려면 얼마나 걸리나요?

얼마나 공부를 많이 하는지, 지금까지 무엇을 공부했는지에 따라 다릅니다.

블루까지는 어려운 문제를 푸는 것보다 간단한 문제를 빨리 파악하고 푸는 것이 중요합니다. 레이팅을 올리는 게 목적이라면 이전 대회 기출문제의 A, B번 문제들을 연습하면 많이 도움이 됩니다.

퍼플 이상을 노린다면 길게 시간을 두고 여러 분야의 문제들을 꾸준히 푸는 것이 좋습니다.

알고리즘만 공부하면 취직할 수 있나요? / 큰 대회에서 입상하거나 코드포스 xxxx점이면 회사에서 연락 오나요?

보통 그렇지 않습니다.

알고리즘을 공부해 코딩 테스트를 통과할 수 있을 정도의 실력이 되면 분명히 그만큼 취업에 유리합니다. 하지만 채용 과정에는 코딩 테스트만 있는 것이 아닙니다. 다른 과정들도 통과할 수 있도록 준비해야 합니다.

알고리즘 대회에서 좋은 성과를 거둔 분들을 많이 채용하는 기업들도 있습니다. 하지만 특기로 삼을 정도로 알고리즘을 공부하려면 그만큼 큰 성과를 내야 하고 오랜 시간이 걸립니다. 적어도 다른 방법으로 취업을 준비하는 것보다 훨씬 많은 시간이 필요합니다.

회사에서 개인에게 오는 연락은 저는 꽤 오래 전에 두 번 받아봤습니다. 그리고 아쉽게도 저는 취직해 본 적이 없습니다.

알고리즘 공부를 하면 실무에 얼마나 도움이 되나요?

만약 프로그래밍에 익숙하지 않고 수학적 모델을(조합론이나 정수론 기초) 구현하는 것이 익숙치 않다면, 알고리즘 공부가 프로그래밍에 익숙해지는 데에 많이 도움이 됩니다.

이미 숙련된 프로그래머라면 알고리즘 공부가 다른 일에 큰 도움이 되지는 않습니다. 여기서 말하는 '다른 일'이 알고리즘 강의나 문제 출제같은 일이 아니라면 말입니다.

폰 노이만과 투어리스트가 싸우면 누가 이기나요?

제가 어제 꿈에서 둘 다 이기고 왔습니다.

함께 보면 좋은 자료

• 알고리즘 문제 해결: 프로그래밍 언어 추천
• 류원하(Being) - 현업 엔지니어의 시각에서 본 알고리즘 공부의 장점과 단점