새싹프로그래머의 이야기

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

문제: 1초마다 해당 위치(X)에서 (X-1,X+1,X*2) 로 이동할 수 있을 때, 주어진 값(K) 까지 도달하는데 몇초가 걸리는지 구하는 문제입니다.

풀이 방법: BFS를 통해 문제를 해결하였습니다.

풀이 설명:

그래프 상하좌우 탐색에서 영감을 받아 해당 위치에서 이동할 수 있는 방향을 지정한 후(pos배열), 해당 점들을 방문하여 횟수를 저장하였습니다.

이때, 해당 값들에 접근하는 방식을 BFS를 통해 풀어냈습니다.

pos = [idx-1,idx+1,idx*2]

또한, queue에서 popleft()를 통해 값을 꺼내줌으로써 매 초마다 접근할 수 있는 점들을 순차적으로 탐색할 수 있게 설정하였습니다.

idx,cnt = queue.popleft()

풀이 코드:

import sys
from collections import deque

Max = 10 ** 5

n,k = map(int,sys.stdin.readline().split())

visitedCnt = [0]*(Max+1)

def bfs():
    queue = deque()
    queue.append([n,0])

    while queue:
        idx,cnt = queue.popleft()
        if(idx == k):
            print(cnt)
            break

        pos = [idx-1,idx+1,idx*2]

        for i in pos:
            if 0 <= i <= Max and not visitedCnt[i]:
                visitedCnt[i] = visitedCnt[idx] + 1
                queue.append([i,visitedCnt[i]])
bfs()

틀렸던 코드:

import sys
from collections import deque

Max = 10 ** 5

n,k = map(int,sys.stdin.readline().split())

visitedCnt = [0]*(Max)

def bfs():
    queue = deque()
    queue.append([n,0])

    while queue:
        idx,cnt = queue.popleft()
        if(idx == k):
            print(cnt)
            break

        pos = [idx-1,idx+1,idx*2]

        for i in pos:
            if 0<= i <= Max:
                visitedCnt[i] = cnt + 1
                queue.append([i,visitedCnt[i]])

bfs()

첫번째로, 최대 입력 값이 10만 이기 때문에 Max 변수에 해당 값을 저장해주었습니다.

근데, 배열 선언하는 부분에서 기초적인 실수를 했습니다. bfs함수에서 배열에 접근할 때, value = 5 라면 배열 index = 4 인 부분에 값을 저장하지 않고 index=5에 값을 저장하도록 코드를 구현하였습니다.

근데..

visitedCnt = [0]*(Max)

배열 크기를 Max+1 이 아닌 Max로 선언하여 IndexError가 발생하였습니다. value = Max 일 때, 에러가 발생한 것이죠.

정말 기초가 얼마나 중요한지 새삼 깨닫는 시간이었습니다..

또한, 방문했던 위치에 대하여 방문 여부를 확인 해주지 않아 큐에 너무 많은 값들이 담겨 '메모리 초과'가 발생하였습니다. 방문 여부 처리는 bfs의 기초라고 할 수 있는데 정답을 출력하는 것에만 매몰되어버려서 놓친 것이죠.

(즉, 매 초마다 방문할 수 있는 위치를 순차적으로 접근하기 때문에 값에 도달한 순간의 시간이 최소 값이기 때문에 방문 여부를 적용할 수 있었습니다.)

<틀렸던 코드>

for i in pos:
    if 0<= i <= Max:
        visitedCnt[i] = cnt + 1
        queue.append([i,visitedCnt[i]])

<정답 코드>

for i in pos:
    if 0 <= i <= Max and not visitedCnt[i]:
        visitedCnt[i] = visitedCnt[idx] + 1
        queue.append([i, visitedCnt[i]])

단순 bfs 문제라 생각해 엄청 간단하게 풀 수 있을줄 알았지만, 메모리 초과와 기초적인 실수들로 인한 IndexError로 인해 엄청나게 고생했던 문제입니다.(심지어 짜증마저 났던..)

