kbj110

문제 출처

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

문제

입력

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

풀이

import sys
input = sys.stdin.readline

N, M, V = map(int, input().split())

graph_matrix = [[0]*(N+1) for _ in range(N+1)]

for _ in range(M): # 간선의 개수만큼 반복하여 데이터를 입력받음
    a, b = map(int,input().split())
    graph_matrix[a][b] = 1
    graph_matrix[b][a] = 1 # 양방향으로 연결

is_visited_dfs = [0]*(N+1) # DFS 방문 체크
is_visited_bfs = [0]*(N+1) # BFS 방문 체크

def dfs(V):
    is_visited_dfs[V] = 1
    print(V, end=' ')
    for i in range(1, N+1):
        if graph_matrix[V][i] == 1 and is_visited_dfs[i] == 0: # 연결되어 있고 방문하지 않았다면
            dfs(i)

def bfs(V):
    queue = [V]
    is_visited_bfs[V] = 1
    while queue:
        V = queue.pop(0) # 큐에서 첫 번째 요소 제거
        print(V, end=' ')
        for i in range(1, N+1):
            if is_visited_bfs[i] == 0 and graph_matrix[V][i] == 1: # 연결되어 있고 방문하지 않았다면
                queue.append(i)
                is_visited_bfs[i] = 1

dfs(V)
print()  # DFS 결과 출력 후 줄바꿈
bfs(V)

해설

DFS

- 이름부터 Depth-First Search로 깊이 우선 탐색 알고리즘이다.

한 노드에서 부터 시작하여 탐색을 진행할 때, 진입한 지점에서 더 깊이 먼저 들어가는 것이다.

주로 그래프 풀이서 visited에 대한 list를 만들어두고 이 지점을 방문했었는가 ? 여부를 판별한다.

BFS

- Breadth-First Search로 탐색을 할 때, 너비를 우선으로 탐색한다.

개인적으로 구현 난이도는 DFS보다는 조금 더 어렵지 않나 생각한다.

예시를 들면, 한 학생이 수학 / 물리 / 영어를 공부한다고 하자.

그 학생이 수학 기초부터 -> 수학 박사과정 공부, 물리 기초부터 -> 물리 박사과정 공부, 영어 기초부터 -> 영어 박사과정 공부 순으로 공부하면 DFS이고, 수학 물리 영어 기초 -> 수학 물리 영어 심화 와 같이 공부를 하면 BFS이다.

bfs에서는 queue를 만들어 나와 동급 라인에 있는 애들이 누구인지를 저장해둔다. 하나씩 탐색 후 queue가 empty가 되면 (동급 라인 애들을 다 서칭하면) 끝난다.

문제 출처

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

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

입력

출력

풀이

유명한 냅색(KnapSack) 문제로 DP에 속한다.

DP는 Dynamic Programming으로 큰 문제를 작은 문제로 나눠푸는 알고리즘이다.

다음과 같은 input이 있을 때,

4 7
6 13
4 8
3 6
5 12

4개의 물품, 7의 무게를 의미하는 첫 행을 제외하면 다음과 같은 표로 변환할 수 있다.

다음 표가 의미하는 다음과 같다.

1. [6,13]행부터 K만큼 들었을 때 최대 가치를 의미한다. 첫 행에선 6 무게의 물품밖에 없기에 6과 7에 해당하는 최대 value는 13이다.

2. 그 아래 [4,8]의 물건이 추가가 되며 K=4~5일때는 4를 챙겼을 때의 무게인 8, K=6~7일때는 6의 물건을 챙겼을 때의 무게이다.

3. 그 아래 [3,6]의 물건까지 추가가 된다면 나머지는 이전과 동일하지만 K=7에서 13이 아닌 14가 된다. 이 부분이 가장 중요한데, 7(K)-3(W)에 해당하는 지점 + 6(New V)와 이전에 채워져있던 값 중 Maximum 값을 택한다.

