문제

• SWEA 4831 - [파이썬 S/W 문제해결 기본 1일차] LIST1 - 전기버스
• 문제링크
• 문제의 저작권은 SW Expert Academy에 있습니다.

나의 코드

TC = int(input())
for tc in range(1, TC+1):
    K,N,M = map(int,input().split())
    station = list(map(int, input().split()))
    station_lst = [0] * (N+1)

    for i in range(len(station)):
        station_lst[station[i]] += 1

    start = 0
    end = K
    cnt = 0

    while True:
        zero = 0
        for i in range(start+1, end+1):
            if station_lst[i] == 1:
                start = i
            else:
                zero += 1

        if zero == K:
            cnt = 0
            break

        cnt += 1
        end = start + K

        if end >= N:
            break

    print('#%s %d'%(tc, cnt))

문제

• SWEA 5105 - [파이썬 S/W 문제해결 기본 1일차] LIST1 - min max
• 문제링크
• 문제의 저작권은 SW Expert Academy에 있습니다.

나의 코드

• min 과 max 내장함수를 사용하지 않고 함수를 구현하여 문제를 풀었음.

def get_max(init_num):
    my_max = init_num[0]
    for i in range(1, len(init_num)):
        if my_max < init_num[i]:
            my_max = init_num[i]

    return my_max

def get_min(init_num):
    my_min = init_num[0]
    for i in range(1,len(init_num)):
        if my_min > init_num[i]:
            my_min = init_num[i]

    return my_min

TC = int(input())
for tc in range(1, TC+1):
    N = int(input())
    init_num = list(map(int, input().split()))
    result = get_max(init_num) - get_min(init_num)
    print(f'#{tc} {result}')

• 오늘 교육의 메인 주제는 BFS와 Queue 였다. BFS에 대한 전반적인 코드 작성은 DFS와 거의 유사하였는데, 말그대로 깊이 탐색이 아니라 너비 탐색일 뿐 만아니라, 재귀를 사용하지 않고, Queue와 FIFO(First-in, First-out) 구조를 사용한다는 것을 알게되었다.

• 알고리즘 유형에 따라 DFS와 BFS를 잘 활용하면 많은 문제를 푸는데 도움이 될 것 같다. 특히 BFS에서 distance라는 개념을 사용한 것이 매우 흥미로웠다. 횟수나 최단거리 등을 구하는 문제에 많이 유용할 것 같은데, DFS와 BFS 복습과 개념이해를 철저히 해야겠다.

• Stack과 Queue는 일반적으로 0으로된 리스트 배열을 만들어 stack의 경우 top을, Queue의 경우 front와 rear값을 변경하여 값을 넣고 빼는데, 파이썬은 pop 과 append 라는 내장함수가 있어서 Stack 과 Queue의 자료구조를 다소 수월하게 이해 할 수 있었다. 나중에 시간을 따로 내서 pop과 append 를 사용하지 않고 코드를 짜는 연습도 해봐야겠다.

• 알고리즘 수업이 시작된지 1주일이 조금 넘었다.(오늘이 8일차다!). 아침부터 저녁까지 알고리즘으로만 Intensive하게 진행되고 있는데, 정렬, 스택, DFS, 백트레킹 등 까지 하루가 다르게 새로운 개념들을 배우고 있다. 게다가 관련 문제들을 많이 풀다보니 수업 후 개념을 이해하고 복습하는데 매진을 하고 있는 상황이다.

• 덕분에 개인적으로 계획했던 추가 공부나 마크다운 정리를 하여 블로그에 업로드하는 시간이 많이 부족해졌는데, 3.1절 공휴일로 인해 꽤나 길어진 주말을 이용해서 꼭 정리를 해야겠다.

• 소프트웨어 교육을 들으면서 많이 느낀 점은 이쪽의 공부가 영어와 매우 유사하다는 것이다. 영어를 배우는 걸 흔히들 계단으로 많이 비유하는데, 공부를 열심히 한다고 가시적인 결과가 바로바로 드러나진 않지만, 꾸준한 노력과 시간을 투자하다보면, 계단을 오르듯이 한 단계 더 성장한 모습을 볼 수 있기 때문이다. 처음 교육을 들을 때만 해도 백준이나 SWEA에서 가장 쉬운문제도 어려워 헤맸었는데, 지금의 나의 기준으로 상당한 난이도의 문제를 꾸역꾸역 풀고있는 걸 보면 참 신기한 것 같다.

• 오늘 백트레킹을 배우면서 그전에 배웠던 DFS와 무슨 차이점이 있는지 처음엔 이해가 잘 되지 않았다. 곰곰히 생각해보니 백트레킹과 DFS는 유사하지만 아래의 차이점이 있다는 것을 알게되었다.

  • DFS: 완전 탐색을 기반으로 하는 일종의 자료구조
  • 백트레킹: DFS를 기반의 알고리즘으로, 가지치기를 통해 불필요한 탐색을 제거할 수 있음

문제

• 1부터 N까지의 수로 이루어진 순열이 있다. 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.
• 사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.
• N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.
  • 1, 2, 3
  • 1, 3, 2
  • 2, 1, 3
  • 2, 3, 1
  • 3, 1, 2
  • 3, 2, 1

나의 코드

• 다음 순열의 핵심은 N개의 숫자 중 N-1과 N 을 비교하여 N-1 < N 인 위치를 저장하는 것이다.
• 이후, N-1을 candidate 1 으로 저장한 후, 뒤에서부터 N-1보다 큰 숫자를 찾아 candidate2로 저장.
• cand1과 cand2의 자리를 바꾼 후, cand1 이후의 숫자를 뒤집어주면 된다.
• N-1 < N 이 없는 경우, 즉 첫번째 숫자가 가장 큰 경우는 다음 순열이 없는 경우이다.

Data = list(map(int, input().split()))
N = len(Data)

cand1 = 0
for i in range(N-1):
    if Data[i] < Data[i+1]:
        cand1 = i

cand2 = N-1
while True:
    cand2 -=1
    if Data[cand1] > Data[cand2]:
        break

Data[cand1], Data[cand2] = Data[cand2], Data[cand1]
Data[cand1+1:] = Data[:cand1:-1]


if cand1 == 0:
    print("다음 순열이 없습니다")
else:
    print(Data)