한달꾸 한달꾸

10월 되돌아보기 11월 되돌아보기 12월 중순 되돌아보기 Jungle에 합류한 지 15일이 지났다. 10분의 1이 지난 현재 한주 한주 조금씩 바빠지기 시작하고 있다. 월말에 바쁠수도 있을 것 같아서 미리 12월 (중순) 되돌아보기를 쓰게 되었다. 12월 22일 오전 00:20분 현재 백준 300문제를 달성하게 된 점도 영향을 미쳤다. 물론 백준 몇 문제를 풀었냐가 그 사람의 실력을 가늠하는 척도는 아니다. 심지어 알고리즘 문제 해결은 프로그래밍의 극히 작은 일부분에 불과하다. 하지만, 8월 말부터 시작해서 하루하루 꾸준히 나아가기로 한 약속을 현재까지도 꾸준히 지키고 있다는 점에 큰 의미가 있는 것 같다. 9월 24일부터 시작한 1일 1포스팅도 Jungle 0주 차 프로젝트를 진행한 12월 8일, 1..

왜? 작년 가을 교양 프로그래밍 수업을 들으며 Python을 처음으로 접하고, 3개월 전 부터 본격적으로 공부를 해왔다. 파이썬을 사용하며 더 깊이 알아보려 하고, 의문을 가졌던 적이 별로 없다. 나무 자르기(포스팅) 문제를 풀면서 파이썬에서 함수를 사용하는 경우에 속도가 더 빠른 경우를 접하게 되었다. 이 당시에는 단순히 백준 사이트의 문제라고 생각하고 넘어갔었다. 그런데, 오늘 함수를 사용했을 때, 더 빠른 상황을 다시 한 번 접하게 되었고 왜 이런 현상이 발생하는 것인지 굉장히 궁금해 졌다. 인터넷의 자료를 찾아봐도 시원하게 해결해 주는 곳이 없었기에, 파이썬을 기초부터 차근차근 다지며 알아가보려 한다. 수면 아래의 굉장히 거대한 빙산이 드러나는 느낌인데, 두려워하지 않고 오늘 부터 파해쳐 나가야겠..

Snake game Jungle 1주 차가 끝나고 2주 차도 절반가량이 지났다. 다음 주 주말에 Doodle 점프 게임을 만들어 보기 위해서 더욱 간단한 Snake game을 만들면서 연습해 보았다. 이번 주말에 만든 게임은 정말 간단한 형태이지만, 시도했고, 시작했다는 것에 큰 의미가 있는 것 같다. 콘솔 창에서 글씨를 출력하고, 삭제하고 다시 출력하는 방식으로 한 프레임 한 프레임을 구현했다. 전형적인 Snake Game과 동일하게 '*'로 표시되는 아이템을 먹을 때 마다 뱀의 길이가 길어진다. w, a, d, s로 상하좌우 방향을 이동할 수 있으며, 뱀이 자기 자신에 부딪힐 때 게임이 종료된다. 코드가 어떻게 구성되는지 알아보자. main main function은 아래와 같이 Setup(), 그리..

히스토그램에서 가장 큰 직사각형 click 3달 전에 도전했다가 바로 포기했었던 문제이다. 이번에는 다행히 풀려서 기쁜 마음으로 포스팅한다. 백준에서 처음으로 플레티넘 문제에서 정답을 받았다. 힌트도 없이! 문제 분석 높이가 다른 직사각형 여러 개로 이루어진 히스토그램이 주어졌을 때, 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 문제이다. 직사각형들을 왼쪽에 위치하는 것 부터 차례대로 stack에 쌓아 나갔다. stack에 직사각형의 높이 정보와 그 직사각형이 왼쪽으로 어디까지 이어질 수 있는지에 대한 정보를 저장했다. stack에는 직사각형의 높이 정보와 왼쪽으로 이어질 수 있는 최소의 index를 저장한다. maxSize에는 직사각형의 최대 높이를 저장하고, 초기값은 0이다. 먼저 높이 2의 직사..

가장 긴 증가하는 부분 수열 click 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 찾는 문제이다. 가장 긴 증가하는 부분 수열 포스팅 가장 긴 증가하는 부분 수열 3 포스팅 이전에 포스팅을 하긴 했지만, 진정으로 이해하고 포스팅한 것들이 아니라서 굉장히 부실했다. 이번 기회에 보다 자세하게 이분 탐색을 어떻게 사용하는지, Lower Bound는 왜 사용하는지 설명해보려고 한다. 이분 탐색을 이용한 구현을 설명하기 전에 DP로 푸는 방식에 대해서 간단히 짚고 넘어가자. DP - O(N^2) DP에는 해당 숫자가 증가하는 부분 수열을 만들 때, 최대 몇 번째 칸에 위치할 수 있는지에 대한 정보를 저장한다. DP[i]에는 [0, i-1]의 범위에서 value[i] > value[i-1]을 만족하는..

컴퓨팅사고로의 전환 1주차 주차별 키워드 알고리즘 기초(기초, 배열, 문자열, 재귀함수), 정렬, 완전탐색, 시간복잡도 더 고민해볼 키워드 문자열 탐색 - Suffix Array, KMP 정렬 - 퀵 정렬, 병합 정렬, 기수 정렬 SW사관학교 정글 WEEK01 시험 더하기 사이클 click 1,2,3 더하기 click 숫자 야구 click 숫자 야구 click 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net 마지막 문제였던 숫자 야구에 대해서 알아보자. 영수가 세자리 숫자를 하나 생각하고, 민혁이가 수를 물어..

처음으로 CodeForce Contest에 참가해 보았다. Div(1~3) 별로 난이도가 나뉘는데 이중 제일 쉬운 Div3를 시도해 봤다. 총 일곱문제가 출제되었고, 이중 3문제 밖에 풀지 못했다. 첫 시도 치고 나쁘지 않은 것 같지만, 앞으로 자극받고 더 열심히 공부하는 계기로 삼아야겠다. 문제 난이도는 그렇게 어렵다고 느껴지진 않았다. 내 실력이 부족할 뿐... E1문제를 풀고 포스팅해보려 했지만, 계속 시간초과의 벽에 부딪히는 바람에 C-Unique Number 문제로 포스팅할 예정이다. Code Froce - Unique Number click 각각의 인풋 X가 주어졌을 때, 숫자의 각 자리수가 중복되지 않으면서, 모두 더했을 때 X가 되는 가장 작은 수를 찾는 문제이다. 먼저, 10보다 작은 인..

타일 채우기3 2133-타일채우기문제와 유사한 DP문제이다. 포스팅한지 정확히 한달이 지나서 응용문제를 다시 한 번 풀어봤다. DP문제 중에서도 특히 2133번은 블로그에 해설을 아무리 찾아봐도 이해가 안되었던 문제였다. DP문제가 늘 그렇듯 이전단계에서 찾아낸 값을 어떻게 활용할지 찾아내야 하는데, 타일 문제들은 이 부분이 유독 안보였다. 문제 분석 먼저, 세로로 더이상 나눌 수 없게 배치한 경우와 세로로 나눌 수 없는 경우를 구별할 줄 알아야 한다. 이에 관한 것은 2133-타일채우기여기에 포스팅해 놓았으니 참고하자. 2 X N 크기의 타일을 세로로 나눌 수 없게 배치하는 경우를 그려보며 생각해보면 위와 같다. N이 2일때는 3가지가 있으며, 나머지는 모두 두가지씩이다. 자연스럽게 N = 1인 경우 ..