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

๋ฐ˜์‘ํ˜•

Algorithm

[Algorithm/Java][๋ฐฑ์ค€] 2775๋ฒˆ ๋ถ€๋…€ํšŒ์žฅ์ด ๋ ํ…Œ์•ผ [BOJ] 2775๋ฒˆ ๋ถ€๋…€ํšŒ์žฅ์ด ๋ ํ…Œ์•ผ https://www.acmicpc.net/problem/2775 ๋ฌธ์ œ ์ ‘๊ทผ ๋ฐฑ์ค€์—์„œ ์—์ œ๋กœ ์ค€ ์ž…๋ ฅ๊ณผ ์ถœ๋ ฅ์„ ํ•˜๋‚˜์”ฉ ์“ฐ๋‹ค๋ณด๋ฉด ๊ทœ์น™์ด ๋ณด์ด๊ฒŒ ๋œ๋‹ค. 000 -> 0 001 -> 1 002 -> 2 003 -> 3 100 -> 0 101 -> 1 102 -> 3 103 -> 6 200 -> 0 201 -> 1 202 -> 4 203 -> 10 ์ด๋•Œ 103ํ˜ธ์—๋Š” 003ํ˜ธ์™€ 102ํ˜ธ๋ฅผ ํ•ฉ์นœ ๊ฐ’์ด ์žˆ๊ณ , 203ํ˜ธ์—๋Š” 103ํ˜ธ์™€ 202ํ˜ธ๋ฅผ ํ•ฉ์นœ ๊ฐ’์ด ์žˆ๋‹ค. ์ด๋ฅผ ์ ํ™”์‹์œผ๋กœ ๋ฐ”๊ฟ”๋ณด๋ฉด (k0n)ํ˜ธ = k-10nํ˜ธ + k0n-1ํ˜ธ ์ฝ”๋“œ๋กœ ๋ฐ”๊ฟ”๋ณด๋ฉด dp[floor][room] = dp[foor-1][n] + dp[floor][n-1]์ด ๋œ๋‹ค. ์ด๋ฅผ ์ฝ”๋“œ๋กœ ๋ฐ”๊พธ๋ฉด ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค. Co.. ๋”๋ณด๊ธฐ
[Algorithm/Java][๋ฐฑ์ค€] 14226๋ฒˆ ์ด๋ชจํ‹ฐ์ฝ˜ [BOJ] 14226๋ฒˆ ์ด๋ชจํ‹ฐ์ฝ˜ https://www.acmicpc.net/problem/14226 ๋ฌธ์ œ ์ ‘๊ทผ ํ™”๋ฉด์— ์žˆ๋Š” ์ด๋ชจํ‹ฐ์ฝ˜์„ S๊ฐœ ๋งŒ๋“œ๋Š” ์ตœ์†Œ ์‹œ๊ฐ„์„ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ด๋‹ค. ํ™”๋ฉด์— ์žˆ๋Š” ์ด๋ชจํ‹ฐ์ฝ˜ ๊ฐœ์ˆ˜์™€ ํด๋ฆฝ๋ณด๋“œ์— ์žˆ๋Š” ์ด๋ชจํ‹ฐ์ฝ˜ ๊ฐœ์ˆ˜ ๊ทธ๋ฆฌ๊ณ  ์‹œ๊ฐ„ ์ •๋ณด๋ฅผ ์ €์žฅํ•  ์ˆ˜ ์žˆ๋Š” Emoticon ํด๋ž˜์Šค๋ฅผ ๋งŒ๋“ค๊ณ  isVisited ๋ฐฐ์—ด์„ ํ™”๋ฉด์— ์žˆ๋Š” ์ด๋ชจํ‹ฐ์ฝ˜ ์ˆ˜์™€ ํด๋ฆฝ๋ณด๋“œ์— ์žˆ๋Š” ์ด๋ชจํ‹ฐ์ฝ˜ ์ˆ˜๋ฅผ ๊ณ ๋ คํ•  ์ˆ˜ ์žˆ๋„๋ก 2์ฐจ์› ๋ฐฐ์—ด๋กœ ๋งŒ๋“ค์—ˆ๋‹ค. ๊ทธ๋ฆฌ๊ณ  BFS๋ฅผ ์ด์šฉํ•ด์„œ ํ™”๋ฉด์— ์žˆ๋Š” ์ด๋ชจํ‹ฐ์ฝ˜์„ ํด๋ฆฝ๋ณด๋“œ์— ์ €์žฅํ•˜๋Š” ๊ฒฝ์šฐ, ํ™”๋ฉด์— ์žˆ๋Š” ์ด๋ชจํ‹ฐ์ฝ˜ ํ•œ๊ฐœ๋ฅผ ์ œ๊ฑฐํ•˜๋Š” ๊ฒฝ์šฐ, ํด๋ฆฝ๋ณด๋“œ์— ์žˆ๋Š” ์ด๋ชจํ‹ฐ์ฝ˜์„ ๋ถ™์—ฌ๋„ฃ๋Š” ๊ฒฝ์šฐ ์„ธ๊ฐ€์ง€๋ฅผ ๊ณ ๋ คํ•ด์„œ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ–ˆ๋‹ค. ๋ฌธ์ œ๋ฅผ ๋ณด๊ณ  ์ด์ฐจ์› ๋ฐฐ์—ด๋กœ ํ•ด๊ฒฐํ•  ์ƒ๊ฐ์„ ํ•˜์ง€ ๋ชปํ•ด์„œ ํ‘ธ๋Š”๋ฐ ๊ฝค๋‚˜ ์˜ค๋ž˜๊ฑธ๋ ธ๋‹ค...๊ทผ๋ฐ .. ๋”๋ณด๊ธฐ
[Algorithm/Java][๋ฐฑ์ค€] 1916๋ฒˆ ์ตœ์†Œ๋น„์šฉ ๊ตฌํ•˜๊ธฐ [BOJ] 1916๋ฒˆ ์ตœ์†Œ๋น„์šฉ ๊ตฌํ•˜๊ธฐ https://www.acmicpc.net/problem/1916 ๋ฌธ์ œ ์ ‘๊ทผ ์–‘์˜ ๊ฐ€์ค‘์น˜๋ฅผ ๊ฐ€์ง„ ๊ฐ„์„ ์œผ๋กœ ์ด๋ฃจ์–ด์ง„ ๊ทธ๋ž˜ํ”„์—์„œ ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ์ฐพ๋Š” ๋ฌธ์ œ์—ฌ์„œ ๋‹ค์ต์ŠคํŠธ๋ผ์™€ ๋ฒจ๋งŒํฌ๋“œ ์•Œ๊ณ ๋ฆฌ์ฆ˜ 2๊ฐœ๋ฅผ ๋ชจ๋‘ ์ ์šฉํ•ด์„œ ๊ตฌํ˜„ํ–ˆ๋‹ค. ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์šฐ์„ ์ˆœ์œ„ ํ๋ฅผ ์ด์šฉํ•ด์„œ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ์ค„์˜€๊ณ , ๋‹ค์ต์ŠคํŠธ๋ผ์™€ ๋ฒจ๋งŒํฌ๋“œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ํฌ์ŠคํŠธ์— ์ •๋ฆฌํ–ˆ๋‹ค. [์•Œ๊ณ ๋ฆฌ์ฆ˜] ๋‹ค์ต์ŠคํŠธ๋ผ & ๋ฒจ๋งŒํฌ๋“œ Code ๋‹ค์ต์ŠคํŠธ๋ผ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; class Node implements Comparable { int to; int .. ๋”๋ณด๊ธฐ
[Algorithm/Java][๋ฐฑ์ค€] 1806๋ฒˆ ๋ถ€๋ถ„ํ•ฉ [BOJ] 1806๋ฒˆ ๋ถ€๋ถ„ํ•ฉ https://www.acmicpc.net/problem/1806 ๋ฌธ์ œ ์ ‘๊ทผ ํˆฌ ํฌ์ธํ„ฐ๋ฅผ ์ด์šฉํ•ด์„œ ๋ฌธ์ œ๋ฅผ ํ’€์—ˆ๋‹ค. deque์™€ ์ด๋ถ„ ํƒ์ƒ‰์„ ์ด์šฉํ•ด์„œ๋„ ํ’€ ์ˆ˜ ์žˆ๋‹ค๊ณ  ํ•˜๋Š”๋ฐ ๋ถ„๋ฅ˜๊ฐ€ ํˆฌ ํฌ์ธํ„ฐ๋ผ์„œ ํˆฌ ํฌ์ธํ„ฐ๋ฅผ ์‚ฌ์šฉํ•ด์„œ ํ’€์—ˆ๋‹ค. start์™€ end์ธ ๋‘ ๊ฐœ์˜ ์ธ๋ฑ์Šค๋ฅผ ์‚ฌ์šฉํ•˜๊ณ  sum์ด t(๋ชฉํ‘œ ๊ฐ’)๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์œผ๋ฉด end๋ฅผ +1ํ•ด์„œ ํ•œ๊ฐœ๋ฅผ ๋” ๋”ํ•˜๋„๋ก ํ•˜๊ณ , sum์ด t(๋ชฉํ‘œ ๊ฐ’)๋ณด๋‹ค ํฌ๋ฉด start๋ฅผ +1 ํ•ด์„œ ํ•ฉ์—์„œ ํ•œ๊ฐœ๋ฅผ ๋นผ์„œ ๋ชฉํ‘œ ๊ฐ’์— ์ ‘๊ทผํ•˜๋„๋ก ํ•œ๋‹ค. ํˆฌ ํฌ์ธํ„ฐ๋ฅผ ์‚ฌ์šฉํ•˜๊ฒŒ ๋˜๋ฉด O(N)์œผ๋กœ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๊ฒŒ ๋˜๋Š” ์žฅ์ ์ด ์žˆ๋‹ค. Code import java.io.BufferedReader; import java.io.IOException; import java.io.. ๋”๋ณด๊ธฐ
[Algorithm/Java][๋ฐฑ์ค€] 1700๋ฒˆ ๋ฉ€ํ‹ฐํƒญ ์Šค์ผ€์ค„๋ง [BOJ] 1700๋ฒˆ ๋ฉ€ํ‹ฐํƒญ ์Šค์ผ€์ค„๋ง https://www.acmicpc.net/problem/1700 ๋ฌธ์ œ ์ ‘๊ทผ ์˜ˆ์ „์— ์šด์˜์ฒด์ œ ์‹œ๊ฐ„์— ๋ฐฐ์› ๋˜ ํŽ˜์ด์ง€ ๊ต์ฒด ์•Œ๊ณ ๋ฆฌ์ฆ˜๊ณผ ๋น„์Šทํ•ด์„œ ์‰ฝ๊ฒŒ ํ’€ ์ˆ˜ ์žˆ์—ˆ๋‹ค. ๋ฉ€ํ‹ฐํƒญ์— ์ž๋ฆฌ๊ฐ€ ์žˆ๊ฑฐ๋‚˜, ์ด๋ฏธ ๊ฝ‚ํ˜€์žˆ์„ ๋•Œ๋Š” ๊ณ ๋ คํ•  ๊ฒƒ ์—†์ด ๊ทธ๋ƒฅ ๊ฝ‚๊ฑฐ๋‚˜ ๋„˜์–ด๊ฐ€๋ฉด ๋˜์ง€๋งŒ ์ž๋ฆฌ๊ฐ€ ์—†์„๋•Œ ๊ณ ๋ คํ•ด์•ผ ๋  ๊ฒฝ์šฐ์˜ ์ˆ˜๊ฐ€ ์žˆ๋‹ค. ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ์ •๋ฆฌํ•ด ๋ณด๋ฉด ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค. ๋ฉ€ํ‹ฐํƒญ์— ์ž๋ฆฌ๊ฐ€ ์žˆ๋Š” ๊ฒฝ์šฐ ์ด๋ฏธ ๋ฉ€ํ‹ฐํƒญ์— ๊ฝ‚ํ˜€ ์žˆ๋Š” ๊ฒฝ์šฐ ๋ฉ€ํ‹ฐํƒญ์— ์ž๋ฆฌ๊ฐ€ ์—†๋Š” ๊ฒฝ์šฐ 3.1. ์‚ฌ์šฉํ•˜์ง€ ์•Š์„ ์ „์ž๊ธฐ๊ธฐ๊ฐ€ ๊ฝ‚ํ˜€ ์žˆ๋Š” ๊ฒฝ์šฐ 3.2. ๋ชจ๋“  ์ „์ž๊ธฐ๊ธฐ๊ฐ€ ๋‹ค์‹œ ์‚ฌ์šฉํ•  ์ „์ž๊ธฐ๊ธฐ์ธ ๊ฒฝ์šฐ ์‚ฌ์šฉํ•˜์ง€ ์•Š์„ ์ „์ž๊ธฐ๊ธฐ๊ฐ€ ๊ฝ‚ํ˜€ ์žˆ์œผ๋ฉด ๊ทธ ์ „์ž๊ธฐ๊ธฐ๋ฅผ ์ œ๊ฑฐํ•˜๊ณ  ์ƒˆ๋กœ์šด ์ „์ž๊ธฐ๊ธฐ๋ฅผ ๊ฝ‚์œผ๋ฉด ํ•ด๊ฒฐ๋œ๋‹ค. ๋ชจ๋“  ์ „์ž๊ธฐ๊ธฐ๊ฐ€ ๋‹ค์‹œ ์‚ฌ์šฉํ•  ์ „์ž๊ธฐ๊ธฐ์ธ ๊ฒฝ์šฐ ์šฐ์„ ์ˆœ์œ„๋ฅผ.. ๋”๋ณด๊ธฐ
[Algorithm/Java][๋ฐฑ์ค€] 1062๋ฒˆ ๊ฐ€๋ฅด์นจ [BOJ] 1062๋ฒˆ ๊ฐ€๋ฅด์นจ https://www.acmicpc.net/problem/1062 ๋ฌธ์ œ ์ ‘๊ทผ ๋ฐฑํŠธ๋ž˜ํ‚น์„ ์ด์šฉํ•ด์„œ ๋ชจ๋“  ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ํƒ์ƒ‰ํ•ด๋ณด๋Š” ๋ฌธ์ œ์˜€๋‹ค. ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ์ค„์ด๊ธฐ ์œ„ํ•ด์„œ ๋ชจ๋“  ๋‹จ์–ด๊ฐ€ ํฌํ•จํ•˜๋Š” anta, tica ์— ํฌํ•จ๋œ 5๊ฐœ์˜ ๋‹จ์–ด๋ฅผ ํ•„์ˆ˜ ๋‹จ์–ด๋กœ ํฌํ•จ์‹œํ‚ค๊ณ , ๊ณต๋ฐฑ์œผ๋กœ ๋ฐ”๊ฟ”์ฃผ์–ด์„œ ํƒ์ƒ‰ํ•ด์•ผ ํ•˜๋Š” ๋‹จ์–ด์˜ ๊ธธ์ด๋ฅผ ์ค„์˜€๊ณ , ๋ฐฐ์šธ ์ˆ˜ ์žˆ๋Š” ๋‹จ์–ด๊ฐ€ 5๊ฐœ ๋ณด๋‹ค ์ ์„๋•Œ 0, 26๊ฐœ ์ผ ๋•Œ ๋ชจ๋“  ๋‹จ์–ด๋ฅผ ๋ฐฐ์šธ ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ n์„ ์ถœ๋ ฅํ–ˆ๋‹ค. ๋ฐฑํŠธ๋ž˜ํ‚น์„ ํ•  ๋•Œ๋„ a~z๊นŒ์ง€ ์ˆœ์ฐจ์ ์œผ๋กœ ํ•™์Šตํ•˜๊ธฐ ๋•Œ๋ฌธ์— ์‹œ์ž‘ ์ธ๋ฑ์Šค๋ฅผ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ถ”๊ฐ€ํ•ด์„œ ์ด๋ฏธ ์ง€๋‚˜๊ฐ„ ๊ณณ์€ ํƒ์ƒ‰ํ•˜์ง€ ์•Š๋„๋ก ํ–ˆ๋‹ค. Code import java.io.BufferedReader; import java.io.IOException; import jav.. ๋”๋ณด๊ธฐ
[Algorithm/Java][๋ฐฑ์ค€] 2504๋ฒˆ ๊ด„ํ˜ธ์˜ ๊ฐ’ [BOJ] 2504๋ฒˆ ๊ด„ํ˜ธ์˜ ๊ฐ’ https://www.acmicpc.net/problem/2504 ๋ฌธ์ œ ์ ‘๊ทผ Stack์„ ์ด์šฉํ•ด์„œ ์—ด๋ฆฐ ๊ด„ํ˜ธ๋ฅผ ์ €์žฅํ•˜๊ณ , ๊ด„ํ˜ธ๊ฐ€ ๋‹ซํž ๋•Œ X๊ฐ’์„ ๋‹ค์‹œ ์Šคํƒ์— ์ €์žฅํ•œ๋‹ค. ๊ด„ํ˜ธ ์†์— ์ˆซ์ž๊ฐ€ ์žˆ์œผ๋ฉด ๊ทธ ์ˆซ์ž๋“ค์„ ๋‹ค ๋”ํ•ด์„œ ํ•ด๋‹น ๊ด„ํ˜ธ ๊ฐ’์„ ๊ณฑํ•ด์ฃผ์—ˆ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ์Šคํƒ์„ Character ์ž๋ฃŒํ˜•์œผ๋กœ ํ•˜๋ฉด ๊ด„ํ˜ธ์™€ ์ˆซ์ž๋ฅผ ๊ตฌ๋ถ„ํ•˜์ง€ ๋ชปํ•˜๊ธฐ ๋•Œ๋ฌธ์—, String์œผ๋กœ ํ•ด์„œ ์ด ๊ฒฝ์šฐ๋ฅผ ํ•ด๊ฒฐํ–ˆ๋‹ค. ์ฝ”๋“œ๊ฐ€ ๋„ˆ๋ฌด ๋ณต์žกํ•˜๊ณ  ์˜ฌ๋ฐ”๋ฅธ ๊ด„ํ˜ธ๊ฐ€ ์•„๋‹Œ๊ฒƒ์„ ๊ฒ€์‚ฌํ•˜๊ธฐ๊ฐ€ ๊นŒ๋‹ค๋กœ์› ๋‹ค... Code import java.util.Scanner; import java.util.Stack; public class BOJ2504 { public static void main(String[] args) { Scanner sc .. ๋”๋ณด๊ธฐ
[Algorithm/Java][๋ฐฑ์ค€] 1987๋ฒˆ ์•ŒํŒŒ๋ฒณ [BOJ] 1987๋ฒˆ ์•ŒํŒŒ๋ฒณ https://www.acmicpc.net/problem/1987 ๋ฌธ์ œ ์ ‘๊ทผ ๊ฐ€๋กœ R, ์„ธ๋กœ C๋กœ ๋œ ๋ณด๋“œ์— ๋Œ€๋ฌธ์ž ์•ŒํŒŒ๋ฒณ์ด ์ ํ˜€์žˆ๊ณ , ๊ฐ€์žฅ ์™ผ์ชฝ ์œ„๋ถ€ํ„ฐ ์•ŒํŒŒ๋ฒณ ๋‹น ํ•œ๋ฒˆ์”ฉ๋งŒ ๋ฐฉ๋ฌธํ•ด์„œ ๊ฐ€์žฅ ๋ฉ€๋ฆฌ ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๊ธธ์ด๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ด๋‹ค. ์ฒ˜์Œ์—๋Š” ์•„๋ฌด์ƒ๊ฐ ์—†์ด bfs๋กœ ํ–ˆ๋‹ค๊ฐ€ ์ƒ๊ฐํ•ด๋ณด๋‹ˆ๊นŒ dfs๊ฐ€ ๋” ๋งž๋Š” ๊ฒƒ ๊ฐ™์•„์„œ ๋ฐฉํ–ฅ์„ ํ‹€์—ˆ๋‹ค. ์ฒ˜์Œ์—๋Š” ๋ณด๋“œ์— ๋ฐฉ๋ฌธ ์—ฌ๋ถ€๋ฅผ ์ €์žฅํ•˜๋Š” isVisited์™€ ์•ŒํŒŒ๋ฒณ ๋ฐฉ๋ฌธ ์—ฌ๋ถ€๋ฅผ ์ €์žฅํ•˜๋Š” alphabetVisited๋ฅผ ์‚ฌ์šฉํ•˜๋ ค ํ–ˆ๋Š”๋ฐ, ์ƒ๊ฐํ•ด๋ณด๋‹ˆ๊นŒ ํ•œ๋ฒˆ ๋ฐฉ๋ฌธํ•œ ์•ŒํŒŒ๋ฒณ์€ ๋ฐฉ๋ฌธํ•˜์ง€ ๋ชปํ•˜๋‹ˆ๊นŒ ๋ณด๋“œ์— ๋ฐฉ๋ฌธ์—ฌ๋ถ€๋ฅผ ์ €์žฅํ•  ํ•„์š”๊ฐ€ ์—†๊ณ , ๊ฒฝ๋กœ๋ฅผ String์œผ๋กœ ๊ณ„์† ์ถ”๊ฐ€ํ•ด๊ฐ€๋ฉด์„œ ํ•˜๋ฉด ์•ŒํŒŒ๋ฒณ ๋ฐฉ๋ฌธ ์—ฌ๋ถ€๋„ ๋”ฐ๋กœ ์ €์žฅํ•˜์ง€ ์•Š์•„๋„ ๋  ๊ฒƒ ๊ฐ™์•„์„œ dfs์— ๊ฐ€๋ ค๋Š” x,y์™€ ์ง€๊ธˆ.. ๋”๋ณด๊ธฐ