해리의 데브로그

(SW 문제해결 응용 구현 - 탐욕 알고리즘) SWEA 5203 - 베이비진 게임

10 Aug 2019 | Algorithm SWEA

문제

  • SWEA 5203 - [파이썬 S/W 문제해결 구현 3일차] 탐욕 알고리즘 - 베이비진 게임
  • 문제링크
  • 문제의 저작권은 SW Expert Academy에 있습니다.

나의 코드

TC = int(input())

for tc in range(1, TC+1):
    Data = list(map(int, input().split()))
    flag = False
    cnt = 0
    for index in range(6, 13, 2):
        result = []
        for i in range(2):
            Deck = [Data[x] for x in range(i, index,2)]
            cnt_lst = [0] * 12

            for j in range(len(Deck)):
                cnt_lst[Deck[j]] += 1

            k = 0
            Tri = Run = 0
            while k < 10:
                if cnt_lst[k] >= 3:
                    cnt_lst[k] -= 3
                    Tri += 1
                    continue

                if cnt_lst[k] >= 1 and cnt_lst[k + 1] >= 1 and cnt_lst[k + 2] >= 1:
                    cnt_lst[k] -= 1
                    cnt_lst[k + 1] -= 1
                    cnt_lst[k + 2] -= 1
                    Run += 1
                    continue
                k += 1

            cnt += 1

            if Tri > 0 or Run > 0:
                result.append(1)
            else:
                result.append(0)


        if (result[0] == 1 and result[1] == 1) or (result[0] == 2 and result[1] == 2) :
            flag = True
            print('#%d'%(tc), 1)
            break

        elif result[0] > result[1]:
            flag = True
            print('#%d'%(tc), 1)
            break

        elif result[0] < result[1]:
            flag = True
            print('#%d'%(tc), 2)
            break


    if flag:
        continue
    else:
        print('#%d'%(tc), 0)

(SW 문제해결 응용 구현 - 탐욕 알고리즘) SWEA 5202 - 화물 도크

10 Aug 2019 | Algorithm SWEA

문제

  • SWEA 5202 - [파이썬 S/W 문제해결 구현 3일차] 탐욕 알고리즘 - 화물 도크
  • 문제링크
  • 문제의 저작권은 SW Expert Academy에 있습니다.

나의 코드

TC = int(input())
for tc in range(1,TC+1):
    N = int(input())
    Data = []
    for i in range(N):
        x, y = map(int, input().split())
        Data.append([x, y])

    #정렬
    for i in range(N):
        for j in range(i, N):
            if Data[i][1] > Data[j][1]:
                Data[i], Data[j] = Data[j], Data[i]

    result = []
    visited = [0]*N
    result.append(Data[0])
    visited[0] = 1

    while True:
        #제거
        for i in range(N):
            if result[-1][-1] > Data[i][0]:
                visited[i] = 1

        if not 0 in visited:
            break

        index = 0
        value = 987654321
        for i in range(N):
            if visited[i] == 0 and result[-1][-1] <= Data[i][0] and Data[i][1] < value:
                index = i
                value = Data[i][0]

        result.append(Data[index])

    print('#%d %d'%(tc, len(result)))

(SW 문제해결 응용 구현 - 탐욕 알고리즘) SWEA 5201 - 컨테이너 운반

10 Aug 2019 | Algorithm SWEA

문제

  • SWEA 5201 - [파이썬 S/W 문제해결 구현 3일차] 탐욕 알고리즘 - 컨테이너 운반
  • 문제링크
  • 문제의 저작권은 SW Expert Academy에 있습니다.

나의 코드

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

    ans = 0
    for i in range(M):
        result = 0
        for unit_Weight in Mat_Weight:
            if Truck_Weight[i] >= unit_Weight and unit_Weight >= result:
                result = unit_Weight
        if result != 0:
            Mat_Weight.remove(result)
        ans += result

    print('#%d %d'%(tc, ans))

2019년 7월 4주차, 8월 1주차 TIL

04 Aug 2019 | TIL

