728x90

이번에 첫 해커톤에 참여를 하였다.
처음에 시작할 때는 잘 할 수 있을지 걱정되기도 하였지만 좋은 경험을 할 수 있었다.
앞으로 해커톤을 하거나 공동해커톤에 참여하는 사람들을 위해, 그리고 이 기록을 남기고 싶어 써본다.

SW 중심대학 공동해커톤 웰컴키트

지원계기

먼저 지원계기는 해커톤을 경험하기 위해서였다. 이 해커톤이 이렇게 큰 대회인 줄 알았다면 지원하지 않았을 수도 있었을 것 같다. 이 해커톤에 대해서 찾아보지도 않았고 다같이 짧은 기간 만들어낸다는 점에서 마음에 들어 지원을 했었다. 무엇보다 종강하고나서 한다는 점에서 마음에 들었던 것 같다.
그래서 교수님 메일을 통해 지원을 하였고 운 좋게도 이번에 개발자로서 참여하게 되었다.

아이디어 등록 및 팀빌딩 기간

이 해커톤은 팀을 꾸리고 아이디어를 내는 것과 달리 미리 등록을 하는 방식이었다. 아이디어 등록을 할까하다가 더 좋은 아이디어도 많고 팀을 잘 꾸릴 자신이 없어서 아이디어 등록때는 아이디어 구경을 했다. 그리고 관심있는 아이디어를 정리해 놓았고 우선순위를 정했다. 그리고 우선순위를 바탕으로 아이디어에 댓글을 달아 팀에 들어갔다.

해커톤 기간

해커톤은 3일간이라고 되어있지만 실제로는 꽉채워서 진행하지는 않았다. 공식적인 개발 시간은 첫쨋날 오후 6시~셋쨋날 오전11시까지였다. 이미 팀원모집이 끝난 팀은 2차팀빌딩 시간부터 회의를 할 수 있었다.

초반에는 완전 개발보다는 형태를 짜는데에 집중했다.
아이디어 중에 개발할 기능들을 선별했다. 아이디어는 좋았지만 API 문제 등 일부는 정보를 얻을 곳이 없거나 우선순위적으로 밀렸기 때문이다. 좀 더 좋고 도움이 될 만한 기능을 선택하였다. 이후 기능정의서와 흐름도를 작성했다.

그리고 본격적으로 개발을 시작했다. 아마 첫쨋날 저녁시간 이후부터였던 것 같다. 게더타운을 통해 음성과 화면공유로도 소통을 할 수 있었지만 파일 공유, 실시간 채팅은 슬랙으로 하는 것이 편리하고 정리가 쉬웠기 때문에 슬랙으로도 공유하였다. 개발을 할 때에는 계속 음성을 키고 안되는 부분은 소통하면서 진행했던 것 같다. 하면서 굉장히 시간이 빠르게 지나갔다. 중간에 ppt 제출을 위해 정리하기도 했지만 개발 과정에서 첫쨋날, 둘쨋날은 이렇게 보냈던 것 같다.

셋쨋날에는 개발보다는 오히려 마무리에 가까웠다. ppt 제작을 위해 기술정의서도 써야 했고 이를 바탕으로 ppt제작과 영상이 제작되었기 때문이다. 11시까지 마무리였는데 거의 시간을 다 채워서 썼다. 이후에는 평가시간이었다. 총 42개 팀이 제출을 하였는데 평가시간이 굉장히 긴 것 같지만 짧게 느껴진다. 많은 영상들을 보고 평가를 해야 하기 때문이다. 평가 이후에는 실시간 질의응답 시간이 있었다. 팀당 1명만 질의응답에 들어가기때문에 이것은 잘 모르겠다. 굉장히 질문이 날카롭다는 것만 들었다.

시상식

비대면 시상식 후 이후에 있었던 오프라인 시상식에서.

실시간 질의응답이 끝나고 나서 조금뒤에 시상식이 진행되었다. 현장에서 느끼는 시상식 분위기는 느끼지못하지만 그래도 나름 재밌게 진행되었다. 평가집계과정에서 해커톤 기간동안 있었던 특별한 일들, 혹은 후기(?)를 들을 수 있었다. 그리고나서 시상식은 굉장히 빠르게 진행되었다. 나중에 오프라인 시상식에서도 비대면으로 한번 했기에 빠르게 진행되었다. 시상식이 비대면으로 진행되어서 그 분위기를 실시간으로 팀원들과 채팅으로 느낄수 밖에 없다는 것이 아쉬웠다.

느낀 것들