하지만, 원인을 알고나서는 해당 원인을 미처 고려하지 못했던 제 부족함을 알 수 있게 되었습니다.

메모리 초과 부분은 제가 부족했던 점과 함께 별도로 좀 더 자세히 포스팅하도록 하겠습니다.

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

문제: 그림의 색상이 주어졌을 때, 적록색약인 사람과 적록 색약이 아닌 사람이 볼 수 있는 색상의 구역 수를 각각 구하는 문제 입니다.

(이때, 적록 색약인 사람은 빨강과 초록을 구분하지 못합니다.)

풀이 방법: 그래프 탐색 방법중 BFS로 문제를 풀었습니다.

풀이 설명:

문제는 총 3가지 idea에서 착안해서 풀었습니다.

1.

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

for k in range(4):
    x = i + dx[k]
    y = j + dy[k]

위 방식을 통한, 각 위치의 상하좌우 요소 탐색. (그래프 탐색 뿐만 아니라 해당 코드를 통해 간단하게 상하좌우 요소를 접근할 수 있다는 점에서 매우 유용한 코드라고 생각합니다.)

2. BFS 를 통한 그래프 탐색

3.  색약인 경우, 파란색을 기준으로 색 판별

if color != 'B' and array[x][y] != 'B':
    visited[x][y] = True
    q.append([x,y])
elif color == 'B' and array[x][y] == 'B':
    visited[x][y] = True
    q.append([x,y])

풀이 코드:

import sys
from collections import deque

sys.setrecursionlimit(10000)

n = int(sys.stdin.readline())

array = [[]*n for _ in range(n)]
for i in range(n):
    array[i] = list(sys.stdin.readline().strip())

cnt = 0
visited = [[False]*n for _ in range(n)]

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

def bfs(a,b,color):

    q = deque()
    q.append([a, b])
    visited[a][b] = True
    while q:
        i, j = q.pop()

        for k in range(4):
            x = i + dx[k]
            y = j + dy[k]

            if x < 0 or x >= n or y < 0 or y >= n or visited[x][y]:
                continue

            if color == array[x][y]:
                visited[x][y] = True
                q.append([x,y])
    return


def bfs_blind(a,b,color):

    q = deque()
    q.append([a,b])

    visited[a][b] = True
    while q:
        i,j = q.pop()
        for k in range(4):
            x = i + dx[k]
            y = j + dy[k]

            if x < 0 or x >= n or y < 0 or y >= n or visited[x][y]:
                continue

            if color != 'B' and array[x][y] != 'B':
                visited[x][y] = True
                q.append([x,y])
            elif color == 'B' and array[x][y] == 'B':
                visited[x][y] = True
                q.append([x,y])
    return



for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            bfs(i,j,array[i][j])
            cnt += 1

print(cnt,end=' ')
visited = [[False]*n for _ in range(n)]
cnt = 0
for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            bfs_blind(i,j,array[i][j])
            cnt += 1

print(cnt)

일단 BFS 탐색 코드를 2가지로 나누어 구현하였습니다.

적록 색맹이 아닌 경우, 탐색 시작점의 색과 동일한지 여부만 판단하면 되는 반면에

적록 색맹인 경우, 빨간색과 초록색을 동일한 색으로 보고 판단해야하기 때문입니다.

이제 BFS 함수 내부에서 상하좌우 요소를 접근하는데, 

if x < 0 or x >= n or y < 0 or y >= n or visited[x][y]:
    continue

해당 코드를 통해 index가 배열을 벗어나는지를 판별함과 동시에 해당 위치를 방문한적이 있는지 판별하였습니다.

마지막으로 큐와 visited 배열을 활용하여 해당 노드를 방문한적 있는지 여부를 바탕으로 구역을 탐색하였습니다.

다른 풀이:

import sys