(사실 맨 처음 생각했을때는 iteration을 돌며 확인하면 되는 것이 아닌가. 혹은 Brutal Force로 확인하면 되는 것이 아닌가 생각을 했었지만, 결국 어떤 한 물건을 기준으로 생각했을 때 최대 효용 case에 그 물건이 들어가거나 / 안 들어가거나 둘 중 하나다. 이 아이디어를 극대화 한 것 같다. 또한, 생각을 조금만 깊게 해보면 처음 주어진 Input의 순서는 상관 없다는 것을 알 수 있다.)

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
# 여기까진 input 대신 sys.stdin.readline 사용 (시간 초과 나지 않기 위해서)

bag = [list(map(int, input().split())) for _ in range(N)]
#가방에 [W,V]의 형태로 물건들을 담아준다

dp = [[0]*(K+1) for _ in range(N+1)]
#빈 N+1 by K+1 Matrix를 만들어준다.


for i in range(N+1): #물건을 하나 하나 돌며 확인
    for j in range(K+1): #그럼 k value를 하나 하나 돌며 확인한다.
        if j >= bag[i-1][0]: #만약 i번째 물건의 무게가 j(현재 가방에 넣을 무게)보다 작다면 ? 들어갈 가능성이 생긴다.
            dp[i][j] = max(bag[i-1][1]+dp[i-1][j-bag[i-1][0]],dp[i-1][j]) #이때 이전의 최댓값과 현재 만들 수 있는 최대를 비교하여 더 큰 값으로 변경한다.
        else: #나머지는 물건의 무게가 더 무거워 집어 넣지 못하는 경우이다.
             dp[i][j] = dp[i-1][j] #이는 이전에 받은 최댓값을 그대로 받는다.
        
print(dp[N][K]) #그러면 이게 최대다.

한줄평 : dp는 참 끝이 없는 것 같다.

문제 출처

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

문제

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.

자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.

1차 풀이

N = int(input())

len_n = len(f"{N}")
start = N-9*len_n

if start <= 0:
    start = 1

for i in range(start, N):
    if i == N-1:
        print(0)
    else:
        digit_sum = sum(int(digit) for digit in f"{i}")
        if i + digit_sum == N:
            print(i)
            break

N의 생성자의 하한을 어느정도 잡아준다.

해당 하한부터 Brutal하게 모든 경우를 check하며 올라간다.

근데 98%에서 틀렸다.

수정 풀이

예외처리 및 for-loop의 범위를 조정하였다.

N = int(input())

len_n = len(f"{N}")
start = N-9*len_n

if start <= 0:
    start = 1

for i in range(start, N+1):
    if N == 1:
        print(0)
        break
    if i == N:
        print(0)
    else:
        digit_sum = sum(int(digit) for digit in f"{i}")
        if i + digit_sum == N:
            print(i)
            break

문제 출처

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

문제

선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.

함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.

함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다.

배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.

1차 풀이

테스트용 및 1차 작성 답안

import sys
input = sys.stdin.readline

T = int(input()) # # of Test Case 받아주고

for _ in range(T):
    function_list = list(input())  #input은 str로 받아지니 list만 씌워도 각 element로 분해, 혹시 모르니 input -> str로 확실히 변환
    list_len = int(input())  # 사실 쓸모없긴한데 주니 일단 받자
    number_list = eval(input())

    for i in function_list:
        print(number_list)
        print(i)
        if i == 'R':
            number_list = list(reversed(number_list))
            print('Im R')
        elif i == 'D':
            print('Im D')
            if len(number_list) == 0:  #list의 empty 판정으로 인한 에러를 bool을 이용하거나 try구문을 이용해도 될 듯
                print("error")
                break
            else:
                number_list.pop(0)
    print(number_list)

python에서는 input()을 받았을 때, string type으로 받아지므로 해당 값을 list, 혹은 integer로 명시적 변환

eval 함수

python의 built-in 함수이며 정말 편리하지만, 위험한 함수.

대부분의 구분을 분석하여 자동적으로 처리해주는 유연한 함수이지만 그만큼 python 자체적인 해석에 의존함으로