위에도 나름 느낀 것들을 적었지만 느낀점을 정리해보자면 짧은 시간이지만 굉장히 놀라운 성과를 낸 것 같다는 생각이 들었다. 이것이 해커톤이구나라는 것을 느꼈다. 개발을 시작하기 전에 기능정의서, 흐름도를 작성해보는 것도 많은 도움이 되었고 이후에 이 경험을 다른 프로젝트에도 적용할 수 있었다.
내가 하고 있는 것들이 정말 맞는지에 대해서 확신이 없었는데 조금이라도 기여를 할 수있어서 좋았고 이 해커톤을 통해 생각하지도 못한 부분들에 대해서도 알 수 있었던 것 같다. 이 경험을 하지 않았다면 이러한 개발 과정에 대해서 잘 몰랐을 것이라고 생각하고 개발 분야에서 협업하는 것 등 많은 것들을 놓치고 했을 것 같다.
좋은 사람들을 만나서 재밌게 개발할 수 있었고 긴 시간 이어지는 개발로 인해 지치기도 했지만 팀원들 덕분에 좀 더 힘내서 할 수 있었다. 혼자하라고 했다면 어려웠을 것 같다. 예상밖의 좋은 결과(특별상)를 얻어서 좋았고 이 경험을 바탕으로 조금 더 높이 나아갈 수 있는 발판이 된 것 같다.

728x90
728x90

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

 

1920번: 수 찾기

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들

www.acmicpc.net

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

 

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

 

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

예제 입력
5
4 1 5 2 3
5
1 3 7 9 5
 
예제 출력
1
1
0
0
1

 

코드 및 설명
import sys
n1=sys.stdin.readline()
num1=sorted(map(int,sys.stdin.readline().split()))
n2=sys.stdin.readline()
num2=map(int,sys.stdin.readline().split())

def binary(i,num1,start,end):
    if start>end:
        return 0
    m=(start+end)//2
    if i == num1[m]:
        return 1
    elif i<num1[m]:
        return binary(i,num1,start,m-1)
    else:
        return binary(i,num1,m+1,end)
for i in num2:
    start=0
    end=len(num1)-1
    print(binary(i,num1, start,end))

일단은 이 문제는 단순한 방법으로는 풀면 시간 초과가 뜬다.

import sys로 입력 시간을 단축시켜도 마찬가지이다.

 

이 문제는 알고리즘 분류에서도 볼 수 있듯이 이분탐색으로 풀어야 한다.

특정 지점에서 해당 숫자가 큰지 작은지 분석해 탐색시간을 절반씩 줄여주는 방식이다.

이를 위해 나중에 검색해야 할 숫자는 정렬로 처리를 해주었다.

 

메인에서는 특정 숫자가 있는지 해주어야 하므로 반복문안에서 함수 호출하는 방식을 이용해주었다.

 

함수를 뜯어보자

 

일단 함수에서는 특정 숫자와 찾아봐야 하는 리스트, 시작점과 끝점이 필요하다.

모든 것을 탐색하면 오래 걸리기에 그 시간을 줄여주기 위한 작업이다.

만약 시작점이 끝점보다 크게되면 오류이므로 return 0으로 마무리를 해주어야 한다.

그리고 위치를 가운대로 맞춰준다. 여기서는 알려주는 것이 m이라는 변수이다.

 

만약 리스트 특정위치의 숫자가 찾고자 하는 숫자가 같으면 있다는 의미인 1을 반환해준다.

아니면 그 숫자가 해당 위치의 숫자보다 작으면 이제 가운데를 기준으로 앞에를 다시 호출해 비교를 해준다.

그외의 경우면 이제 가운데를 기준으로 뒷부분을 처리해주어야 한다.

가운데란 start와 end점의 가운데(중간)를 의미한다.

 

이런 방식으로 호출을 통해 반환하면 시간도 줄어들면서 빠르게 탐색이 가능하다.

728x90

'Python > Baekjoon' 카테고리의 다른 글

[Python] 백준 13305 주유소  (0) 2022.09.03
[Python] 백준 10828 스택  (0) 2022.07.29
[Python] 백준 2630 색종이 만들기  (0) 2022.07.04
[Python] 백준 1021 회전하는 큐  (0) 2022.05.28
[Python] 백준 10866 덱  (0) 2022.05.14
728x90
문제

아래 <그림 1>과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.

전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.

전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

위와 같은 규칙에 따라 잘랐을 때 <그림 3>은 <그림 1>의 종이를 처음 나눈 후의 상태를, <그림 4>는 두 번째 나눈 후의 상태를, <그림 5>는 최종적으로 만들어진 다양한 크기의 9장의 하얀색 색종이와 7장의 파란색 색종이를 보여주고 있다.