7월 4주차 & 8월 1주차 TIL Summary

  • 되돌아보니 참으로 정심없이 바쁜 한주 였던 것 같다. 일요일이 되서야 TIL을 그리고 하나의 TIL으로 마무리 짓는 나 자신을 다시한번 반성한다.

  • 이번주는 프로젝트 진행 + 정보처리기사 시험 준비 + 자기소개서 작성 등을 진행하였다.

  • 우선 첫번째로, 정보처리기사 필기 시험을 오늘(8/4)에 치고왔다. 2020년부터 정보처리 기사 유형이 바뀌기전 마지막 시험이었는데, 시험 직전까지 모의고사 성적이 간당간당해서 이번주 방과후에는 내내 모의고사 풀기에 집중했던 것 같다. 생각보다 높은 점수로 마무리를 지어서 다행이라 생각이 든다.

  • 7주 간의 프로젝트가 이제 종착역으로 달리고 있다. 이렇게 긴 기간동안, 그리고 팀으로 프로젝트를 진행해본 것이 처음인데, 이번주는 특히나 여러모로 집중을 제대로 못했던 것 같다. 2번째 소 프로젝트 기간동안 너무 모든 것을 쏟으면서 오롯이 프로젝트에만 매진을 했던 것이, 돌이켜보면, 컨디션 조절에 실패한 것 같다. 오래달리기 경주에서 처음부터 전력질주룰 한 느낌이다. 체력적으로나 심적으로나 긴 프로젝트 기간동안에는 안배를 잘해야한다는 것을 정말 뼈저리게 깨닫을 수 있었다. 아무쪼록, 내일부터 다시 초심으로 돌아가 프로젝트의 유종의 미를 거둬야겠다.

  • 추가로, 하반기 준비를 드디어 시작하였다. 정말 오랜만에 자기소개서를 작성해보았는데, 역시나 너무나도 자소서 작성은 어려운것 같다… 앞으로 더욱더 하반기 준비에 많이 바빠질 것 같은데, 일정 관리를 철저히 잘해야겠다.

SWEA 1247 - 최적 경로

03 Aug 2019 | Algorithm SWEA

문제

  • SWEA 1247 - 최적 경로
  • 문제링크
  • 문제의 저작권은 SW Expert Academy에 있습니다.

나의 코드

  • 백트레킹 문제인데, 회사 & 집 거리를 추가로 고려해줘야는 문제이다.
  • 추가로 시간 단축을 위해 프루닝 조건도 넣어주었다.
  • 거리를 계산하는 변수인 sub_result를 사용하여 이전 재귀로 돌아갈 때 기존 값을 빼주는 방식으로도 코드를 작성할 수도 있으며, 혹은 간단하게, 누적 값을 인자로 넘겨서도 풀 수 있다.
def DFS(x, y):
    global result, sub_result

    if sub_result > result:
        return

    if 0 not in visited:
        sub_result += abs(x - Home_x) + abs(y - Home_y)
        if result > sub_result:
            result = sub_result
        sub_result -= abs(x - Home_x) + abs(y - Home_y)
        return


    for i in range(N):
        x1 = Clients[i][0]
        y1 = Clients[i][1]
        if not visited[i]:
            visited[i] = 1
            sub_result += abs(x-x1) + abs(y-y1)
            DFS(x1, y1)
            visited[i] = 0
            sub_result -= abs(x-x1) + abs(y-y1)


TC = int(input())
for tc in range(1, TC+1):
    N = int(input())
    Data = list(map(int, input().split()))
    Office_x, Office_y = Data[0], Data[1]
    Home_x, Home_y = Data[2], Data[3]
    # print(Data)

    Clients = []
    for i in range(2, N+2):
        x = Data[i*2]
        y = Data[i*2+1]
        Clients.append([x,y])

    print(Clients)

    visited = [0]*N
    sub_result = 0
    result = 987654321
    DFS(Office_x, Office_y)
    print('#%d %d'%(tc, result))

def DFS(x, y, cnt):
    global result

    if cnt > result:
        return

    if 0 not in visited:
        cnt += abs(x - Home_x) + abs(y - Home_y)
        if result > cnt:
            result = cnt
        return


    for i in range(N):
        x1 = Clients[i][0]
        y1 = Clients[i][1]
        if not visited[i]:
            visited[i] = 1
            temp = abs(x-x1) + abs(y-y1)
            DFS(x1, y1, cnt+temp)
            visited[i] = 0


TC = int(input())
for tc in range(1, TC+1):
    N = int(input())
    Data = list(map(int, input().split()))
    Office_x, Office_y = Data[0], Data[1]
    Home_x, Home_y = Data[2], Data[3]
    # print(Data)

    Clients = []
    for i in range(2, N+2):
        x = Data[i*2]
        y = Data[i*2+1]
        Clients.append([x,y])

    visited = [0]*N
    # cnt = 0
    result = 987654321
    DFS(Office_x, Office_y, 0)
    print('#%d %d'%(tc, result))