한달꾸 한달꾸

🧀치즈 click 이 문제도 두 달에 걸쳐 시도했지만, 풀지 못했던 문제였다. 두달여 만에 시도했더니 생각보다 수월하게 풀 수 있었다. 그새 실력이 성장한 것 같다. 앞으로도 꾸준히 풀어나가자! 문제 분석 문제를 풀면서 가장 고민이었던 부분 두 가지는, 내부 공기를 어떻게 처리해야 하는지와 치즈들을 어떻게 탐색해 나갈지 였다. 내부 공기 먼저, 내부 공기와 외부 공기를 다른 문자(혹은 숫자)로 표시한다. 녹을 치즈들에 대해 내부 공기와 동일한 문자로 변경해둔다. 한 사이클을 모두 돌고난 후에 녹은 치즈들을 시작으로 BFS탐색을 하며 외부 공기와 닿은 내부 공기도 모두 외부 공기로 변경한다. 치즈 탐색 치즈들을 모두 deque에 추가해둔 후에, 각 치즈들에 대해 탐색을 한다. 이때, 녹은 치즈면 deque..

벽 부수고 이동하기 click 두 달 동안 고통받았던 문제를 (힌트를 조금 얻긴 했지만)오늘 드디어 풀 수 있었다. 기본적인 컨셉은 이해하고 있었는데, 시간초과의 벽에 부딛혀 힘들어 했었다. 기본 BFS를 별 생각없이 너무 많이 풀다보니, 내 코드에 틀을 정해놓고 적용시키는 느낌이 든다. 유연한 사고를 방해하는 원인인 것 같다. 알파벳 문제도 그렇고 조금 더 높은 난이도의 문제를 풀며 응용력을 키워나가야 겠다. 문제 분석 맵에서 0은 이동할 수 있는 곳을 나타내고 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 다른 BFS문제와 다른 점은 벽을 한 번 부수고 이동할 수 있다는 것이다. 이때, 벽을 부쉈는지 혹은 부수지 않았는지에 상관 없이 최단거리로 도달하는 경우를 구해야 한다. BFS를 진행하며 현재 ..

Python에서의 'Call by Object Reference' 파이썬의 변수에 대해 공부하다가 함수 인수 전달 방식인 call by value call by reference call by object reference 에 대해 알게 되었다. 이들의 차이점에 대해 알아보자! Call by Value 함수에 인수를 전달하는 방식이다. 변수의 값을 복사해 함수의 인자로 전달한다. 따라서, 함수 내에서 전달된 인자를 조작해도 함수 외부의 변수에는 영향을 미치지 않는다. Call by Reference 함수에 인수를 전달하는 방식이다. Java 혹은 C언어의 포인터로 함수의 인자에 전달하는 방식이 이와 같은 방식이다. 변수가 가리키는 주소 값을 함수의 인자로 전달한다. 함수 내에서 전달된 인자를 조작하면, ..

컴퓨팅 사고로의 전환 1주 차 주차별 키워드 - 이분 탐색, 분할 정복, 스택, 큐, 우선순위 큐 더 고민해볼 키워드 - 세그먼트 트리 - 분할 정복 - heapq, stack, deque Class 구현 SW사관학교 정글 WEEK01 시험 - 쿼드 트리 click - 쇠막대기 click - 소수의 곱 click 소수의 곱 click 2014번: 소수의 곱 첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의 소수가 오름차순으로 주어진다. 같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 모두 541보다 작거나 www.acmicpc.net 이번 주의 마지막 문제였던 숫자 야구에 대해서 알아보자. K 개의 소수가 주어졌을 때, 이 소수들을 서..

히스토그램에서 가장 큰 직사각형 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]을 만족하는..

처음으로 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인 경우 ..