[TIL] - 2023.04.13

2023. 4. 21. 00:06ยท ์ •๊ธ€/TIL
๋ชฉ์ฐจ
  1. ๐Ÿ‘ฅ ์ด์ง„ ํƒ์ƒ‰
  2. ๋ธŒ๋ฃจํŠธ ํฌ์Šค ๋ฌธ์ œ ๋ฆฌ์ŠคํŠธ

๐Ÿ‘ฅ ์ด์ง„ ํƒ์ƒ‰


  
- ๋ฐฐ์—ด์ด ์ •๋ ฌ๋˜์–ด ์žˆ์–ด์•ผ ํ•˜๋ฉฐ, ํ•˜๋‚˜์˜ ๋ฐฐ์—ด์—์„œ ๋ฐ˜๋ฐ˜ ์ชผ๊นจ์„œ ๊ฐ’์„ ์ฐพ๋Š” ํƒ์ƒ‰์ด๋‹ค.
- ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” O(logN)์ด๋‹ค

์ด์ง„ ํƒ์ƒ‰์˜ ๊ธฐ๋ณธ ํ‹€


  
from sys import stdin as s
s = open('input.txt','rt')
N, M = list(map(int,s.readline().split()))
arr = list(map(int,s.readline().split()))
def binary_search(array, target,start,end):
if start > end:
return None
mid = (start + end) //2
if array[mid] == target:
return mid
elif array[mid] >target:
return binary_search(array,target,start,mid-1)
else :
return binary_search(array,target,mid+1,end)
result = binary_search(arr,M,0,N-1)
if result == "None":
print("์กด์žฌํ•˜์ง€ ์•Š์Šต๋‹ˆ๋‹ค.")
else:
print(result + 1)

๋ฐ˜๋ณต๋ฌธ์œผ๋กœ ์ž‘์„ฑํ•œ ์ด์ง„ ํƒ์ƒ‰ ํ‹€


  
def binary_search(array, target, start, end):
while start <= end:
mid = (start + end) // 2
# ์›ํ•˜๋Š” ๊ฐ’ ์ฐพ์€ ๊ฒฝ์šฐ ์ธ๋ฑ์Šค ๋ฐ˜ํ™˜
if array[mid] == target:
return mid
# ์›ํ•˜๋Š” ๊ฐ’์ด ์ค‘๊ฐ„์ ์˜ ๊ฐ’๋ณด๋‹ค ์ž‘์€ ๊ฒฝ์šฐ ์™ผ์ชฝ ๋ถ€๋ถ„(์ ˆ๋ฐ˜์˜ ์™ผ์ชฝ ๋ถ€๋ถ„) ํ™•์ธ
elif array[mid] > target:
end = mid - 1
# ์›ํ•˜๋Š” ๊ฐ’์ด ์ค‘๊ฐ„์ ์˜ ๊ฐ’๋ณด๋‹ค ํฐ ๊ฒฝ์šฐ ์˜ค๋ฅธ์ชฝ ๋ถ€๋ถ„(์ ˆ๋ฐ˜์˜ ์˜ค๋ฅธ์ชฝ ๋ถ€๋ถ„) ํ™•์ธ
else:
start = mid + 1
return None
n, target = list(map(int, input().split()))
array = list(map(int, input().split()))
result = binary_search(array, target, 0, n - 1)
if result is None:
print('์›์†Œ๊ฐ€ ์กด์žฌ X')
else:
print(result + 1)

๋ธŒ๋ฃจํŠธ ํฌ์Šค ๋ฌธ์ œ ๋ฆฌ์ŠคํŠธ

NO LV ์œ ํ˜• ์ œ๋ชฉ ๋น„๊ณ 
1110 B1 ๋ธŒ๋ฃจํŠธ ํฌ์Šค ๋”ํ•˜๊ธฐ ์‚ฌ์ดํด ์„ฑ๊ณต
9095 S3 ๋ธŒ๋ฃจํŠธ ํฌ์Šค 1,2,3 ๋”ํ•˜๊ธฐ ์„ฑ๊ณต
1182 S2 ๋ธŒ๋ฃจํŠธ ํฌ์Šค ๋ถ€๋ถ„ ์ˆ˜์—ด์˜ ํ•ฉ ์„ฑ๊ณต






 

 ์ž‘์€ ์ผ์— ์ตœ์„ ์„ ๋‹คํ•˜๋ผ

" ํ–‰๋ณต์€ ์ž‘์€ ์ผ์„ ํ†ตํ•ด ๊นจ๋‹ซ๊ฒŒ ๋œ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ์ด๊ฒƒ์€ ๊ฒฐ์ฝ” ์ž‘์€ ์ผ์ด ์•„๋‹ˆ๋‹ค. "

