• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

문제들 출처가 궁금합니다

20.03.26 08:37 작성 조회수 113

1

혹시 문제들 출처가 어딘지좀 가르쳐 주실 수 있나요 !?!

답변 1

답변을 작성해보세요.

4

안녕하세요~

질문을 주셔서 감사드립니다.

리코드, 해커랭크, interviewBit, geeks등 다양한 문제가 시중에 있습니다.

이중에 핵심적인거, 가장 많이 알려진거 꼭 알아야 할 개념문제를 모아서 풀어봤습니다.

개념적인거를 알아야 그 비슷한걸 풀수 있기때문이죠

결론적으로, 시중문제+카카오 블라인드 출제문제 유형이라고 보시면됩니다. 아래 간략히 설명드리겠습니다

=========아래====

1. String, Array, Map, Set 을 이용하는 문제는

subString,String 함수응용, Array와 char[]을 이용해서 알파벳저장, Array를  for로돌리다가 Map에 키로 등록(TwoSum같은 문제응용)

Map두개를 써서 key, Value를 크로스로 저장해서 결과를 얻거나

Map을 이용해서 Set에 중복되지 않는거 저장하거나

특히 2018 카카오는 MergeInterval 류의 문제가 많이 나오더라구요

Comparator를 이용한게 3개나 나왔습니다. PriorityQueue는 단골로 나오죠

2. 큐스택: Queue는 levelOrder(너무 유명한문제)를 이해해야합니다. 스택은 딱 보고 이거 스택이다 감이 와야겠죠

(BaseballGame, 계산기문제)

3. 그래프(dfs, bfs):  당락의핵심이죠

가장 많이 알려진게 numberOf island는  dfs, bfs로 다양하게 풀어야합니다. 양쪽다 접근가능해야하고요

코딩테스트를 총 3개문제를 낸다면 한개는 저걸로 응용하는 경우를 많이 봤습니다.

island 모양이 distinct 하게 똑같은게 몇개인가 문제, island에 최대 큰면적, 또는 최소 면적등 너무 다양하게 응용함 

그래프는 문제는 꼭 나옵니다. 배점도 크고 dfs를 이용하여 stack에 넣으면서 풀줄도 알아야 하고,

bfs처럼 큐에 하나씩 넣어서 빼먹으면서 접근 할 줄도 알아야 하고, 거의 완벽하게 알면 이것만 건져도 승

산이 있죠

dfs, bfs는 공식이 있습니다. 제강의를 보시면 공식을 만들어 놨습니다. 대입해서 문제 접근하시면 보다 쉽게 이해될수 가 있죠...

출제자가 무궁무궁진하게 낼수가 있기에 ...제일 많이 이용하는게 그래프입니다.

시험볼때 3시간이 너무 금방가서 , 30분처럼 느껴지는데 단 1분이라도 아껴야 되겠죠...

4. 동적프로그래밍(Dynamic Programming): 대표적인게 coinChange를 정확히 이해하셔야죠

다이나믹 프로그램밍은 for문을 2번 돌려서 해를 찾는게 아니라,  정해진 값을 이용해서 topDown, bottomUp방식으로 이미 정해진 길을 찾아내는게 핵심입니다. 가끔 출제되서 사람을 돌게하는 문제가 있지만, dp 냄새가 날경우이거 dp 아닌가 하고 접근하면 됩니다. 물론 시간은 걸리겠지만..

5. 백트랙킹

저는 개인적으로 백트랙킹, 재귀가 힘들었습니다. GenerateParentheses문제는  제 강의 보시면 무식하게 호출하는거 다 적어서 백트랙킹 뭔지 , recursive가 어떤 동작하는지 아실겁니다.

6. 기타(최단경로, 다익스트라...등은 여기서 다루지 않았습니다.)

감사합니다.

해피코딩하시기 바랍니다.