입 달린 감자의 코딩 블로그

자 우리는 자료구조를 공부하고 있는 것이 아니라 알고리즘을 공부하는 것이니 간단하게 설명만 하고 넘어가자.

스택

후입선출 (Last In First Out)

나중에 들어온 것이 먼저 나간다. 나 같은 경우 프링글스의 감자칩에 비유한다.

# 스택
# 후입선출(Last In First Out)
# 나중에 들어온 것이 먼저 나감(나는 프링글스의 감자칩에 비유함)

# 삽입(5), 삽입(2), 삽입(3), 삽입(7), 삭제(), 삽입(1), 삽입(4), 삭제()
stack=[]
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack)

큐

선입선출(First In First Out)

먼저 들어온 것이 먼저 나간다. 나 같은 경우 사람들이 줄서는 것에 비유한다.

# 큐
# 선입선출(First In First Out)
# 나는 줄 서는 것에 비유한다.

# 삽입(5), 삽입(2), 삽입(3), 삽입(7), 삭제(), 삽입(1), 삽입(4), 삭제()

from collections import deque

queue = deque()

queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue)

재귀함수

자기 자신을 다시 호출하는 함수

재귀함수의 대표적인 예제인 팩토리얼을 구현해보았다.

# 재귀 함수
# 자기 자신을 다시 호출하는 함수

# 팩토리얼 예제
def factorial(n):
    if n <= 1:
        return 1
    else:
        return n*factorial(n-1)

print(factorial(5))

DFS

깊이 우선 탐색으로 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

def dfs(graph,v,visited):
    visited[v]=True
    print(v,end=' ')
    for i in graph[v]:
        if not visited[i]:
            dfs(graph,i,visited)

BFS

너비 우선 탐색으로 가까운 노드부터 탐색하는 알고리즘이다.

from collections import deque

def bfs(graph,start,visited):
    queue=deque([start])
    visited[start] = True
    while queue:
        v=queue.popleft
        print(v,end=' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

문제

8 x 8 좌표 평면의 체스판이 있고 나이트는 L자 형태로만 이동할 수 있고 체스판 밖을 벗어나지 못한다. 이 때 경우는 2가지로

1. 수평으로 두 칸 이동한 뒤에 수직으로 이동하기

2. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기

체스판의 행은 1 ~ 8, 열은 a ~ h로 표기했을 때 입력받은 위치에서 이동가능한 경우의 수를 출력하세요.

예시

입력

a1

출력

2

정답

# 현재 나이트의 위치 입력받기
data =input()
row=int(data[1])
column=int(ord(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_column=column+step[1]
    # 해당 위치로 이동이 가능하다면 카운트 증가
    if next_row>=1 and next_row <=8 and next_column>=1 and next_column<=8:
        result +=1

print(result)

내가 시도를 해봤는데 잘 구현이 되지 않아 바로 정답코드 올린다...

문제

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오.

입력 예시

입력

5

출력

11475

코드

n=int(input())

count=0

for i in range(0,n+1):
    for j in range(0,60):
        for k in range(0,60):
            if '3' in str(i) + str(j)+ str(k):
                count +=1

print(count)

워낙 간단하고 책풀이와 내 풀이가 비슷해서 하나만 올린다.

구현이란?

머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다.

문제

여행가 A는 N x N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 x 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1,1)이며, 가장 오른쪽 아래 좌표는 (N,N)에 해당한다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1,1)이다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있다.

L : 왼쪽으로 한칸, R: 오른쪽으로, U: 위로, D 아래로

첫째줄에는 N을 입력받고 둘째줄에는 방향을 입력받는다.

입력 예시

5

R R R U D D

출력

3 4

내 풀이

n = int(input())

dir = list(map(str,input().split()))

x=1
y=1

for i in dir:
    if i=='R' and y!=n:
        y+=1
    elif i=='L' and y!=1:
        y-=1
    elif i=='U' and x!=1:
        x-=1
    elif i=='D' and x!=n:
        x+=1

print(x,y)

나는 단순하게 입력받은 방향에 따라 사각형 끝의 조건을 추가하여 구현했다.

책 풀이

n=int(input())
x,y=1,1
plans=input().split()

# L,R,U,D에 따른 이동 방향
dx=[0,0,-1,1]
dy=[-1,1,0,0]
move_type=['L','R','U','D']

# 이동 계획을 하나씩 확인
for plan in plans:
    # 이동 후 좌표 구하기
    for i in range(len(move_type)):
        if plan == move_type[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)

이게 정석적인 풀이이다. 다른 문제를 접했을 때 이게 무슨 소리인가 했는데 이러한 풀이 방식을 많이 쓰더라. 이 정도는 이해하며 암기해두자.

문제

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선책하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.

1. N에서 1을 뺀다.

2. N을 K로 나눈다.

예제 입력

입력

17 4

출력

3

입력

25 5

출력

2

내 풀이

n,k=map(int,input().split())

count =0

while n!=1:
    if n%k==0:
        n=n/k
    else:
        n=n-1
    count +=1

print(count)

단순하게 생각해서 1씩 줄여가며 나눠떨어지면 나누고 나누어 떨어지지 않으면 -1을 해주는 식으로 코드를 구현했다.

역시 책에서는 단순하게 푸는 방식이라고 소개되어있다. 비효율적인 방식이란다... 아직 나는 멀었다.

책 풀이

n,k=map(int,input().split())

result =0

while True:
    # (n==k로 나누어떨어지는 수)가 될 때까지 1씩 빼기
    target=(n//k)*k
    result+=(n-target)
    n=target
    # n이 k보다 작을 때(더 이상 나눌 수 없을 때) 반복문 탈출
    if n<k:
        break
    result +=1
    n//=k

result+=(n-1)
print(result)

크게 배울점은

    target=(n//k)*k
    result+=(n-target)
    n=target

이 부분인 것 같다. 나는 한번 연산할 때마다 1번 시행되어 비효율적이었다면

이 코드에서 나눠떨어지는 숫자까지 한번의 연산으로 진행되어 효율적인 코드가 구현된다. 

자 오늘은 그리디 알고리즘 중 숫자 카드 게임을 풀어보자.

문제

숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다.

1. 숫자가 쓰인 카드들이 N x M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은ㅇ 열의 개수이다.

2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.

3. 그 다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.

4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세운다.

문제가 장황하다. 요약하자면 각 행마다 가장 작은 값을 뽑고 그 값들 중 가장 큰 값을 출력하면 된다.

입력 예시

입력

3 3

3 1 2

4 1 4

2 2 2

출력

2

입력

2 4

7 3 1 8

3 3 3 4

출력

3

내가 푼 풀이

# 숫자 카드 게임

n,m = map(int,input().split())  # n은 행, m은 열의 개수

result = 0

for i in range(n):
    data = list(map(int,input().split()))
    if result < min(data):
        result = min(data)
print(result)

각 행마다 가장 작은 값을 뽑고 그 값들 중 가장 큰 값을 출력하면 된다. 반복문을 통해 입력을 받고 행마다 가장 작은 값을 result 로 저장하고 다음 result 값과 비교하여 더 큰 값을 저장하도록 코드를 짜봤다.

책 정답 풀이

n,m = map(int,input().split())  # n은 행, m은 열의 개수

result=0
for i in range(n):
    data=list(map(int,input().split()))
    min_value = 10001
    for a in data:
        min_value=min(min_value,a)
    result=max(result,min_value)

print(result)

정답과 비슷한 맥락인 것 같다.