- ์ œ๋…ผ, ๋””์˜ค๊ฒŒ๋„ค์Šค์˜ ๊ฐ•์˜์—์„œ ์ธ์šฉ, ํƒ์›”ํ•œ ์ฒ ํ•™์ž๋“ค์˜ ์‚ถ 7. 1. 26

์ข‹์€ ์‚ฌ๋žŒ์ด๋ผ๋Š” ํ‰ํŒ์€ ๊ทธ๊ฐ€ ํ•œ ๋ง ๋•Œ๋ฌธ์ด ์•„๋‹ˆ๋‹ค. ๊ทธ๊ฐ€ ํ–‰ํ•œ ๋ฐ”๋žŒ์งํ•œ ํ–‰๋™ ๋•Œ๋ฌธ์— ๋งŒ๋“ค์–ด์ง„๋‹ค. ์ด๋Š” ๋งˆ๋ฒ• ๊ฐ™์€ ๋‹จ ํ•œ๋ฒˆ์˜ ํ–‰๋™์ด ์ด๋ฃจ์–ด ๋‚ด๋Š” ๊ฒƒ์ด ์•„๋‹ˆ๋ผ ๋ฐ”๋žŒ์งํ•œ ์„ ํƒ์˜ ๋ˆ„์ ์ด ๋งŒ๋“ค์–ด ๋‚ด๋Š” ๊ฒƒ์ด๋‹ค.



 ๋ˆˆ ์•ž์— ์žˆ๋Š” ์ผ์— ์ง‘์ค‘ํ•˜๋ผ

" ๋งค์ผ๋งค์ผ ๋‹ฅ์ณ์˜ฌ ๋ชจ๋“  ์ผ์„ ๋กœ๋งˆ์ธ๋“ค์ฒ˜๋Ÿผ ๊ฐ•๊ฑดํ•œ ๋ง๋ฏ€์œผ๋กœ ์ฒ˜๋ฆฌํ•˜๋ผ. ์—„๊ฒฉํ•˜๊ณ  ๋‹จ์ˆœํ•œ ์œ„์—„, ์• ์ •๊ณผ ์ž์œ , ๊ทธ๋ฆฌ๊ณ  ๊ณตํ‰๋ฌด์‚ฌํ•จ์œผ๋กœ ๋Œ€ํ•˜๋ผ, ์ด๊ฒƒ ์™ธ์— ๋‹ค๋ฅธ ์‚ฌํ•ญ์€ ์ƒ๊ฐํ•˜์ง€ ๋ง๋ผ. ํ•ฉ๋ฆฌ์  ์ด์„ฑ์ด ๊ฐ์ •์— ํœ˜๋‘˜๋ฆฌ์ง€ ์•Š๋„๋ก ํ•˜๊ณ , ์žก๋…์— ๋งค์ด์ง€ ์•Š์œผ๋ฉฐ, ๊ทน์ ์ธ ์ƒํ™ฉ๊ณผ ์ž๋งŒ์‹ฌ, ๊ณต์ •ํ•œ ๋ชซ์— ๋Œ€ํ•œ ๋ถˆํ‰์„ ์ž ์žฌ์›Œ๋ผ. ๋งˆ์ง€๋ง‰์ธ ๊ฒƒ์ฒ˜๋Ÿผ ์ฃผ์–ด์ง„ ์ผ์— ์ ‘๊ทผํ•˜๋ผ. ์ด ๋ช‡๊ฐ€์ง€๋ฅผ ๋ฐฐ์šฐ๋Š” ๊ฒƒ๋งŒ์œผ๋กœ๋„ ํ’์š”๋กœ์šด ์‚ถ๊ณผ ๋…์‹คํ•œ ์ธ์ƒ์„ ์™„์„ฑํ•  ์ˆ˜ ์žˆ์„ ๊ฒƒ์ด๋‹ค. ์ด๋ฅผ ๋Š์ž„์—†์ด ์‹ค์ฒœํ•  ์ˆ˜ ์žˆ๋‹ค๋ฉด ์‹ ๋„ ์šฐ๋ฆฌ์—๊ฒŒ ๋” ๋งŽ์€ ๊ฒƒ์„ ์š”๊ตฌํ•˜์ง€ ์•Š๋Š”๋‹ค. "

- ๋งˆ๋ฅด์ฟ ์Šค ์•„์šฐ๋ ๋ฆฌ์šฐ์Šค, ๋ช…์ƒ๋ก, 2.5