sys.setrecursionlimit(10000)

n = int(sys.stdin.readline())

array = [[]*n for _ in range(n)]
for i in range(n):
    array[i] = list(sys.stdin.readline().strip())

cnt = 0
visited = [[False]*n for _ in range(n)]
def bfs(a,b,eyes,color):
    dx = [0,0,-1,1]
    dy = [-1,1,0,0]

    for i in range(4):
        x = a + dx[i]
        y = b + dy[i]
        if x < 0 or x >= n or y < 0 or y >=n or visited[x][y]:
            continue

        if(eyes == 'color-blindness'):
            if((color != 'B') and array[x][y] != 'B'):
                visited[x][y] = True
                bfs(x, y, eyes, color)
            elif(color == 'B' and array[x][y] =='B'):
                visited[x][y] = True
                bfs(x, y, eyes, color)
            else:
                continue


        else:
            if color == array[x][y]:
                visited[x][y] = True
                bfs(x,y,eyes,color)

    return

for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            bfs(i,j,'!color-blindness',array[i][j])
            cnt += 1

print(cnt,end=' ')
visited= [[False]*n for _ in range(n)]
cnt = 0
for i in range(n):
    for j in range(n):
        if not visited[i][j] :
            bfs(i,j,'color-blindness',array[i][j])
            cnt += 1
print(cnt)

이 코드를 통해 문제를 맞췄지만 문제를 다시 푼 이유는 다음과 같았습니다.

1. 그래프 탐색을 반복문이 아닌 재귀로 문제를 품으로써 메모리 사용량과 속도가 반복문에 비해 떨어질 것이라고 생각했습니다.

2. 함수를 호출 할 때마다, 색약의 여부에 따라 함수를 다르게 구현한 풀이 코드와 달리 색약을 판단하는 조건문이 계속적으로 동작하기 때문에 속도가 뒤떨어질 것이라고 판단했습니다.

첫번째가 풀이 코드인데요. 반복문으로 구현한 만큼 메모리는 적게 사용했지만 오히려 속도 부분에서는 느렸습니다.

반복적인 조건문의 동작과 재귀함수의 사용으로 인해 속도 부분은 확실하게 빠를 것이라 판단했지만 그렇지 않은 결과가 나와서 조금은 당황스러웠습니다.

해당 부분을 조금 더 공부한 후, 메모리와 속도 모두 효율적인 코드를 짤 수 있기 위해 노력하려고 합니다.

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

문제: 해당 그림과 같이 정삼각형의 변의 길이가 구성될 때, 입력된 N의 값에 따라 파도반 수열에 따른 P(N) 값을 구하는 문제

풀이 방법: 다이나믹 프로그래밍

풀이 설명:

주어진 수열은 다음과 같습니다.

[1,1,1,2,2,3,4,5,7,9]

이 수열을 봤을 때, P(i) = P(i-2) + P(i-3) (i >= 4)인 규칙을 발견할 수 있었습니다.

이를 바탕으로 다이나믹 프로그래밍을 통해 문제를 풀었습니다.

풀이 코드:

import sys

t = int(sys.stdin.readline())

p = [0,1,1,1] + [0] * 97

for _ in range(t):
    n = int(sys.stdin.readline())
    if n > 3:
        for i in range(3,n+1):
            p[i] = p[i-3] + p[i-2]
    print(p[n])

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

문제: 최대 힙을 통해서 입력된 값이 0일 경우에는 힙 안의 최대 값을 출력한 후 해당 값을 제거, 자연수일 경우 배열에 자연수를 넣는 연산을 수행하는 프로그램 작성하기

풀이 방법: 최소 힙인 heapq을 priority를 설정하여 최대 힙처럼 활용하기

풀이 설명:

최소 힙인 heapq를 활용하는데, 값의 입력을 (priority(-value),value) 형태로 입력하여 최대 힙으로 활용하여 문제를 해결하였다.