strip과 같은 방식으로 처리하여주는 것이 더 안전하긴 함.

위 코드는 "시간 초과" 발생

시간 초과의 발생 가능성이 있는 항목은

• input
• list를 reverse 하는 과정

등 이 있지만

해당 코드에서는 input 대신 sys.stdin.readline을 사용하였기에 input에서의 시간 초과라고 보기 힘듦.

'list를 reverse 하는 과정'에서 시간 초과가 발생했다면 해당 과정을 최소화 하는 방향으로 다시 짜보자.

보완 방향

1. RR이 짝수개 나온 경우 원래의 순서 그대로임으로 해당 작업 미 실행

2. function_list의 구문을 해석하여 원래의 number_list에서 양쪽 끝에서 각 x, y개 제거 및 reverse 작업 0회 or 1회 실행

순서대로 해보자.

1의 방법을 구현하던 도중 iteration을 도는 과정에서 RR의 짝수개를 처리하는 것이 아닌, function_list 자체에 대해 먼저 정리를 해두고 refine된 function_list를 돌리는 것이 더 효율적이라 판단.

보완코드

def refine_func(fun_list):
    for i in range(len(fun_list)-1):
        if fun_list[i] == 'P':
            continue
        if fun_list[i] != 'R':
            continue
        elif fun_list[i] == 'R':
            if fun_list[i+1] == 'R':
                fun_list[i]='P'
                fun_list[i+1]='P'
                continue
        else:
            print("?")
            

#뒤쪽의 main for-loop내의 코드 변환
for i in function_list:
        if i == 'P':
            continue
        if i == 'R':
            number_list = list(reversed(number_list))
        elif i == 'D':
            if len(number_list) == 0:  #list의 empty 판정으로 인한 에러를 bool을 이용하거나 try구문을 이용해도 될 듯 ?
                print("error")
                break
            else:
                number_list.pop(0)

해당 함수는 function_list를 받았을 때, 짝수개의 연속된 R에 대해서는 P로 변환한다.

R자체를 제거하면 좋긴하지만, iteration에서 list의 index를 참조하기에 삭제하는 방향으로는 힘들 것 같았다.

다만, 위 보완코드를 사용한 답안 또한 시간 초과

2번 방법

Reverse를 0번 혹은 1번만 실행하며 list의 좌, 우측에서 각각 몇번 pop 해야하는지 구한 후 실행

2차 수정 풀이

#최종 5430

import sys
input = sys.stdin.readline

def refine_func(fun_list):
    for i in range(len(fun_list)-1):
        if fun_list[i] == 'P':
            continue
        if fun_list[i] != 'R':
            continue
        elif fun_list[i] == 'R':
            if fun_list[i+1] == 'R':
                fun_list[i]='P'
                fun_list[i+1]='P'
                continue

T = int(input()) # # of Test Case 받아주고

for _ in range(T):
    function_list = list(input())  #input은 str로 받아지니 list만 씌워도 각 element로 분해, 혹시 모르니 input -> str로 확실히 변환
    list_len = int(input())  # 사실 쓸모없긴한데 주니 일단 받자
    number_list = eval(input())

    refine_func(function_list)

    check_li = [0,0]
    reverse_cnt = 0
    del_cnt = 0
    
    for command in function_list:
        if command == 'P':
            continue
        elif command == 'R':
            check_li.reverse()
            reverse_cnt += 1
        elif command == 'D':
            check_li[0] += 1
            del_cnt += 1

    if del_cnt > list_len:
        print("error")
        continue

    if reverse_cnt%2 ==0:
        pass
    elif reverse_cnt%2 ==1:
        check_li.reverse()
        left_del, right_del = check_li[0], check_li[1]
        for _ in range(right_del):
            del number_list[-1]
        for _ in range(left_del):
            del number_list[0]

    print(number_list)

이번엔 출력 초과 발생. 또한 16%에서 걸리는 거 보니 해당 test case에 뭐가 있는 듯.