์ˆ˜๋งŽ์€ ์žฅ์• ๋ฌผ ์•ž์—์„œ ๋‹ค๋ฅธ ์‚ฌ๋žŒ์„ ์‹ ๊ฒฝ ์“ฐ์ง€ ์•Š๊ณ  ๋ฌต๋ฌตํžˆ ๋‚˜์˜ ๊ธธ์„ ๊ฑธ์–ด๊ฐˆ ์ˆ˜ ์žˆ์–ด์•ผ ํ•œ๋‹ค.
๋งˆ์ž๋ง‰์ธ ๊ฒƒ์ฒ˜๋Ÿผ ์ฃผ์–ด์ง„ ๊ณผ์ œ์— ๋„์ „ํ•˜๋ผ.
์‚ฌ๋…์ด ๋ผ์–ด๋“ค์ง€ ์•Š๋Š” ํ•œ ์šฐ๋ฆฌ์—๊ฒŒ ์ฃผ์–ด์ง„ ๊ณผ์ œ๋Š” ์–ธ์ œ๋‚˜ ๋‹จ์ˆœํ•˜๋‹ค.



 ๋ชจ๋“  ๊ฒƒ์„ ์•Œ ํ•„์š”๋Š” ์—†๋‹ค.

" ๋ฐœ์ „ํ•˜๊ณ ์ž ํ•œ๋‹ค๋ฉด ์™ธ์ ์ธ ๋ฌธ์ œ(์žฌ๋ฌผ,ํ‰ํŒ)์— ๋ฌด๊ฐ๊ฐํ•ด์•ผ ํ•˜๊ณ  ๊ทธ ์†์—์„œ ์–ด๋ฆฌ์„์Œ์„ ๋ณผ ์ˆ˜ ์ž‡์–ด์•ผ ํ•œ๋‹ค. ๋งŽ์ด ์•Œ๊ณ  ์žˆ๋Š” ๊ฒƒ์ฒ˜๋Ÿผ ๋ณด์ด๋Š” ๊ฒƒ์„ ๊ฒฝ๊ณ„ํ•˜๋ผ. ๋ˆ„๊ตฐ๊ฐ€ ๋‹น์‹ ์„ ์ค‘์š”ํ•œ ์‚ฌ๋žŒ์œผ๋กœ ๊ฐ„์ฃผํ•œ๋‹ค๋ฉด, ์Šค์Šค๋กœ๋ฅผ ๋ถˆ์‹ ํ•˜๋ผ "

- ์—ํ”ฝํ…Œํ† ์Šค, ์—ฅ์ผ€์ด๋ฆฌ๋””์˜จ, 13a

์ž ์žฌ์  ์œ„ํ˜‘์— ๋” ์ด์ƒ ํฅ๋ถ„ํ•˜์ง€๋„ ๋ถ„๋…ธํ•˜์ง€๋„ ์•Š์œผ๋ ค๋ฉด ์–ผ๋งˆ๋‚˜ ๋” ํœด์‹์„ ์ทจํ•ด์•ผ ํ• ๊นŒ?

๋‹น์žฅ ๋ˆˆ์•ž์˜ ์ผ์— ์ง‘์ค‘ํ•˜์ž. ๋ˆˆ ์•ž์— ์žˆ๋Š” ์ผ์— ์ง‘์ค‘์„ ํ•˜๋ฉด์„œ ์ž‘์€ ์ผ๋„ ์ตœ์„ ์„ ๋‹คํ•˜์ž. ์ž”์ž”ํ•œ ํ˜ธ์ˆ˜์— ํ•œ ๋ฐฉ์šธ ํ•œ ๋ฐฉ์šธ ๋–จ์–ด์ง€๋Š” ๋ฌผ๋ฐฉ์šธ์ด ํฐ ๋ฌผ๊ฒฐ์ด ๋  ๊ฒƒ์ด๋‹ค.

 


 

 

 

DFS, BFS๋ž‘ ๋ธŒ๋ฃจํŠธํฌ์Šค ํ•˜๋Š” ๋ฐฉ๋ฒ• ์ต์ˆ™์น˜ ์•Š์•˜๋Š”๋ฐ ์—ฌ๋Ÿฌ ๋ฌธ์ œ๋ฅผ ํ’€๋‹ค๋ณด๋‹ˆ ์‹œํ—˜ 1์ฃผ์ฐจ ๋ฌธ์ œ๋“ค ์ „๋ถ€ ์™„์ „ ํƒ์ƒ‰์œผ๋กœ ํ•ด๊ฒฐํ–ˆ๊ณ , ๋‹ค์Œ ์ด๋ถ„ ํƒ์ƒ‰, ์Šคํƒ, ํ, ๋ถ„ํ•  ์ •๋ณต ๋ฌธ์ œ๋„ ๋งˆ์ฐฌ๊ฐ€์ง€๋กœ ์—ฌ๋Ÿฌ ๋ฌธ์ œ๋“ค์„ ํ’€์–ด๋ณด๋ฉด์„œ ์ผ๋‹จ ๋ฌธ์ œ์— ์ต์ˆ™ํ•ด์ ธ์•ผ ํ•  ๊ฒƒ ๊ฐ™๋‹ค.

  1. ๐Ÿ‘ฅ ์ด์ง„ ํƒ์ƒ‰
  2. ๋ธŒ๋ฃจํŠธ ํฌ์Šค ๋ฌธ์ œ ๋ฆฌ์ŠคํŠธ