입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다.

 

출력

첫째 줄에는 잘라진 햐얀색 색종이의 개수를 출력하고, 둘째 줄에는 파란색 색종이의 개수를 출력한다.

 

입력예시
8
1 1 0 0 0 0 1 1
1 1 0 0 0 0 1 1
0 0 0 0 1 1 0 0
0 0 0 0 1 1 0 0
1 0 0 0 1 1 1 1
0 1 0 0 1 1 1 1
0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 1

 

출력예시
9
7

 

코드 및 설명
import sys
num=int(sys.stdin.readline())
paper=[list(map(int,sys.stdin.readline().split())) for _ in range(num)]

w=0
b=0

def cut(x,y,num):
    global b,w
    check=paper[x][y]
    for i in range(x,x+num):
        for j in range(y,y+num):
            if check!=paper[i][j]:
                cut(x,y,num//2)
                cut(x,y+num//2,num//2)
                cut(x+num//2,y,num//2)
                cut(x+num//2, y+num//2, num//2)
                return
    if check==0:
        w+=1
        return
    else:
        b+=1
        return
cut(0,0,num)
print(w)
print(b)

이 문제는 쿼드 트리라는 문제라고 한다.

처음에 쿼드 트리라는 것이 어떤 것인지 이해하기가 어려웠다.

쿼드 트리는 같은것 끼리 한번에 묶는 것이라고 한다.

 

입력 예시를 보면서 설명을 하자면

이렇게 8*8로 리스트가 주어지게 되면

파란것끼리는 하나로 묶어진다고 생각을 해야한다. 맨왼쪽 위에 있는 파란색 사각형이 실질 4칸이더라도 1개라고 되게 된다고 생각하면 된다. 

 

그럼 대략적으로 쿼드트리에 대해서 이해를 해보았으니 코드를 어떻게 짜야 할까?

처음이니만큼 다른사람의 코드를 통해 이해를 해보았다.

위 코드 역사 아래 링크에 있는 코드를 따라 쳤다.

 

https://developmentdiary.tistory.com/334

 

[Python]분할정복 백준 2630

 문제  https://www.acmicpc.net/problem/2630 쿼드트리 문제이다.조건이 만족되지 않을시 4개로 쪼개어 다시 푸는 방식이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29..

developmentdiary.tistory.com

 

코드에 대해서 설명을 해보자면

일단 리스트의 크기를 입력받는것과 리스트를 만드는 과정까지는 그렇게 어렵게 느껴지지 않을 것이라고 생각한다.

문제는 재귀함수로 반복하는 코드 안에서 1분위, 2분위, 3분위, 4분위로 분리하는 것이다.

그림으로 한번 보자

시작은 이렇게 시작할 것이다.

그리고 순수하게 숫자 한개로 통일되지 않았다. 그럼 쪼개주어야 한다.

이렇게 나눠졌다.

여기서 4분위 수는 순수하게 나누어진것을 확인할 수 있다.

그리고 1로만 이루어져있으므로 b에 값이 한개 올라가게 된다. 그리고 4분위 자리는 더이상 작업이 필요없다.

나머지에 대해 또다시 작업을 해보자

각각 작업을 하기 때문에 여러번 해야 하지만 편의를 위해 1,2, 3분위를 다 나눈 모습으로 표현했다.

이렇게 되면 1분위는 b가 2개, w가 2개가 생성되었고 2분위에는 b가 1개, w가 3개가 되었다.

3분위 수는? 4칸 중 1개가 순수하지 않다. 그러면 재귀로 불러올 것이다. 나머지는 w가 2개, b가 1개로 이루어져있다.

이렇게 된다면 추가로 b가 2개, w가 2개로 만들어졌다.

 

이 과정에서 b, w를 모두 더한다면 최종적으로 흰색, 파란색 색종이의 수가 나오게 될 것이다.

 

이렇게 여러번 불러오는 코드와 return을 통해 해주게 되면 코드가 완성이 된다. 

이 문제를 풀면서 쿼드 트리에 대한 이해와 재귀에 대해서 안다면 풀기 쉬울 수도 있을 것 같다는 생각이 들었다.

728x90

'Python > Baekjoon' 카테고리의 다른 글

[Python] 백준 10828 스택  (0) 2022.07.29
[Python] 백준 1920 수찾기  (0) 2022.07.07
[Python] 백준 1021 회전하는 큐  (0) 2022.05.28
[Python] 백준 10866 덱  (0) 2022.05.14
[Python] 백준 9375 패션왕 신혜빈  (0) 2022.05.10

+ Recent posts