러닝머신 하는 K-공대생

개학 전날까지 너무 달리기만 했는데 잠시 나를 돌아보는 시간과 휴식이 필요할 것 같아 오랫만에 글을 써본다. 가끔 이런 시간을 가지고나면 다시 열심히 달릴 생각에 두근댄다. 하지만 쓰고 보니 뻘글같다 헤헿ㅎㅎ 작년인 과학고 1학년 때, 과학고라는 낯선 환경에 새롭게 적응해야 한다는 점이 힘들었던 것 같다(지금보면 별거없다). 기숙사 환경에 어떻게 적응해야 할지, 동아리는 무엇을 하며, 연구는 또 어떤 것을 해야하며, 앞으로 깊게 공부하고 싶은거는 뭐고, 친구들이랑은 어떻게 지낼지, 대학은 어디를 가야할지, 성적관리는 어떻게 해야하고, 조기졸업(하지만 어림도 없지), 하고 싶은 활동과 내신 비중은 어떻게 해야하는지, 내가 이 학교에서 어떤 사람으로 성장하고 싶은지 고민을 많이 했었고 지금도 하고있다. 그래..

2021년에 새롭게 시작해보고 싶은 것 중 내신 공부 균형있게 하기, PS 틈틈히 공부하기에 이어 바로 캐글(kaggle)이 있었다. 평소 머신러닝이나 딥러닝 분야에 관심이 많아 지금까지 앤드류 응님의 코세라 강의, 모두의 딥러닝 강의, CS231등을 수강하면서 여러 머신러닝 입문책을 보면서 머신러닝 모델, 데이터 처리등에 대해 배웠다. 이과정에서 캔위성 프로젝트에서 Semantic Segmentation을 구현하고, 현재 진행중인 R&E에서도 Weakly-Supervised Semantic Segmentation, CNN, YOLO등을 적용해보는 시도를 하고 있다. 하지만 이때 직접 데이터를 수집하고 라벨링이나 어노테이션을 하는 과정은 시간이 많이 걸리기도하고 사실은 연구나 공부보다는 본격 노가다(?!..

1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제자체가 매우 간단해보여서 리스트를 이용해 정렬한 후 중간값을 출력했는데 시간초과가 떴다. 정렬을 하는데 O(nlogn) 걸리고 이를 N번 반복한다고 하면 대충봐도 O(N^2)은 가뿐히 넘긴다. 여기서 N이 1보다 크거나 같고, 100,000보다 작거나 같으므로 시간초과가 뜨는 것은 당연하다. 따라서 매 입력이 들어올 때마다 O(nlogn) 보다 작은 시간복잡도를 가지는 방법으로 중간값을 찾아야 한다. 전혀 시간복잡도를 줄일 방법이 떠오르지 않..

12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 일단 DP로 풀 수 있을 것 같아서 점화식부터 세우려고 시도했다. D(i,k)를 i번째 인덱스 이후 중, k이하의 무게 중 가치의 합의 최댓값 으로 두고서 생각을 했다. 보통 조합론적 증명을 할 때 처럼 자신을 포함시킬 때와 포함하지 않을 때 경우를 나누어 V[i] 를 i번째 인덱스의 가치, W[i]를 i번째 인덱스의 무게라고 했을 때 i번째와 i+1번째 관계를 이끌어냈다. 일단 점화식을 유도하긴 ..

아직 문제풀이 경험이 적어서 이진탐색 문제를 풀 때마다 매번 부등호의 등호를 결정하는 것이 헷갈린다. 이진탐색 관련 문제 풀이 경험을 늘려 이 점을 극복해야겠다 (혹시 이진탐색을 할 때 부등호 등호와 출력값을 정하는 팁이 있다면 댓글로 공유 부탁드립니다.!) 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 1에서부터 최대랜선길이를 각각 start,end로 시작해서 각 wire의 길이를 mid로 나눈 값의 합을 cnt라고 하였다. 아래 그림에서 보라색 영역은 가능한 랜선의 길이이며 ..

16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 같은 색으로 이루어진 사이클을 찾는 과정은 간단하다. 같은 색으로 이루어진 공간만을 이동하면서 탐색을 진행하는데 만약 이동하려는 공간이 바로 전 depth에서 탐색한 노드가 아니고(다시 돌아가는 경우) 이전에 방문했었더라면 사이클을 만들 수 있다. 아래 코드에서 recur[]은 탐색하고자 하는 색에서 방문할 때마다 현재의 탐색깊이를 저장한 것이며 recur를 통해 이전에 방문했는지, 바로 이전에 탐색한 곳인지를 확인하고 모든 칸에서 DFS를 진행하는 방식..

작년 홍보자료 내용을 활용해 2021 PASS 홍보자료를 만들었다. 작년에 코로나 상황때문에 메이킹을 마무리 못하고 끝낸것이 아쉬웠는데 올해는 세미나,메이킹 시간 분배를 잘해서 드론이나 rc비행기 하나는 완성해보고 싶다. 사실 1학년 때 SADA와 해동까지 들어간 상태에서 미쳐 PASS 안하면 후회할 것 같아서 지원했었는데 SADA기장에 이어 PASS 부기장을 맡게되었다. 처음에 난 그냥 정보나 수학쪽만 생각했었는데 1학년 때 캔위성 경연대회에 참여하고 중학교 때는 우주풍선 프로젝트를 기획하는 등 사실 생각해보면 항공우주분야와 접점이 꽤 있었다.. 머신러닝,알고리즘,해킹에 이어 항공우주까지..관심이 많다 참. 2학년 때는 내신공부는 정말 철저히 해야겠고, 머신러닝,알고리즘,해킹,항공우주 이 분야들을 엮어..

1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net DFS로만 풀려고 하니 시간초과가 떠서 고민하다 DFS에서 탐색을 진행할 때 사이클을 이루는 경우를 제외하고 이전에 탐색한 것과 동일한 탐색을 반복하는 경우가 있다. 예를 들어 아래와 같은 맵이 있다고 하자. 이때 (0,0) 부터 시작해서 이동가능한 경로를 따라 dfs를 진행한다고하면 아래와 같이 트리를 따라 탐색을 진행한다. 이때 왼쪽에서 오른쪽으로 dfs가 진행되고 있다고 하면 왼쪽에서 dfs를 시행할 때 (1,3)에서 탐색한 것, (3,1)에서 탐색한 것,..

1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 만약 연결 그래프라면 노드 1에서 부터 탐색을 시작해서 총 2가지 색을 이용해 인접 노드를 자신과 다른 색으로 색칠한다. 이때 이분 그래프를 만들때는 색깔을 기준으로 노드를 분류하면 된다. 만약 어떤 노드의 색과 그 노드의 인접 노드의 색이 같은 것이 있다면 이분 그래프는 불가능하다. 연결 그래프가 아니라면 색칠된 수와 전체 노드의 수를 비교했을 때 이 둘이 다를 경우이다. 따라서 이때는 노드 1에서 시작하지 말고 다른 노드들에서 시작해서 동일한 색..

13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 문제의 조건에 맞는 A,B,C,D,E 가 존재한다는 것은 각 사람들을 노드로 두고, 친구관계를 갖는 두 사람을 연결하는 간선으로 그래프를 생각하면, 어떤 한 노드에서 시작해서 다른 노드로 이동할때 탐색 깊이가 4 이상이라는 것이다. 즉 DFS를 이용해 어느 한 노드에서부터 시작해 다른 노드를 탐색할 때 깊이가 4 이면 조건을 만족한다고 볼 수 있다. 따라서 처음에 아래와 같이 DFS 코드를 작성했다. def dfs(v,graph,visited,depth): visited[v] = True # 만약 탐색 깊이가 4이면 가능 if depth == 4: print(1) ex..

https://www.acmicpc.net/problem/89728972번: 미친 아두이노요즘 종수는 아두이노를 이용해 "Robots"이라는 게임을 만들었다. 종수는 아두이노 한대를 조정하며, 미친 아두이노를 피해다녀야 한다. 미친 아두이노는 종수의 아두이노를 향해 점점 다가온다. www.acmicpc.net단순(?! 조금은 깐깐한) 구현 문제이다. 문제에서 제시된 게임 순서대로 꼼곰히 구현을 하면 된다. 다만 게임을 종료시키거나 로봇을 제거하는 부분을 어떻게 구현할지 적절한 아이디어를 떠올리는 것이 중요하다. 이번 글에는 내가 풀기 위해 떠올린 2개의 아이디어를 설명하고자 한다. 각 아이디어를 보면서 속으로 아이디어의 구현 가능성/명확성/타당성을 확인해보자. 참고로 1번 아이디어는 구현할 때 생각할 점..

19939번: 박 터뜨리기 $N$개의 공을 $K$개의 바구니에 문제의 규칙을 만족하면서 나눠 담을 수 있다면, 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이를 출력한다. 나눠 담을 수 없는 경우에는 -1을 www.acmicpc.net 간단한 수학문제이다. 바구니가 k개, 공이 n개인데 최소한 1개 들어가야하고 바구니 속 공의 개수는 다 달라야한다. 공의 개수의 최소는 높이가 1,2,3,..,k일 때 이므로 k(k+1)/2 > n 이면 불가능. n-k(k+1/2)는 1,2,3,..,k 개를 만들고 남은 공의 개수, 이때 가장 많은 공의 개수와 가장 적은 공의 개수의 차는 k-1개가 나올 수 있는 가장 최소임. 이때의 조건은 a+1,a+2,a+3,...,a+k, 즉 남은 공의 개수가 k의..