๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

Algoritm/Coding Interview5

[3.์Šคํƒ/ํ] stack, queue 1. Stack : ๋‹จ์–ด์˜ ์˜๋ฏธ์ฒ˜๋Ÿผ ๋ฐ์ดํ„ฐ๋ฅผ ์Œ“์•„ ์˜ฌ๋ฆฐ๋‹ค๋Š” ์˜๋ฏธ : ๋ฐฐ์—ด ๋Œ€์‹ ์— ์‚ฌ์šฉ๋˜๋Š” ๊ฒฝ์šฐ๊ฐ€ ์žˆ์Œ : LIFO(Last In First Out) > ๋งˆ์น˜ ์ ‘์‹œ๋ฅผ ์Œ“์•„๋‘์—ˆ๋‹ค๊ฐ€ ๋งจ ์œ„๋ถ€ํ„ฐ ์‚ฌ์šฉํ•˜๋Š” ๊ฒƒ์ฒ˜๋Ÿผ, ๊ฐ€์žฅ ์ตœ๊ทผ์— ์ถ”๊ฐ€ํ•œ ํ•ญ๋ชฉ์ด ๊ฐ€์žฅ ๋จผ์ € ์ œ๊ฑฐ๋  ํ•ญ๋ชฉ์ด๋ผ๋Š” ๊ฒƒ. : ๋ฏธ๋กœ ์ฐพ๊ธฐ, ๊ด„ํ˜ธ ์œ ํšจ์„ฑ ์ฒดํฌ, ์žฌ๊ท€ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋“ฑ์— ํ™œ์šฉ : ์ง์ ‘ new์—ฐ์‚ฐ์ž๋กœ ๊ฐ์ฒด๋ฅผ ์ƒ์„ฑํ•˜์—ฌ ์‚ฌ์šฉ๊ฐ€๋Šฅ 2. Stack์˜ ์—ฐ์‚ฐ stack.pop() ๊ฐ€์žฅ ์ตœ๊ทผ ์›์†Œ ๋ฐ˜ํ™˜ ํ›„ ์ œ๊ฑฐ stack.peek() ๊ฐ€์žฅ ์ตœ๊ทผ ์›์†Œ ํ˜ธ์ถœ (์ œ๊ฑฐX) stack.push(e) ์š”์†Œ ์‚ฝ์ž… stack.isEmpty() ์Šคํƒ์ด ๋น„์–ด์žˆ๋Š” ๊ฒฝ์šฐ true๋ฐ˜ํ™˜, ์š”์†Œ๊ฐ€ ์žˆ๋Š” ๊ฒฝ์šฐ false๋ฐ˜ํ™˜ stack.search() ๊ฐ์ฒด๊ฐ€ ์กด์žฌํ•˜๋Š” ์ธ๋ฑ์Šค ๋ฐ˜ํ™˜(๋งˆ์ง€๋ง‰ ์š”์†Œ๋กœ๋ถ€ํ„ฐ .. 2020. 8. 31.
[2.์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ] ์ค‘๋ณต์—†์• ๊ธฐ, ๋’ค์—์„œ k๋ฒˆ์งธ ์›์†Œ๊ตฌํ•˜๊ธฐ, ์ค‘๊ฐ„๋…ธ๋“œ์‚ญ์ œ, ๋ถ„ํ• , ๋ฆฌ์ŠคํŠธ์˜ํ•ฉ, ํšŒ๋ฌธ(์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ), ๊ต์ง‘ํ•ฉ, ๋ฃจํ”„๋ฐœ๊ฒฌ [ Q1. ์ค‘๋ณต์—†์• ๊ธฐ ] ์ •๋ ฌ๋˜์–ด์žˆ์ง€ ์•Š์€ ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ๊ฐ€ ์ฃผ์–ด์กŒ์„๋•Œ ์ด ๋ฆฌ์ŠคํŠธ์—์„œ ์ค‘๋ณต๋˜๋Š” ์›์†Œ๋ฅผ ์ œ๊ฑฐํ•˜๋Š” ์ฝ”๋“œ๋ฅผ ์ž‘์„ฑํ•˜๋ผ. (์ž„์‹œ๋ฒ„ํผ๊ฐ€ ์—†๋‹ค๋ฉด ์–ด๋–ป๊ฒŒ ํ’€๊นŒ?) - ๋‚ด ํ’€์ด - 1. ํ•ด์‹œ๋งต ํ™œ์šฉ(์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ ์ €์žฅ์šฉ๋„) 2. ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ๋ฅผ ์ˆœํšŒํ•˜๋ฉฐ n์ด ํ‚ค๋กœ ์กด์žฌํ•˜๋Š”์ง€ ์ฒดํฌ => ์กด์žฌํ•˜์ง€ ์•Š๋Š” ๊ฒฝ์šฐ ๋งต์— ๋ฅผ ์‚ฝ์ž… => ์กด์žฌํ•˜๋Š” ๊ฒฝ์šฐ n.prev.next=n.next๋กœ ๋ณ€๊ฒฝ (์ด๊ฒŒ ๋…ธ๋“œ ์‚ญ์ œ) * ์•ผ ๋‚ด ๋ฌธ์ œ๋Š” ๋…ธ๋“œํด๋ž˜์Šค ๊ตฌํ˜„ํ•˜๋Š”๊ฑฐ๊ฐ€ ๋ฌธ์ œ์•ผ.. class LinkedNode{ int data; LinkedNode prev, next; public LinkedNode() { // TODO Auto-generated constructor stub } public LinkedNode(int d) { data=d; } .. 2020. 8. 30.
[2.์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ] LinkedList, ์žฌ๊ท€, LinkedListNode 1. ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ๋ž€ ? : ์ฐจ๋ก€๋Œ€๋กœ ์—ฐ๊ฒฐ๋œ ๋…ธ๋“œ๋ฅผ ํ‘œํ˜„ํ•ด์ฃผ๋Š” ์ž๋ฃŒ๊ตฌ์กฐ 1) ๋‹จ๋ฐฉํ–ฅ ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ : ๋…ธ๋“œ๋Š” ๋‹ค์Œ ๋…ธ๋“œ๋ฅผ ๊ฐ€๋ฅดํ‚จ๋‹ค. 2) ์–‘๋ฐฉํ–ฅ ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ : ๋…ธ๋“œ๋Š” ๋‹ค์Œ ๋…ธ๋“œ์™€ ์ด์ „ ๋…ธ๋“œ๋ฅผ ๊ฐ€๋ฅดํ‚จ๋‹ค. : ํŠน์ • ์ธ๋ฑ์Šค ์ ‘๊ทผ์‹œ ์ƒ์ˆ˜์‹œ๊ฐ„์— ์ ‘๊ทผ ๋ถˆ๊ฐ€ (์ฒ˜์Œ๋ถ€ํ„ฐ ~K๋ฒˆ๊นŒ์ง€ ๋ฃจํ”„๋ฅผ ๋Œ๋ ค์•ผํ•˜๊ธฐ ๋•Œ๋ฌธ) : ๋”ฐ๋ผ์„œ ์‹œ์ž‘์ง€์ ์—์„œ ์•„์ดํ…œ ์ถ”๊ฐ€/์‚ญ์ œ๋ฅผ ์ƒ์ˆ˜์‹œ๊ฐ„์— ํ•  ์ˆ˜ ์žˆ๋Š” ํŠน์ • ์–ดํ”Œ๋ฆฌ์ผ€์ด์…˜์—์„œ ์œ ์šฉํ•˜๊ฒŒ ์‚ฌ์šฉ๋จ 2. ๋‹จ๋ฐฉํ–ฅ ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ ๋งŒ๋“ค๊ธฐ : LinkedList์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ์‚ฌ์šฉํ•˜์ง€ ์•Š๊ณ  ๊ตฌํ˜„ > head์˜ ๋…ธ๋“œ์ฃผ์†Œ๋ฅผ ์ฐธ์กฐํ•˜๋Š” ๋ฐฉ๋ฒ• ์‚ฌ์šฉ : ์ฆ‰, ๋…ธ๋“œ์† ํ•„๋“œ๋กœ ๋…ธ๋“œ๋ฅผ ์—ฐ๊ฒฐ class Node{ Node next=null; int data; public Node(int d) { data=d; } void appendToTail(in.. 2020. 8. 25.
[1. ๋ฐฐ์—ด/๋ฌธ์ž์—ด] ์ค‘๋ณตํ™•์ธ, ์ˆœ์—ดํ™•์ธ, URLify(๋Œ€์ฒด), ํšŒ๋ฌธ์ˆœ์—ด, ํ•˜๋‚˜๋นผ๊ธฐ, ๋ฌธ์ž์—ด์••์ถ•, ํ–‰๋ ฌํšŒ์ „, 0ํ–‰๋ ฌ, ๋ฌธ์ž์—ดํšŒ์ „ [ Q1. ์ค‘๋ณต์ด ์—†๋Š”๊ฐ€ ] ๋ฌธ์ž์—ด์ด ์ฃผ์–ด์ง„ ๊ฒฝ์šฐ, ์ด ๋ฌธ์ž์—ด์— ๊ฐ™์€ ๋ฌธ์ž๊ฐ€ ์ค‘๋ณต๋˜์–ด ๋“ฑ์žฅํ•˜๋Š”์ง€ ํ™•์ธํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ž‘์„ฑํ•˜๋ผ. ์ถ”๊ฐ€์ ์œผ๋กœ ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ์‚ฌ์šฉํ•˜์ง€์•Š๊ณ  ํ’€ ์ˆ˜ ์žˆ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์—ญ์‹œ ์ž‘์„ฑํ•˜๋ผ. - ๋‚ด ํ’€์ด - 1. ๋ฌธ์ž์—ด์„ char๋ฐฐ์—ด์— ๋„ฃ๊ธฐ 2. ๊ฐ๋ฐฐ์—ด์˜ ์š”์†Œ๋ฅผ ๋ฐ˜๋ณต์ฒ˜๋ฆฌ > hashmap์— ์žˆ๋‹ค๋ฉด ์ค‘๋ณต์žˆ์Œ ์ข…๋ฃŒ, ์—†๋‹ค๋ฉด hashmap์— ์š”์†Œ๋กœ ์ถ”๊ฐ€ boolean charDup(String s) { char[] char_set=s.toCharArray(); HashMap map=new HashMap(); for(char c:char_set) { if(map.containsKey(c)) { return true; } else { map.put(c, 0); } } return false; } ๋”๋ณด๊ธฐ *.. 2020. 8. 25.