풀어서 설명하자면,

heapq.heappush(1)

heapq.heappush(2) 를 수행하게 되면, heapq는 [1,2]가 되어

heapq.heappop(heap)을 수행하면 1,2 순서대로 나오게 된다.

하지만 push 할 때, (-1,1) ,(-2,2) 형태로 입력하고자하는 value의 음수 값을 priority 역할로 값을 넣어 입력하게되면 

heapq는  [(-2,2),(-1,1)] 된다. 

여기서, heapq.heappop(heap)을 수행하게 되면 최대 값을 가지고 있는 (-2,2) 부터 나오게 된다.

이 원리를 통해 pop을 수행할 경우 최대 값을 담은 요소부터 나오게 되는 최대 힙을 만들어 활용하였다.

풀이 코드:

import sys
import heapq

n = int(sys.stdin.readline())
heap =[]
for _ in range(n):
    val = int(sys.stdin.readline())
    if(val == 0):
        if(len(heap) == 0):
            print(0)
        else:
            print(heapq.heappop(heap)[1])
    else:
        heapq.heappush(heap,(-val,val))

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

문제: 주어진 숫자 n을 1,2,3의 숫자 합으로 나타내는 방법의 수 출력하기

풀이방법: 동적 계획법

풀이 설명: 

각 케이스 별로 봤을 때,

<n == 1> -> 1

(1)

<n==2> -> 2

(1,1) (2)

<n==3> -> 4

(1,1,1) (1,2) (2,1) (3)

<n==4> ->  7

(1,1,1,1) (1,1,2) (1,2,1) (2,1,1) (2,2) (1,3) (3,1)

각 케이스별로 나오는 결과 값을 봤을 때, f(n) = f(n-3) + f(n-2) + f(n-1) (n >= 4) 가 성립하는 것을 찾을 수 있었습니다.

이에, 동적 프로그래밍을 통해 코드를 구현하였습니다.

풀이 코드:

import sys

n = int(sys.stdin.readline())
array = []

for _ in range(n):
    array.append(int(sys.stdin.readline()))

dp = [1,2,4]

for i in range(3,max(array)):
    dp.append(sum(dp[i-3:i]))

for i in array:
    print(dp[i-1])

<초기 코드>

처음에는 문제에서 주어진대로 풀어보려고 했습니다.

문제 설명에서 나오는 숫자들이 순열과 일치한다고 생각하여 순열로 문제를 풀어보고자 하였습니다.

주어진 숫자로 만들 수 있는 1,2,3의 조합을 구하고, 이를 itertools의 permuations를 통해 나오는 결과 값의 갯수를 세면 정답을 구할 수 있을거라고 생각했습니다.(이때, permutation함수는 (1,1,2)의 각 1을 다른 개체로 보기 때문에 중간에 set 함수를 통해 결과 값에서 중복된 값을 제거해주었습니다.)

정답인 값들은 구할 수 있었지만 연산이 너무 많이 필요해서 시간초과가 발생하였습니다.

이에 , 다른 규칙을 찾고자 했고 위의 점화식으로 표현되는 규칙을 찾을 수 있어 '다이나믹 프로그래밍'으로 문제를 해결하였습니다

import sys

import itertools

n = int(sys.stdin.readline())

array = []

for _ in range(n):
    array.append(int(sys.stdin.readline()))

for i in range(n):

    cnt = 0

    num = array[i]

    for a in range(num, -1, -1):

        for b in range((num - a) // 2, -1, -1):

            for c in range((num - a - 2 * b) // 3, -1, -1):

                numArray = []

                numArray.append(['1'] * a)

                numArray.append(['2'] * b)

                numArray.append(['3'] * c)

                numArray = list(itertools.chain.from_iterable(numArray))

                if (1 * a + 2 * b + 3 * c == num):
                    cnt += len(list(set(list(itertools.permutations(numArray, a + b + c)))))

    print(cnt)