[์•Œ๊ณ ๋ฆฌ์ฆ˜] DFS์™€ BFS JAVA
ยท
์•Œ๊ณ ๋ฆฌ์ฆ˜
๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰ DFS (Depth-First Search)    ์‹œ์ž‘ ๋…ธ๋“œ ์„ ํƒ: ํƒ์ƒ‰์„ ์‹œ์ž‘ํ•  ๋…ธ๋“œ๋ฅผ ์„ ํƒํ•ฉ๋‹ˆ๋‹ค.๋…ธ๋“œ ๋ฐฉ๋ฌธ: ํ˜„์žฌ ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธํ•˜๊ณ , ๋ฐฉ๋ฌธํ–ˆ๋‹ค๊ณ  ํ‘œ์‹œํ•ฉ๋‹ˆ๋‹ค.์ธ์ ‘ ๋…ธ๋“œ ํƒ์ƒ‰: ํ˜„์žฌ ๋…ธ๋“œ์— ์ธ์ ‘ํ•œ ๋…ธ๋“œ๋“ค ์ค‘ ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ๋…ธ๋“œ๋กœ ์ด๋™ํ•ฉ๋‹ˆ๋‹ค.๋ฐ˜๋ณต: ๋” ์ด์ƒ ๋ฐฉ๋ฌธํ•  ๋…ธ๋“œ๊ฐ€ ์—†์„ ๋•Œ๊นŒ์ง€ ์ธ์ ‘ ๋…ธ๋“œ๋กœ ์ด๋™ํ•˜๋Š” ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•ฉ๋‹ˆ๋‹ค. ๋ชจ๋“  ์ธ์ ‘ ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธํ–ˆ๋‹ค๋ฉด, ์ด์ „ ๋…ธ๋“œ๋กœ ๋Œ์•„๊ฐ€์„œ ๋‹ค์Œ ์ธ์ ‘ ๋…ธ๋“œ๋ฅผ ํƒ์ƒ‰ํ•ฉ๋‹ˆ๋‹ค. DFS์˜ ํ™œ์šฉ๋ฏธ๋กœ ์ฐพ๊ธฐ: DFS๋Š” ๋ฏธ๋กœ ์ฐพ๊ธฐ์™€ ๊ฐ™์€ ๊ฒฝ๋กœ ํƒ์ƒ‰ ๋ฌธ์ œ์— ์œ ์šฉํ•ฉ๋‹ˆ๋‹ค.์‚ฌ์ดํด ํƒ์ง€: ๊ทธ๋ž˜ํ”„์—์„œ ์‚ฌ์ดํด์ด ์กด์žฌํ•˜๋Š”์ง€ ํ™•์ธํ•  ๋•Œ ์‚ฌ์šฉ๋ฉ๋‹ˆ๋‹ค.๊ฐ•๊ฒฐํ•ฉ ์š”์†Œ ์ฐพ๊ธฐ: DFS๋Š” ๊ทธ๋ž˜ํ”„์—์„œ ๊ฐ•๊ฒฐํ•ฉ ์š”์†Œ๋ฅผ ์ฐพ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ๊ธฐ๋ณธ์ด ๋ฉ๋‹ˆ๋‹ค.์œ„์ƒ ์ •๋ ฌ: ์œ ํ–ฅ ๋น„์ˆœํ™˜ ๊ทธ๋ž˜ํ”„(DAG)์—์„œ ์œ„์ƒ ์ •๋ ฌ์„ ์ˆ˜ํ–‰..
์ด์ง„ํƒ์ƒ‰(Binary Search) ๊ฐœ๋…์ •๋ฆฌ
ยท
์•Œ๊ณ ๋ฆฌ์ฆ˜
์ด์ง„ํƒ์ƒ‰(Binary Search)์ •๋ ฌ๋œ ๋ฐฐ์—ด ๋˜๋Š” ๋ฆฌ์ŠคํŠธ์—์„œ ์›ํ•˜๋Š” ๊ฐ’์„ ๋น ๋ฅด๊ฒŒ ์ฐพ์•„๋‚ด๋Š” ํƒ์ƒ‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ˆœ์„œํƒ์ƒ‰ ๋Œ€์ƒ์˜ ์ค‘๊ฐ„ ์ธ๋ฑ์Šค๋ฅผ ์ฐพ์Šต๋‹ˆ๋‹ค.์ค‘๊ฐ„ ๊ฐ’๊ณผ ์ฐพ๊ณ ์ž ํ•˜๋Š” ๊ฐ’์„ ๋น„๊ตํ•ฉ๋‹ˆ๋‹ค.๋งŒ์•ฝ ์ค‘๊ฐ„ ๊ฐ’์ด ์ฐพ๊ณ ์ž ํ•˜๋Š” ๊ฐ’๊ณผ ์ผ์น˜ํ•˜๋ฉด ํƒ์ƒ‰์„ ์ข…๋ฃŒํ•ฉ๋‹ˆ๋‹ค.๋งŒ์•ฝ ์ฐพ๊ณ ์ž ํ•˜๋Š” ๊ฐ’์ด ์ค‘๊ฐ„ ๊ฐ’๋ณด๋‹ค ์ž‘๋‹ค๋ฉด, ์™ผ์ชฝ ๋ถ€๋ถ„์„ ํƒ์ƒ‰ํ•ฉ๋‹ˆ๋‹ค.๋งŒ์•ฝ ์ฐพ๊ณ ์ž ํ•˜๋Š” ๊ฐ’์ด ์ค‘๊ฐ„ ๊ฐ’๋ณด๋‹ค ํฌ๋‹ค๋ฉด, ์˜ค๋ฅธ์ชฝ ๋ถ€๋ถ„์„ ํƒ์ƒ‰ํ•ฉ๋‹ˆ๋‹ค.์ด ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•˜์—ฌ ์›ํ•˜๋Š” ๊ฐ’์„ ์ฐพ์„ ๋•Œ๊นŒ์ง€ ๊ณ„์†ํ•ฉ๋‹ˆ๋‹ค. ์ด์ง„ ํƒ์ƒ‰๊ณผ ์„ ํ˜• ํƒ์ƒ‰์˜ ์ฐจ์ด์  ์„ ํ˜• ํƒ์ƒ‰(Linear Search)๋ฐฐ์—ด ๋˜๋Š” ๋ฆฌ์ŠคํŠธ๋ฅผ ์ฒ˜์Œ๋ถ€ํ„ฐ ๋๊นŒ์ง€ ์ˆœ์ฐจ์ ์œผ๋กœ ํƒ์ƒ‰ํ•˜์—ฌ ์›ํ•˜๋Š” ๊ฐ’์„ ์ฐพ์Šต๋‹ˆ๋‹ค. ๋ฐฐ์—ด ๋˜๋Š” ๋ฆฌ์ŠคํŠธ๊ฐ€ ์ •๋ ฌ๋˜์–ด ์žˆ์ง€ ์•Š์•„๋„ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.์ด์ง„ ํƒ์ƒ‰(Binary Search)์ •๋ ฌ๋œ ๋ฐฐ์—ด ๋˜๋Š” ๋ฆฌ์ŠคํŠธ๋ฅผ ๋ฐ˜..
Queue ๊ฐœ๋…์ •๋ฆฌ
ยท
์•Œ๊ณ ๋ฆฌ์ฆ˜
Queue ์„ ์ž…์„ ์ถœ(FIFO, First-In-First-Out) ๋ฐฉ์‹Queue๋Š” ํŠน์ดํ•˜๊ฒŒ contains() ํ•จ์ˆ˜๋ฅผ ํ†ตํ•ด ์–ด๋– ํ•œ ๊ฐ’์ด ํฌํ•จ๋˜์–ด์žˆ๋Š”์ง€๋Š” ํ™•์ธํ•  ์ˆ˜ ์žˆ์ง€๋งŒIndex์˜ ๊ฐœ๋…์ด ์—†์–ด์„œ ์–ด๋– ํ•œ ๊ฐ’์ด ๋ช‡๋ฒˆ์งธ์— ์žˆ๋Š”์ง€๋Š” ์•Œ ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค.  ์„ ์–ธ๋ฐฉ๋ฒ•Queue que = new LinkedList();Queue ๋ณ€์ˆ˜๋ช… = new LinkedList();Queue์™€ LinkedList ์œ ํ‹ธ์„ ๋ชจ๋‘ importํ•ด์ค˜์•ผ ์ •์ƒ์ ์œผ๋กœ ์‚ฌ์šฉ ๊ฐ€๋Šฅ   enqueue (offer): ํ์˜ ๋์— ์š”์†Œ๋ฅผ ์ถ”๊ฐ€ํ•ฉ๋‹ˆ๋‹ค.dequeue (poll): ํ์˜ ์•ž์—์„œ ์š”์†Œ๋ฅผ ์ œ๊ฑฐํ•˜๊ณ  ๋ฐ˜ํ™˜ํ•ฉ๋‹ˆ๋‹ค.peek: ํ์˜ ์•ž์— ์žˆ๋Š” ์š”์†Œ๋ฅผ ์ œ๊ฑฐํ•˜์ง€ ์•Š๊ณ  ๋ฐ˜ํ™˜ํ•ฉ๋‹ˆ๋‹ค.isEmpty: ํ๊ฐ€ ๋น„์–ด ์žˆ๋Š”์ง€ ํ™•์ธํ•ฉ๋‹ˆ๋‹ค.size: ํ์˜ ์š”์†Œ ๊ฐœ์ˆ˜๋ฅผ ๋ฐ˜ํ™˜ํ•ฉ๋‹ˆ๋‹ค..
Stack ๊ฐœ๋… ์ •๋ฆฌ
ยท
์•Œ๊ณ ๋ฆฌ์ฆ˜
Stack์žฅ์ ๊ฐ„๋‹จํ•œ ์‚ฌ์šฉ: ์š”์†Œ๋ฅผ ์ถ”๊ฐ€ํ•˜๊ณ  ์ œ๊ฑฐํ•˜๋Š” ๋ฉ”์„œ๋“œ๊ฐ€ ์ง๊ด€์ ์ž…๋‹ˆ๋‹ค.LIFO ๊ตฌ์กฐ: ํ›„์ž…์„ ์ถœ ๋ฐฉ์‹์œผ๋กœ ์ž‘์—…์„ ์ฒ˜๋ฆฌํ•  ๋•Œ ์œ ์šฉํ•ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ์žฌ๊ท€์  ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‚˜ ์—ญ์ˆœ ์ถœ๋ ฅ ๋“ฑ์— ์‚ฌ์šฉ๋ฉ๋‹ˆ๋‹ค.๋‹จ์ ๋™๊ธฐํ™” ๋ฌธ์ œ: Stack ํด๋ž˜์Šค๋Š” ๋™๊ธฐํ™”๋˜์–ด ์žˆ์–ด ๋ฉ€ํ‹ฐ์Šค๋ ˆ๋“œ ํ™˜๊ฒฝ์—์„œ ์•ˆ์ „ํ•˜์ง€๋งŒ, ๋™๊ธฐํ™” ๋•Œ๋ฌธ์— ์„ฑ๋Šฅ์ด ์ €ํ•˜๋  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.Legacy ํด๋ž˜์Šค: Stack ํด๋ž˜์Šค๋Š” Java์˜ ์ดˆ๊ธฐ ๋ฒ„์ „์—์„œ ๋„์ž…๋œ ํด๋ž˜์Šค์ž…๋‹ˆ๋‹ค. ์ดํ›„์— ๋” ๋‚˜์€ ๋Œ€์•ˆ์ด ์ œ๊ณต๋˜์—ˆ์Šต๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, Deque ์ธํ„ฐํŽ˜์ด์Šค๋ฅผ ๊ตฌํ˜„ํ•œ ArrayDeque ํด๋ž˜์Šค๋Š” ๋น„์Šทํ•œ ๊ธฐ๋Šฅ์„ ์ œ๊ณตํ•˜์ง€๋งŒ ๋” ์„ฑ๋Šฅ์ด ์ข‹์Šต๋‹ˆ๋‹ค.์ฃผ์š” ๋ฉ”์„œ๋“œ push(E item): ์Šคํƒ์˜ ๋งจ ์œ„์— ์š”์†Œ๋ฅผ ์ถ”๊ฐ€ํ•ฉ๋‹ˆ๋‹ค.pop(): ์Šคํƒ์˜ ๋งจ ์œ„์— ์žˆ๋Š” ์š”์†Œ๋ฅผ ์ œ๊ฑฐํ•˜๊ณ  ๋ฐ˜ํ™˜ํ•ฉ๋‹ˆ๋‹ค.peek():..
๋ฐฑ์ค€ 10988 ์ž๋ฐ” ํŒฐ๋ฆฐ๋“œ๋กฌ์ธ์ง€ ํ™•์ธํ•˜๊ธฐ
ยท
์•Œ๊ณ ๋ฆฌ์ฆ˜
https://www.acmicpc.net/problem/10988 10988๋ฒˆ: ํŒฐ๋ฆฐ๋“œ๋กฌ์ธ์ง€ ํ™•์ธํ•˜๊ธฐ ์ฒซ์งธ ์ค„์— ๋‹จ์–ด๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‹จ์–ด์˜ ๊ธธ์ด๋Š” 1๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๊ณ , 100๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์œผ๋ฉฐ, ์•ŒํŒŒ๋ฒณ ์†Œ๋ฌธ์ž๋กœ๋งŒ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค. www.acmicpc.net ์š”๊ตฌ์‚ฌํ•ญ ํŒฐ๋ฆฐ๋“œ๋กฌ ์—ฌ๋ถ€์— ๋”ฐ๋ผ ์ถœ๋ ฅํ•˜๊ธฐ ์„ค๊ณ„ ์šฐ์˜์šฐ, ๊ธฐ๋Ÿฌ๊ธฐ, ๋ณ„๋˜ฅ๋ณ„, ์—ญ์‚ผ์—ญ๊ณผ ๊ฐ™์ด ์•ž ๋’ค ๋ฌธ์ž๊ฐ€ ๊ฐ™์€ ๊ฒƒ์„ ํŒฐ๋ฆฐ๋“œ๋กฌ์ด๋ผ๊ณ  ํ•œ๋‹ค. ์ฒ˜์Œ์—๋Š” ๋ฌธ์ž์—ด์˜ ๊ธธ์ด๋ฅผ ๊ตฌํ•œ ํ›„ ๋ฐ˜์œผ๋กœ ๋‚˜๋ˆ„์–ด reverse ํ•˜๋Š” ๋ฐฉ๋ฒ•์„ ์ƒ๊ฐํ–ˆ์ง€๋งŒ, ์•ž๋’ค ๊ธ€์ž๊ฐ€ ๊ฐ™์€ ํŒฐ๋ฆฐ๋“œ๋กฌ์ด๊ธฐ ๋•Œ๋ฌธ์— for๋ฌธ์„ ์‚ฌ์šฉํ•˜์ง€ ์•Š๊ณ ๋„ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์„ ๊ฒƒ ๊ฐ™๋‹ค๋Š” ์ƒ๊ฐ์ด ๋“ค์—ˆ๋‹ค. ์ด๋•Œ ์ด์ „์— ์‚ฌ์šฉํ•ด๋ดค๋˜ StringBuffer์˜ reverse๋ฅผ ํ™œ์šฉํ–ˆ๋‹ค. ๋‚ด ํ’€์ด import java.util.Scanner..
๋ฐฑ์ค€ 2609 java ์ตœ๋Œ€๊ณต์•ฝ์ˆ˜์™€ ์ตœ์†Œ๊ณต๋ฐฐ์ˆ˜
ยท
์•Œ๊ณ ๋ฆฌ์ฆ˜
https://www.acmicpc.net/problem/2609 2609๋ฒˆ: ์ตœ๋Œ€๊ณต์•ฝ์ˆ˜์™€ ์ตœ์†Œ๊ณต๋ฐฐ์ˆ˜ ์ฒซ์งธ ์ค„์—๋Š” ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง„ ๋‘ ์ˆ˜์˜ ์ตœ๋Œ€๊ณต์•ฝ์ˆ˜๋ฅผ, ๋‘˜์งธ ์ค„์—๋Š” ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง„ ๋‘ ์ˆ˜์˜ ์ตœ์†Œ ๊ณต๋ฐฐ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. www.acmicpc.net ์ •๋‹ตํ’€์ด 1. ๋ฐ˜๋ณต๋ฌธ์„ ์ด์šฉํ•œ ๋ฐฉ๋ฒ• import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int a = in.nextInt(); int b = in.nextInt(); int d = gcd(a, b);// ์ตœ๋Œ€๊ณต์•ฝ์ˆ˜ System.out.println(d); System.out.println(a * ..
๋ฐฑ์ค€ 2743 java ๋‹จ์–ด ๊ธธ์ด ์žฌ๊ธฐ
ยท
์•Œ๊ณ ๋ฆฌ์ฆ˜
https://www.acmicpc.net/status?from_mine=1&problem_id=2743&user_id=raplend17 ์ฑ„์  ํ˜„ํ™ฉ www.acmicpc.net ๋‚ด ํ’€์ด import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String str = sc.next(); String[] result = str.split(""); System.out.println(result.length); } } ๋‹ค๋ฅธ ํ’€์ด import java.util.Scanner; import java.util.StringTokenizer; public c..
๋ฐฑ์ค€ 11382 java ๊ผฌ๋งˆ ์ •๋ฏผ
ยท
์•Œ๊ณ ๋ฆฌ์ฆ˜
https://www.acmicpc.net/problem/11382 11382๋ฒˆ: ๊ผฌ๋งˆ ์ •๋ฏผ ์ฒซ ๋ฒˆ์งธ ์ค„์— A, B, C (1 ≤ A, B, C ≤ 1012)์ด ๊ณต๋ฐฑ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ฃผ์–ด์ง„๋‹ค. www.acmicpc.net import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); long a = sc.nextLong(); long b = sc.nextLong(); long c = sc.nextLong(); System.out.println(a+b+c); } } ์ฒ˜์Œ ๋‹จ์ˆœํ•˜๊ฒŒ intํ˜•์œผ๋กœ ์ œ์ถœํ–ˆ๋‹ค๊ฐ€ ๋Ÿฐํƒ€์ž„ ์˜ค๋ฅ˜๊ฐ€ ๊ฑธ๋ ธ๋‹ค. ๋ฐ›๋Š” ์ˆซ์ž๊ฐ€ intํ˜•๋ณด๋‹ค ..
๋ž˜๋‹ˆ
'์•Œ๊ณ ๋ฆฌ์ฆ˜' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๊ธ€ ๋ชฉ๋ก