'์ •๊ธ€/TIL' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [TIL] - 2023.04.28
  • [TIL] - 2023.04.18
  • [TIL] - 2023.04.09
  • [TIL] - 2023.04.03
Casteira
Casteira
ํ•  ๋ฟ
Casteira
SpongeCake
Casteira
์ „์ฒด
์˜ค๋Š˜
์–ด์ œ
  • __Main__ (104)
    • ์•Œ๊ณ ๋ฆฌ์ฆ˜ (65)
      • ๊ฐœ๋… (6)
      • ๋ฌธ์ œ (58)
    • ์ปดํ“จํ„ฐ ๊ตฌ์กฐ (9)
      • ์ž๋ฃŒ ๊ตฌ์กฐ (2)
      • OS (7)
    • ์›น (1)
      • ์ž๋ฐ” (1)
      • ์Šคํ”„๋ง (5)
      • SQL (0)
    • ๊ธฐ๋ก (4)
      • ํฌํŠธํด๋ฆฌ์˜ค (2)
    • ์ •๊ธ€ (18)
      • TIL (17)

๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

  • ๐Ÿ—’๏ธ ๊นƒํ—ˆ๋ธŒ
  • ํƒœ๊ทธ
  • ๋ฐฉ๋ช…๋ก
  • ๊ด€๋ฆฌ

๊ณต์ง€์‚ฌํ•ญ

์ธ๊ธฐ ๊ธ€

ํƒœ๊ทธ

  • ์ฝ”๋”ฉํ…Œ์ŠคํŠธ
  • springboot
  • dp
  • ๋ฐฑ์ค€ ๊ณจ๋“œ
  • annotation
  • ํฌ๋ž˜ํ”„ํ†ค
  • java
  • ํฌ๋ž˜ํ”„ํ†ค ์ •๊ธ€
  • framework
  • ๋ฐฑ์ค€
  • spring
  • ์ •๊ธ€

์ตœ๊ทผ ๋Œ“๊ธ€

์ตœ๊ทผ ๊ธ€

hELLO ยท Designed By ์ •์ƒ์šฐ.v4.2.1
Casteira
[TIL] - 2023.04.13
ํ…Œ๋งˆ์ƒ๋‹จ์œผ๋กœ

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”

๋‹จ์ถ•ํ‚ค

๋‚ด ๋ธ”๋กœ๊ทธ

๋‚ด ๋ธ”๋กœ๊ทธ - ๊ด€๋ฆฌ์ž ํ™ˆ ์ „ํ™˜
Q
Q
์ƒˆ ๊ธ€ ์“ฐ๊ธฐ
W
W

๋ธ”๋กœ๊ทธ ๊ฒŒ์‹œ๊ธ€

๊ธ€ ์ˆ˜์ • (๊ถŒํ•œ ์žˆ๋Š” ๊ฒฝ์šฐ)
E
E
๋Œ“๊ธ€ ์˜์—ญ์œผ๋กœ ์ด๋™
C
C

๋ชจ๋“  ์˜์—ญ

์ด ํŽ˜์ด์ง€์˜ URL ๋ณต์‚ฌ
S
S
๋งจ ์œ„๋กœ ์ด๋™
T
T
ํ‹ฐ์Šคํ† ๋ฆฌ ํ™ˆ ์ด๋™
H
H
๋‹จ์ถ•ํ‚ค ์•ˆ๋‚ด
Shift + /
โ‡ง + /

* ๋‹จ์ถ•ํ‚ค๋Š” ํ•œ๊ธ€/์˜๋ฌธ ๋Œ€์†Œ๋ฌธ์ž๋กœ ์ด์šฉ ๊ฐ€๋Šฅํ•˜๋ฉฐ, ํ‹ฐ์Šคํ† ๋ฆฌ ๊ธฐ๋ณธ ๋„๋ฉ”์ธ์—์„œ๋งŒ ๋™์ž‘ํ•ฉ๋‹ˆ๋‹ค.