배극곰의 IT식량창고

문제설명

여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있다.

각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다.

이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다.

따라서 개미 전사가 정찰병에서 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다.

개미 전사를 위해 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하시오.

[입력 조건]

1. 첫째 줄에 식량창고의 개수 N이 주어집니다. (3 <= N <= 100)

2. 둘째 줄에 공백을 기준으로 각 식량창고에 저장된 식량의 개수 K가 주어진다. (0 <= K <= 1,000)

[출력 조건]

첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하시오

문제풀이

D[i] 는 i번째까지의 최적의 해를 메모이제이션을 통해 저장한 것이다.

즉, 털 수 있는 식량의 최댓값이 저장됨을 의미한다.

점화식을 도출해보면,

D[i] = max(D[i-1], D[i-2]+arr[i]) 가 된다. (2<= i < N 일 경우)

코드

N = int(input())
arr = list(map(int, input().split()))
D = [0] * 1001

D[0] = arr[0]
D[1] = max(D[0], arr[1])

for i in range(2, N):
    D[i] = max(D[i-1], D[i-2] + arr[i])

print(D[N-1])

문제설명

현민이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 X 1 크기의 정사각형으로 이뤄진 N X M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다.

맵의 각 칸은 (A, B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다. 캐릭터의 움직임을 설정하기 위해 정해 놓은 매뉴얼은 이러하다.

현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다.

캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 횐전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다.

만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우에는, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단, 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우에는 움직임을 멈춘다.

현민이는 위 과정을 반복적으로 수행하면서 캐릭터의 움직임에 이상이 있는지 테스트하려고 한다. 메뉴얼에 따라 캐릭터를 이동시킨 뒤에, 캐릭터가 방문한 칸의 수를 출력하는 프로그램을 만드시오.

입력

첫째 줄에 맵의 세로 크기 N과 가로 크기 M을 공백으로 구분하여 입력한다.

(3 <= N, M <= 50)

둘째 줄에 게임 캐릭터가 있는 칸의 좌표 (A, B)와 바라보는 방햔 d가 각각 서로 공백으로 구분하여 주어진다. 방향 d의 값으로는 다음과 같이 4가지가 존재한다.

0 : 북쪽

1 : 동쪽

2 : 남쪽

3 : 서쪽

셋째 줄부터 맵이 육지인지 바다인지에 대한 정보가 주어진다. N개의 줄에 맵의 상태가 북쪽부터 남쪽 순서대로, 각 줄의 데이터는 서쪽부터 동쪽 순서대로 주어진다. 맵의 외각은 항상 바다로 되어 있다.

0 : 육지

1 : 바다

처음에 게임 캐릭터가 위치한 칸의 상태는 항상 육지이다.

출력

첫째 줄에 이동을 마친 후 캐릭터가 방문한 칸의 수를 출력한다.

입력 예시

4 4

1 1 0 // (1, 1)에 북쪽(0)을 바라보고 서 있는 캐릭터

1 1 1 1

1 0 0 1

1 1 0 1

1 1 1 1

출력 예시

3

문제풀이

별도의 알고리즘 없이 조건 잘보고 그대로 구현만 하면 된다

핵심

1. 다음 이동할 좌표를 새로운 변수에 두고, (1) 검증하는 로직과 (2) 이동하는 로직 따로 생각하기

2. rCnt(회전횟수를 세는 변수) 만들어서(네방향 모두 체크하는 것이 조건이므로) 적절하게 초기화로직, 증가 로직 배치하기

코드

N, M = map(int, input().split())
visited = [[0 for _ in range(M)] for _ in range(N)]
arr = [[0 for _ in range(M)] for _ in range(N)]
x, y, direct = map(int, input().split())
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
answer = 1
rCnt = 0

for i in range(N):
    arr[i] = list(map(int, input().split()))

def rotateToLeft():
    global direct
    if direct == 0:
        direct = 3
    else:
        direct -= 1

# 현재위치 방문
visited[x][y] = 1

# 반복
while True:
    # [1번조건] 왼쪽으로 회전 로직
    rotateToLeft()
    
    # 다음 이동할 좌표 (회전이 끝난 상태의 방향에서 이동) 
    nx = x + dx[direct]
    ny = y + dy[direct]

    # [2번 조건]
    # 다음 좌표가 범위내에 있고, 육지이며, 방문하지 않았다면
    if 0 < nx <= M and 0 < ny <= N and arr[nx][ny] == 0 and not visited[nx][ny]:
        # 이동 (현재좌표 갱신)
        x, y = nx, ny
        visited[nx][ny] = 1
        answer += 1
        rCnt = 0
    else:
        rCnt += 1
    
    # [3번 조건] 4방향 모두 가본 칸이거나, 바다로 되어있다면 뒤로 한칸 이동
    if rCnt == 4:
        nx = x - dx[direct]
        ny = y - dy[direct]
        # [3번 예외조건] 뒤쪽이 바다라면 이동안하고 멈춤 (반복종료)
        if arr[nx][ny] == 1:
            break
        x, y = nx, ny
        rCnt = 0

print(answer)

쉬운 문제였지만

한창 BFS 문제를 풀었기에

BFS로도 풀어볼 수 있지 않을까 하여 한번 풀어보었다.

그 과정에서 공부한 과정을 적는다.

N이 1이 되기까지의 각 연산과정을 그래프의 노드라고 생각하고.

BFS를 사용하면 가능한 모든 상황에 대해서 탐색을 한다. => 완전탐색

노드와 간선의 수에 따라 시간복잡도 결정.

즉, BFS로 접근하면 N의 가능한 모든값에 대해 탐색을 해야한다.

하지만, 이 문제는 N이 1이 될때까지 최적의 선택을 하는 것이 핵심이므로 그리디를 사용하자.

문제풀이

핵심

N을 1로 만들어야 하므로,
빠르게 줄이려면 -1보다는 나누기 연산이 최적의 해를 찾기에 더 적합

그리디 알고리즘
매 순간 현재의 상황에서 좋아보이는 나누기(나누어 떨어진다면)를 우선적으로 하고, 안되면 빼는 전략방식
전체 연산 횟수 최소화 (하지만 항상 보장하지는 않음.)

코드

N, K = map(int, input().split())

cnt = 0

while N > 1:
    if N % K == 0:
        N //= K
    else:
        N -= 1

    cnt += 1

print(cnt)

[백준] 1로 만들기와 다른점 

문제링크

https://www.acmicpc.net/problem/1463

이 문제에 그리디를 적용 하면 최적의 해를 구할 수 없다.
N = 10 이라고 하면
현재의 상황에서는 나누기 3을 하는게 좋아보이나, 실제로는 그렇지 않고 -1을 해야 최적의 해를 도출할 수 있으므로.

이 문제는 DP를 사용하는 것이 바람직하다.
DP를 사용하면 작은 문제의 해를 저장하고, 이를 나중에 활용하여 큰 문제의 해를 도출할 수 있다.
DP는 "메모이제이션" 개념을 활용한다.

import sys

def solution(N):
    for i in range(2, N+1):
        D[i] = D[i-1] + 1

        if i % 2 == 0:
            D[i] = min(D[i], D[i//2] + 1)
        if i % 3 == 0:
            D[i] = min(D[i], D[i//3] + 1)

    return D[N]

if __name__ == "__main__":
    input = sys.stdin.readline
    N = int(input())

    # D[i]는 주어진 규칙들로 정수 i를 1로 만드는데에 사용된 최소연산횟수
    D = [0] * (N+1)
    D[1] = 0

    print(solution(N))

튜플 - 다익스트라 최단경로 알골때 우선순위 큐 이용하는데, 우선순위 큐에 들어가는 데이터를 튜플로 구성
, 그래프 알고리즘 구현할때 자주 사용

리스트 - C++의 STL vector와 유사함.

 빈리스트 선언 : arr = list() 혹은 arr=[] (arr는 변수명이라 가정)
 인덱싱, 슬라이싱
 ★컴프리헨션 : 리스트 초기화방법  array = [i for i in range(20) if i%2==1]
    특히 2차원 배열 초기화할때 유용함
     arr = [[0]*m for _ in range(n)]

★★ 특정 크기의 2차원 리스트 초기화시엔 반드시 리스트 컴프리헨션 이용해야함

기타메서드

insert()함수를 사용하면 시간복잡도는 O(N), append()함수가 O(1)에 수행되는데에 반해 너무 느리다
★insert함수 남발하면 시간초과 날수있음
remove()또한 삭제후 리스트의 원소위치를 조정해야하므로 O(N)만큼 소요


★ 전형적이 코테 문제풀때 input()이용하지만,
input개수가 많은 경우에는 동작속도가 느려서 시간초과 날 수 있기때문에
==> sys 라이브러리 이용.

sys.stdin.readline().rstrip()

파이썬에서 지원하는 표준라이브러리

내장함수

sorted()함수는 iterable한 객체 들어왔을때, 정렬된 결과 반환

key속성으로 reverse를 활용해 정렬된 리스트 뒤집을지 여부 결정할 수 있음

sorted([8,2,4], reverse=True)        #내림차순 정렬

itertools

가장 유용하게 쓸만한 클래스는 permutations, combinations

- permutations

리스트같은 iterable한 객체에서 r개의 데이터 뽑아 일렬로 나열하는 모든경우 즉, 순열에 사용

- combinations

순서고려하지 않고 나열하는 모든 경우(조합)

from itertools import permutations

arr = ['A','B','C']
answer = list(permutations(data,3)) #모든 순열 구하기

print(result)

- 보통 파이썬에서는 deque 사용해 큐 구현