Skip to content

Files

Latest commit

4306562 ยท Aug 10, 2020

History

History
This branch is 295 commits behind gyoogle/tech-interview-for-developer:master.

Algorithm

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
Nov 16, 2019
Nov 15, 2019
Feb 5, 2020
Aug 3, 2019
Jun 9, 2019
Aug 25, 2019
Aug 7, 2019
Jun 9, 2019
Oct 16, 2019
Oct 7, 2019
Aug 10, 2020
Sep 4, 2019
Sep 4, 2019
Jul 31, 2019
Mar 1, 2020
Feb 27, 2020
Aug 1, 2019

์•Œ๊ณ ๋ฆฌ์ฆ˜(์ฝ”๋”ฉํ…Œ์ŠคํŠธ) ๋ฌธ์ œ ์ ‘๊ทผ๋ฒ•


Data Structure

  1. ๋ฐฐ์—ด : ์ž„์˜์˜ ์‚ฌ์ด์ฆˆ๋ฅผ ์„ ์–ธ (Heap, Queue, Binary Tree, Hashing ์‚ฌ์šฉ)
  2. ์Šคํƒ : ํ–‰ ํŠน์ •์กฐ๊ฑด์— ๋”ฐ๋ผ push, pop ์ ์šฉ
  3. ํ : BFS๋ฅผ ํ†ตํ•ด ์ˆœ์„œ๋Œ€๋กœ ์ ‘๊ทผํ•  ๋•Œ ์ ์šฉ
  4. ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ : ๋ฐฐ์—ด ๊ตฌํ˜„, ํฌ์ธํ„ฐ ๊ตฌํ˜„ 2๊ฐ€์ง€ ๋ฐฉ๋ฒ• - ์‚ฝ์ž…,์‚ญ์ œ๊ฐ€ ๋งŽ์ด ์ผ์–ด๋‚  ๋•Œ ํ™œ์šฉํ•˜๊ธฐ
  5. ๊ทธ๋ž˜ํ”„ : ๊ฒฝ์šฐ์˜ ์ˆ˜, ์—ฐ๊ฒฐ ๊ด€๊ณ„๊ฐ€ ์žˆ์„ ๋•Œ ์ ์šฉ
  6. ํ•ด์‹ฑ : ๋ฐ์ดํ„ฐ ์ˆ˜๋งŒํผ ๋ฉ”๋ชจ๋ฆฌ์— ์ƒ์„ฑํ•  ์ˆ˜ ์—†๋Š” ์ƒํ™ฉ์— ์ ์šฉ
  7. ํŠธ๋ฆฌ : Heap๊ณผ BST(์ด์ง„ํƒ์ƒ‰)

Algorithm

  1. โ˜…์žฌ๊ท€(Recursion) : ๊ฐ€์žฅ ๋งŽ์ด ํ™œ์šฉ. ์ค‘์š”ํ•œ ๊ฑด ํ˜ธ์ถœ ํšŸ์ˆ˜๋ฅผ ์ค„์—ฌ์•ผ ํ•จ (๋ฐ˜๋ณต ์กฐ๊ฑด, ์ข…๋ฃŒ ์กฐ๊ฑด ์ฒดํฌ)
  2. โ˜…BFS, DFS : 2์ฐจ์› ๋ฐฐ์—ด์—์„œ ํ™•์žฅ ์‹œ, ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ํƒ์ƒ‰ํ•  ๋•Œ ๊ตฌ์กฐ์ฒด(class)์™€ visited ์ฒดํฌ๋ฅผ ์‚ฌ์šฉํ•จ
  3. โ˜…์ •๋ ฌ : ํ€ต์†ŒํŠธ๋‚˜ ๋จธ์ง€์†ŒํŠธ๊ฐ€ ๋Œ€ํ‘œ์ ์ด์ง€๋งŒ, ๋ณดํ†ต ํ€ต์†ŒํŠธ๋ฅผ ์‚ฌ์šฉํ•จ
  4. โ˜…๋ฉ”๋ชจ์ด์ œ์ด์…˜(memoization) : ์ด์ „ ๊ฒฐ๊ณผ๊ฐ€ ๋˜ ์‚ฌ์šฉ๋  ๋•Œ, ๋ฐ˜๋ณต ์ž‘์—…์„ ์•ˆํ•˜๋„๋ก ์ €์žฅ
  5. โ˜…์ด๋ถ„ํƒ์ƒ‰(Binary Search) : logN์œผ๋กœ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ์ค„์ผ ์ˆ˜ ์žˆ๋Š” ๊ฐ„๋‹จํ•˜๋ฉด์„œ ํ•ต์‹ฌ์ ์ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜
  6. ์ตœ์†Œ์‹ ์žฅํŠธ๋ฆฌ(MST) : ์‚ฌ์ดํด์ด ํฌํ•จ๋˜์ง€ ์•Š๊ณ  ๋ชจ๋“  ์ •์ ์ด ์—ฐ๊ฒฐ๋œ ํŠธ๋ฆฌ์— ์‚ฌ์šฉ (ํฌ๋ฃจ์Šค์นผ, ํ”„๋ฆผ)
  7. ์ตœ์†Œ๊ณตํ†ต์กฐ์ƒ(LCA) : ๊ฒฝ์šฐ์˜ ์ˆ˜์—์„œ ์กฐ๊ฑด์ด ๊ฒน์น˜๋Š” ๊ฒฝ์šฐ. ์ตœ๋‹จ ๊ฒฝ๋กœ ํƒ์ƒ‰์‹œ ๊ณตํ†ต์ธ ๊ฒฝ์šฐ๊ฐ€ ๋งŽ์„ ๋•Œ ์ ์šฉ
  8. Disjoint-Set : ์„œ๋กœ์†Œ ์ง‘ํ•ฉ. ์ธ์ ‘ํ•œ ์ง‘ํ•จ์˜ ๋ชจ์ž„์œผ๋กœ Tree์˜ ์ผ์ข…์ด๋ฉฐ ์‹œ๊ฐ„๋ณต์žก๋„๊ฐ€ ๋‚ฎ์Œ
  9. ๋ถ„ํ•  ์ •๋ณต : ๋จธ์ง€ ์†ŒํŠธ์— ์‚ฌ์šฉ๋˜๋ฉฐ ๋ฒ”์œ„๋ฅผ ๋‚˜๋ˆ„์–ด ํ™•์ธํ•  ๋•Œ ์‚ฌ์šฉ
  10. ํŠธ๋ผ์ด(Trie) : ๋ชจ๋“  String์„ ์ €์žฅํ•ด๋‚˜๊ฐ€๋ฉฐ ๋น„๊ตํ•˜๋Š” ๋ฐฉ๋ฒ•
  11. ๋น„ํŠธ๋งˆ์Šคํ‚น : |๋Š” OR, &๋Š” AND, ^๋Š” XOR <<๋ฅผ ํ†ตํ•ด ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์ ˆ์•ฝํ•  ์ˆ˜ ์žˆ์Œ

  • Sort ์‹œ๊ฐ„๋ณต์žก๋„