[자료구조] 구현

 

🚩 구현 

---

 

| 머리속에 있는 알고리즘을 정확하고 빠르게 프로그램으로 작성하기 

 

| 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제 

 

 

🐾 완전 탐색 

 

| 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 

 

 

🐾 시뮬레이션

 

| 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형 

 

 

🐾 구현시 고려해야 할 메모리 제약 사항 

 

| 변수 유형

 

• 파이썬에서 실수형 변수는 유효 숫자에 따라 연산 결과가 원하는 값이 나올 수 있지 않다는 점을 기억하자 

 

 

| 리스트 크기 - 메모리 제한 

 

• 일반적인 코딩테스트 수준에서는 메모리 사용량 제한보다 더 적은 크기의 메모리를 사용해야 한다는 점만 기억하도록 하자 

 

 

 

1️⃣  실전 유형 문제 : 상하좌우 

---

 

 

| 일련의 명령에 따라 개체를 차례대로 이동 시킴 → 시뮬레이션 유형 

 

 

| KEY IDEA : 좌표의 이동 움직임을 리스트로 표현하여 x,y 좌표 값을 바꾸어 나가는 것 (dx,dy)

 

 

# n 을 입력 받기 : nxn 
n = int(input()) 
x,y = 1,1 # (1,1)에서 시작 
plans = input().split() # 이동 계획 입력 


# L,R,U,D 에 따른 이동 방향 
# L : (x, y-1), R : (x, y+1) , U : (x-1, y) , D : (x+1,y)

dx = [0,0,-1,1]  
dy = [-1,1,0,0]
types = ['L','R','U','D'] 



# 이동 계획을 하나씩 확인 
for plan in plans : 

  # 이동 후 좌표 구하기 
  for i in range(len(types)) : # 인덱스를 통해 이동 방향에 접근 
    if plan == types[i] : 
      nx = x + dx[i] 
      ny = y + dy[i] 
  
  # 공간을 넘어가는 경우 무시 
  if nx < 1 or ny < 1 or nx > n or ny > n : 
    continue # 아래 코드를 실행하지 않고 다음 반복문으로 넘어감 
  
  x,y = nx, ny 


print(x,y)

 

 

 

 

 

2️⃣  실전 유형 문제 : 시각

---

 

 

| 가능한 경우의 수를 모두 검사 

 

 

| KEY IDEA : 시/분/초 를 문자열 자료형으로 변환하여 합친다음 3이 포함되어 있는지 체크한다. 

 

 

h = int(input()) 

count = 0 

for i in range(h+1) : 
  # 00시도 포함되니까 range(h+1) 

  for j in range(60) : 
    for k in range(60) : 
      # 매 시각 안에 3이 포함되면 카운트 증가

      if '3' in str(i) + str(j) + str(k) : 
        count+=1


print(count)

 

 

 

 

3️⃣  실전 유형 문제 : 왕실의 나이트 

---

 

| KEY IDEA : 특정한 위치에서 특정한 형태(방향)로만 이동할 수 있는 좌표평면 이동 문제 → 이동할 수 있는 방향을 직접 정의

 

# 현재 나이트의 위치 입력받기 
input_data = input() # a1 : a(열), 1(행)
row = int(input_data[1]) 
column = int(ord(input_data[0]) - int(ord('a'))) + 1 

# 나이트가 이동할 수 있는 8가지 방향 정의 
steps = [(-2,-1),(-1,-2),(1,-2),(2,-1),(2,1),(1,2),(-1,2),(-2,1)] 

# 8가지 방향에 대하여 각 위치로 이동이 가능한지 확인 
result = 0 

for step in steps : 

  # 이동하고자 하는 위치 확인 
  next_row = row + step[0] 
  next_col = column + step[1] 

  # 해당 위치로 이동이 가능하다면 카운트 증가 
  if next_row >=1 and next_row <=8 and next_col >= 1 and next_col <= 8 : 
    result +=1
  
print(result)

 

* 현재 위치를 기준으로 아래쪽과 오른쪽은 양수 값을, 위쪽과 왼쪽은 음수의 값을 대입한 결과 

 

 

* steps 변수 형태와 1번 실전유형문제에서의 dx ,dy 변수형태는 코테에서 자주 사용되니 기억하기

 

 

🗨 ord 함수 

 

• ord(문자) : 하나의 문자를 인자로 받고 해당 문자에 해당하는 유니코드 정수를 반환한다. 

 

  * ord('a') : 97을 반환

 

• chr(정수) : 하나의 정수를 인자로 받고 해당 정수에 해당하는 유니코드 문자를 반환한다.

 

  * chr(97) : 'a' 를 반환 

 

 

🗨 2차원 자료형

 

• 리스트 = [ [값,값], [값,값], [값,값] ] 

 

• 튜플 = ( (값,값), (값,값), (값,값) ) 

 

• 튜플 = ( [값, 값], [값, 값], [값, 값] )

 

• 리스트 = [ (값, 값), (값, 값), (값,값) ]