충남대학교

컴퓨터융합학부 20학번

슈뢰딩거의 20학번 4회차

업데이트:

4회차 세부사항

모임 일자

  • 2020-07-09

모임 일시

  • 14:00 ~ 17:00 (3시간)

모임 장소

  • 각자 집

다과사진0

목표 사전 발표

  • 최민우: 백준 그래프 문제 + DP 문제 해결
  • 노채은: 생활코딩 강의 -DATABASE1, DATABASE2-MySQL 수강 BOJ에서 파이썬 2문제 이상 풀기
  • 송유찬: 백준 문제집 입출력 마무리 후 DP 할 수 있는 만큼
  • 임지은: ### 결석 ###
  • 최수빈: 컴퓨터프로그래밍1 6주차 조건문에 대한 복습(2회차), 반복문에 대한 복습 및 해당 주차 과제 2개(구구단 출력, 다이아몬드 출력) 다시 하기

공부사진0

회고

이름 클릭시 해당 회고록 블로그로 이동합니다

최민우

목표 : 백준 그래프 문제 + DP 문제 해결

최민우1

최민우2

백준의 그래프(BFS) 골드3, 골드1 문제들을 해결하려고 하였다.

실버이상부터는 구현의 문제가 아니라 알고리즘의 최적화에 더 신경 쓰게 되는 것 같다.

한문제(골드3)는 최적화에 성공하였지만, 골드1 문제인 백조의 호수는 시간초과로 해결하지 못했다

아래는 시간초과 문제를 해결하지 못한 백조의 호수 소스코드이다.

백조의 호수

import sys
from collections import deque


def bfs():
    global time_table, blank_pos, swan_pos, w, h
    bQueue = deque(blank_pos)
    current_time = 0

    # BLANK 의 이동
    while True:
        current_time += 1
        while bQueue:
            pos_x, pos_y = bQueue.popleft()
            if time_table[pos_y][pos_x] is not current_time:
                bQueue.insert(0, (pos_x, pos_y))
                break
            for dx, dy in dirs:
                if 0 <= pos_x + dx < w and 0 <= pos_y + dy < h:
                    if time_table[pos_y + dy][pos_x + dx] == 0:
                        time_table[pos_y + dy][pos_x + dx] = current_time + 1
                        bQueue.append((pos_x + dx, pos_y + dy))
        if swan_bfs(time_table, swan_pos[0], swan_pos[1]):
            return current_time


# 백조는 0이 아닌 곳을 움직일 수 있다.
def swan_bfs(table, begin, end):
    sQueue = deque([begin])
    visit = []
    while sQueue:
        pos_x, pos_y = sQueue.popleft()
        if (pos_x, pos_y) == end:
            return True
        if (pos_x, pos_y) not in visit:
            visit.append((pos_x, pos_y))
            for dx, dy in dirs:
                if 0 <= pos_x + dx < w and 0 <= pos_y + dy < h:
                    if table[pos_y + dy][pos_x + dx] != 0:
                        sQueue.append((pos_x + dx, pos_y + dy))
    return False


h, w = map(int, sys.stdin.readline().rstrip().split())
array = [list(sys.stdin.readline().rstrip()) for _ in range(h)]
time_table = [[0] * w for _ in range(h)]
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]

blank_pos = []
swan_pos = []

for y in range(h):
    for x in range(w):
        if array[y][x] == '.':
            blank_pos.append((x, y))
            time_table[y][x] = 1
        elif array[y][x] == 'L':
            swan_pos.append((x, y))
            blank_pos.append((x, y))
            time_table[y][x] = 1

print(bfs())

다음에 이 문제를 모각코 시간 중에 해결한다면 이 코드와 비교해보며 어떤 과정을 거쳐서 최적화를 이뤄냈는지 살펴보면 좋을 것 같다.

노채은

목표 : 생활코딩 강의 -DATABASE1, DATABASE2-MySQL 수강 BOJ에서 파이썬 2문제 이상 풀기

시간이 없어서 생활코딩의 DATABASE 강의는 다 수강하지 못했다.

DATABASE1에서는 Spreadsheet를 활용해서 간단하게 데이터베이스를 소개해줬기 때문에 이해하기 쉬웠다.

DATABASE2에서는 MySQL을 이용한 실습이 진행될 것이라고 했었다.

하지만 데이터베이스에 대한 기본적인 설명을 듣고 MySQL을 설치하는 과정에서 시간이 너무 많이 소요되어서 실습까지 다 수강하지는 못해 아쉬웠다.

오늘도 백준 알고리즘에서 DP 관련 문제를 풀어봤는데 알고리즘을 구현하는 사고까지 문제당 30~40분씩 걸렸다.

어쩌면 DP 문제는 점화식과 규칙성을 찾으면 쉽게 해결할 수 있다는 장점이 있지만, 그것을 찾는 것과 코드로 구현하는 것이 어려워서 난항을 겪고 있다…

모각코 활동이 아니었으면 DP문제는 건드리지도 않고 넘어갔을 것 같은데, 이번 활동을 통해서 DP 문제를 도전해보고 알고리즘적 사고를 계속해서 강화할 수 있었다.

DP문제가 끝나면 기하나 수학 관련 문제도 풀어보고 싶고 실제 코딩테스트와 유사한 문제들도 꼭 풀어보고 싶다!

송유찬

목표 : 백준 문제집 입출력 마무리 후 DP 할 수 있는 만큼

송유찬

사실 오늘 배운 내용들 중에서는 어렵다고 느낄만한 문제들이 없었다.

다만 알고리즘이 하나라도 잘못되면 오류가 뜨는 문제들이였기 때문에 오류가 뜨는 부분들을 검토해보고 다른 사람들의 코드와도 비교해보며 문제를 풀었다.

생각했던것만큼 쉽게 풀리지 않아 열받았지만 끝까지 포기하지 않아 출력문 내용을 다 마칠 수 있었다.

별 찍기는 몇 번이고 더 해도 도움이 많이 된다는 것을 느꼈다.

최수빈

목표 : 컴퓨터프로그래밍1 6주차 조건문에 대한 복습(2회차), 반복문에 대한 복습 및 해당 주차 과제 2개(구구단 출력, 다이아몬드 출력) 다시 하기

최수빈

반복문은 내가 생각하기에 서툴다고 생각하는 부분이기도 하고 코딩에서 많이 사용되는 부분이기도 한만큼 이번 복습은 더 중요하다고 생각했다.

실제로 당시의 과제를 이번에 다시 해봤을 때도 다 배운 내용이지만 버벅거리는 부분이 있었기 때문에 더욱 경각심을 가지게 되었다.

그래도 모각코를 통해 예전에는 일일이 타이핑하는 것도 염두에 두고 코드를 작성했었는데 이제는 효율과 가독성을 먼저 생각하게 되었다는 사실을 깨달아서 조금씩이지만 한 걸음씩 나아가고 있다는 것을 확실히 느낄 수 있었다.

카테고리:

업데이트:

참고