✍️ μ½”ν…Œ μ€€λΉ„/Two Pointer

✍️ μ½”ν…Œ μ€€λΉ„/Two Pointer

[νˆ¬ν¬μΈν„° / Kotlin] BOJ 1644 - μ†Œμˆ˜μ˜ 연속합

문제 ν•˜λ‚˜ μ΄μƒμ˜ μ—°μ†λœ μ†Œμˆ˜μ˜ ν•©μœΌλ‘œ λ‚˜νƒ€λ‚Ό 수 μžˆλŠ” μžμ—°μˆ˜λ“€μ΄ μžˆλ‹€. λͺ‡ 가지 μžμ—°μˆ˜μ˜ 예λ₯Ό λ“€μ–΄ 보면 λ‹€μŒκ³Ό κ°™λ‹€. 3 : 3 (ν•œ 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (μ„Έ 가지) 53 : 5+7+11+13+17 = 53 (두 가지) ν•˜μ§€λ§Œ μ—°μ†λœ μ†Œμˆ˜μ˜ ν•©μœΌλ‘œ λ‚˜νƒ€λ‚Ό 수 μ—†λŠ” μžμ—°μˆ˜λ“€λ„ μžˆλŠ”λ°, 20이 κ·Έ μ˜ˆμ΄λ‹€. 7+13을 κ³„μ‚°ν•˜λ©΄ 20이 λ˜κΈ°λŠ” ν•˜λ‚˜ 7κ³Ό 13이 연속이 μ•„λ‹ˆκΈ°μ— μ ν•©ν•œ ν‘œν˜„μ΄ μ•„λ‹ˆλ‹€. λ˜ν•œ ν•œ μ†Œμˆ˜λŠ” λ°˜λ“œμ‹œ ν•œ 번만 λ§μ…ˆμ— μ‚¬μš©λ  수 있기 λ•Œλ¬Έμ—, 3+5+5+7κ³Ό 같은 ν‘œν˜„λ„ μ ν•©ν•˜μ§€ μ•Šλ‹€. μžμ—°μˆ˜κ°€ μ£Όμ–΄μ‘Œμ„ λ•Œ, 이 μžμ—°μˆ˜λ₯Ό μ—°μ†λœ μ†Œμˆ˜μ˜ ν•©μœΌλ‘œ λ‚˜νƒ€λ‚Ό 수 μžˆλŠ” 경우의 수λ₯Ό κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€. μž…λ ₯ 첫째 쀄에 μžμ—°μˆ˜ N이 주어진닀...

✍️ μ½”ν…Œ μ€€λΉ„/Two Pointer

[νˆ¬ν¬μΈν„° / Kotlin] BOJ 1806 - λΆ€λΆ„ ν•©

문제 10,000 μ΄ν•˜μ˜ μžμ—°μˆ˜λ‘œ 이루어진 길이 N짜리 μˆ˜μ—΄μ΄ 주어진닀. 이 μˆ˜μ—΄μ—μ„œ μ—°μ†λœ μˆ˜λ“€μ˜ λΆ€λΆ„ν•© 쀑에 κ·Έ 합이 S 이상이 λ˜λŠ” 것 쀑, κ°€μž₯ 짧은 κ²ƒμ˜ 길이λ₯Ό κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€. μž…λ ₯ 첫째 쀄에 N (10 ≤ N < 100,000)κ³Ό S (0 < S ≤ 100,000,000)κ°€ 주어진닀. λ‘˜μ§Έ μ€„μ—λŠ” μˆ˜μ—΄μ΄ 주어진닀. μˆ˜μ—΄μ˜ 각 μ›μ†ŒλŠ” 곡백으둜 κ΅¬λΆ„λ˜μ–΄μ Έ 있으며, 10,000μ΄ν•˜μ˜ μžμ—°μˆ˜μ΄λ‹€. 좜λ ₯ 첫째 쀄에 κ΅¬ν•˜κ³ μž ν•˜λŠ” μ΅œμ†Œμ˜ 길이λ₯Ό 좜λ ₯ν•œλ‹€. 만일 κ·ΈλŸ¬ν•œ 합을 λ§Œλ“œλŠ” 것이 λΆˆκ°€λŠ₯ν•˜λ‹€λ©΄ 0을 좜λ ₯ν•˜λ©΄ λœλ‹€. ν•΄κ²° 방법 μ•žμ„  2λ¬Έμ œμ™€ λ‹€λ₯΄κ²Œ 정렬을 ν•  ν•„μš”κ°€ μ—†λŠ” λ¬Έμ œμ΄λ‹€. 주어진 λ°°μ—΄ μžμ²΄μ—μ„œμ˜ κ°€μž₯ μž‘μ€ 길이의 λΆ€λΆ„ 합을 μ°Ύμ•„μ•Όν•˜κΈ° λ•Œλ¬Έμ΄λ‹€. μ•Œκ³ λ¦¬μ¦˜μ€ μ•„λž˜μ™€ κ°™λ‹€. 1. le..

✍️ μ½”ν…Œ μ€€λΉ„/Two Pointer

[νˆ¬ν¬μΈν„° / Kotlin] BOJ 2470 - 두 μš©μ•‘

문제 KOI λΆ€μ„€ κ³Όν•™μ—°κ΅¬μ†Œμ—μ„œλŠ” λ§Žμ€ μ’…λ₯˜μ˜ μ‚°μ„± μš©μ•‘κ³Ό μ•ŒμΉΌλ¦¬μ„± μš©μ•‘μ„ λ³΄μœ ν•˜κ³  μžˆλ‹€. 각 μš©μ•‘μ—λŠ” κ·Έ μš©μ•‘μ˜ νŠΉμ„±μ„ λ‚˜νƒ€λ‚΄λŠ” ν•˜λ‚˜μ˜ μ •μˆ˜κ°€ μ£Όμ–΄μ Έμžˆλ‹€. μ‚°μ„± μš©μ•‘μ˜ νŠΉμ„±κ°’μ€ 1λΆ€ν„° 1,000,000,000κΉŒμ§€μ˜ μ–‘μ˜ μ •μˆ˜λ‘œ λ‚˜νƒ€λ‚΄κ³ , μ•ŒμΉΌλ¦¬μ„± μš©μ•‘μ˜ νŠΉμ„±κ°’μ€ -1λΆ€ν„° -1,000,000,000κΉŒμ§€μ˜ 음의 μ •μˆ˜λ‘œ λ‚˜νƒ€λ‚Έλ‹€. 같은 μ–‘μ˜ 두 μš©μ•‘μ„ ν˜Όν•©ν•œ μš©μ•‘μ˜ νŠΉμ„±κ°’μ€ ν˜Όν•©μ— μ‚¬μš©λœ 각 μš©μ•‘μ˜ νŠΉμ„±κ°’μ˜ ν•©μœΌλ‘œ μ •μ˜ν•œλ‹€. 이 μ—°κ΅¬μ†Œμ—μ„œλŠ” 같은 μ–‘μ˜ 두 μš©μ•‘μ„ ν˜Όν•©ν•˜μ—¬ νŠΉμ„±κ°’μ΄ 0에 κ°€μž₯ κ°€κΉŒμš΄ μš©μ•‘μ„ λ§Œλ“€λ €κ³  ν•œλ‹€. 예λ₯Ό λ“€μ–΄, 주어진 μš©μ•‘λ“€μ˜ νŠΉμ„±κ°’μ΄ [-2, 4, -99, -1, 98]인 κ²½μš°μ—λŠ” νŠΉμ„±κ°’μ΄ -99인 μš©μ•‘κ³Ό νŠΉμ„±κ°’μ΄ 98인 μš©μ•‘μ„ ν˜Όν•©ν•˜λ©΄ νŠΉμ„±κ°’μ΄ -1인 μš©μ•‘μ„ λ§Œλ“€ 수 있고, 이 μš©μ•‘..

✍️ μ½”ν…Œ μ€€λΉ„/Two Pointer

[νˆ¬ν¬μΈν„° / Kotlin] BOJ 3273 - 두 수의 ν•©

문제 n개의 μ„œλ‘œ λ‹€λ₯Έ μ–‘μ˜ μ •μˆ˜ a1, a2, ..., an으둜 이루어진 μˆ˜μ—΄μ΄ μžˆλ‹€. ai의 값은 1보닀 ν¬κ±°λ‚˜ κ°™κ³ , 1000000보닀 μž‘κ±°λ‚˜ 같은 μžμ—°μˆ˜μ΄λ‹€. μžμ—°μˆ˜ xκ°€ μ£Όμ–΄μ‘Œμ„ λ•Œ, ai + aj = x (1 ≤ i < j ≤ n)을 λ§Œμ‘±ν•˜λŠ” (ai, aj)쌍의 수λ₯Ό κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€. μž…λ ₯ 첫째 쀄에 μˆ˜μ—΄μ˜ 크기 n이 주어진닀. λ‹€μŒ μ€„μ—λŠ” μˆ˜μ—΄μ— ν¬ν•¨λ˜λŠ” μˆ˜κ°€ 주어진닀. μ…‹μ§Έ μ€„μ—λŠ” xκ°€ 주어진닀. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000) 좜λ ₯ 문제의 쑰건을 λ§Œμ‘±ν•˜λŠ” 쌍의 개수λ₯Ό 좜λ ₯ν•œλ‹€. 해결방법 문제λ₯Ό 처음 μ ‘ν–ˆμ„ λ•ŒλŠ” μ½”ν‹€λ¦°μ˜ findλ₯Ό μ‚¬μš©ν•΄μ„œ 문제λ₯Ό ν•΄κ²°ν–ˆλ‹€. μš°μ„  μž…λ ₯ 받은 배열을 μ˜€λ¦„μ°¨μˆœμœΌλ‘œ μ •λ ¬ν•˜κ³ , 맨 μ•žλΆ€ν„° 탐색을 μ§„ν–‰ν•˜λ©΄μ„œ μž…λ ₯받은 x - ..

kodo_o
'✍️ μ½”ν…Œ μ€€λΉ„/Two Pointer' μΉ΄ν…Œκ³ λ¦¬μ˜ κΈ€ λͺ©λ‘