www.acmicpc.net/problem/2869 단계별 문제에 기본 수학 1에 올라와 있던 문제입니다. 당연히, 올라갔다 내려갔다를 반복하는 알고리즘을 짜면 안되고, 도착했을 시점에 며칠이 흘렀는지 계산하는 수학 식을 적절히 세워야합니다. 🤔 고민된 점 특별히 고민이 될만한 점...이라기 보다는, 달팽이가 마지막에 목표 높이에 올라가는 시점에 며칠이 지났는지를 측정한다는 점을 주의해야 한다는 정도였습니다. 그러니까, 목표 높이에 닿으면 다시 미끄러질일이 없다는 점을 주의해야해요. ✔️ 힌트/해결법 먼저, 달팽이는 하루에 A미터 올라가고 B미터 내려가는 행동을 반복하기 때문에 하루가 지나면 최종적으로 A-B 미터를 움직인다는 것을 쉽게 알 수 있습니다. 앞서 말했듯이, 중요한 점은 A미터를 올라갔을 때..
https://www.acmicpc.net/problem/2805 2805번 문제는 백준 알고리즘의 이분 탐색 단계에 속하는 비교적 낮은 성공률의 문제입니다. 문제의 성공률이 낮아 어려울까 생각을 했었는데, 이분 탐색의 개념을 그대로 적용할 수만 있다면 난이도가 높은 문제는 아니었습니다. 이분 탐색은 매 스텝마다 탐색의 범위를 절반씩 줄여나가며 정답으로 가까워지는 탐색 방법으로 탐색 방법 중 매우 빠른 속도를 자랑하는 알고리즘입니다. 흔히, 오름차순으로 이루어진 배열에서 원하고자 하는 값을 찾을 때 이분 탐색을 사용해 빠르게 찾아내는 것을 예시로 들어 설명하는 것 같았습니다. 저는 이분 탐색의 개념을 이 블로그에서 쉽게 알 수 있었는데요, 그림으로 차근차근 설명이 되어 있으니 공부하실 때 참고하시면 좋을..
https://www.acmicpc.net/problem/1027 1027번 문제는 겉보기에 그렇게 어렵지 않게 보이지만, 약간의 수학적인 아이디어가 필요한 문제입니다. 여기서 사용된 수학적인 아이디어란, 어떤 건물에서 다른 건물을 볼 수 있는 조건이 수학적으로 어떻게 해석되느냐? 에 대한 답을 할 수 있어야 한다는 것이었네요. Hint! 문제에서는 어떤 건물(x1, y1)에서 다른 건물(x2, y2)을 볼 수 있으려면, 두 건물을 이은 선분이 다른 건물을 지나거나 접하지 않아야 한다고 했습니다. 아래의 그림은 임의의 한 건물을 기준으로 오른쪽을 볼 때, 볼 수 있는 건물들이 무엇이 있는지 보여준 것입니다. 아이디어 설명을 위해 그렸네요. 우선, 빨간색 건물을 기준으로 본다고 할 때, 저는 이 건물의 오..
https://www.acmicpc.net/problem/1026 1026번 문제는 보물이라는 이름으로 소개되어 있습니다. 어렵지 않은 문제였고, 다만 저는 문제를 풀 때 두가지 방법이 생각이 났었네요. Hint! 이 문제에서 주어진 것처럼, A는 재정렬을 해야하는 수열, B는 그대로 있어야 하는 수열입니다. S는 두 배열의 각 원소끼리 곱하여 더하는 수식을 의미합니다. (임의로 배열을 설정하고 수식에 적용하시면 알 수 있습니다.) 두 배열의 각 원소끼리 곱하여 더했을 때, 최소가 되는 상황은 한 원소가 크면 클수록 곱해지는 다른 원소는 작아져야 한다는 것입니다. 문제의 예제와 힌트를 보면, 재정렬된 A는 B의 원소들 중 가장 큰 원소 (8)를 A 원소들 중, 가장 작은 수(0)와 매치하고 그 다음 큰 ..
https://www.acmicpc.net/problem/1629 이번 문제는 분할 정복 개념을 공부하기 위해 백준 알고리즘의 단계별 문제 풀이에서 고른 성공률 25%의 곱셈이라는 문제입니다. 음.. 이 문제를 풀면서 느꼈던 것은 분할 정복의 개념 자체는 쉽지만 이 개념을 어떻게 적용하는지는 쉽지 않다는 것입니다. 마치, 고등학교 때 미적분 기본 개념들을 숙지해도 수능의 29, 30번 문제는 어떻게 푸는지 감이 잘 안잡히는... 그런 느낌이었습니다. 아이디어가 떠오르면 어떻게든 하면 되는데? 그 아이디어가 생각나기까지는 어느 정도 직관이 필요한 것 같습니다. 분할 정복이란? 분할 정복이란, 말 그대로 분할하고 정복하여 답을 구해내는 알고리즘 기법입니다. 당연한 말이잖아... 좀 더 풀어 설명하면, 주어진..
https://www.acmicpc.net/problem/10951 백준 문제 번호 순서대로 푸는 것이... 그닥 좋은 것 같지 않아서 단계별로 풀고 있습니다. (쉬운 문제가 정말정말 많군요 ㅠㅠ, 순위 팍팍 올려버뤼기~) 쉬운 대부분의 문제는 스킵하고 살짝 테크닉이 들어간 문제들을 리뷰하려고 합니다. 10951 문제.. 사실 별건 아니고, while문을 사용하는 단계에 있는 기본 문제인데 사용자의 `input`이 없을 경우 while문을 어떻게 빠져나오는지 몰라서 구글링 했다는 그런... 자존심 살짝 상한 일이 있어서 살포시 적고 갑니다. 채점 컴퓨터의 `input`이 없는 경우 런타임 에러가 발생하는 것을 확인할 수 있었습니다. 따라서, 인풋을 진행을 할 때 런타임 에러가 발생하는 경우 사용자의 입력..
https://www.acmicpc.net/problem/1931 이번 문제는 Greedy 알고리즘에 대한 개념을 공부하기 위해 선정된 1931번 회의실 배정 문제입니다. Greedy 알고리즘이 이름이 생소해서 시간이 좀 걸릴까 했는데, 개념 자체는 그렇게 어렵지 않고 그 개념을 그대로 이해해서 풀 수 있는 문제여서 적절히 잘 배운 것 같습니다. Greedy 알고리즘, 탐욕 알고리즘은 매 순간마다 최적의 답을 찾아가는 알고리즘입니다. 보통 이전에 리뷰한 Dynamic Programming(DP)과 비교가 되곤 하는데요, 되도록 모든 경우에 대해 탐색을 해서 전체의 해결책을 찾는 DP와는 달리 탐욕 알고리즘은 지금 당장의 분기마다 최적의 답만 찾아간다는 것이 다릅니다. 1분의 시간이 있는데, 지금 당장 바..
https://www.acmicpc.net/problem/2178 2178번 문제는 알고리즘 스터디에서 BFS 주제로 잡은 문제입니다. 기본적인 BFS 문제인 것으로 생각이 될 정도의 난이도인 것 같고 연습하기에 좋은 것 같습니다. Breadth First Search(너비 우선 탐색)의 줄임말인 BFS는 깊이 우선 탐색인 DFS 와 함께 소개가 되고는 합니다. 노드를 전부 탐색한다는 점에서 비슷하지만 탐색하는 방식의 차이 때문에 각각의 방법으로 풀 수 있는 문제가 구분되기도 하기 때문인데요, 미로에서 시작 지점부터 도착 지점까지 최소거리를 구하는 이번 문제가 대표적인 BFS 문제로 여겨지는 것 같습니다. BFS는 DFS와는 달리 재귀적인 함수의 형태를 가지지 않는 점과, Queue 자료 구조를 사용한다..
이번 포스트는 큐/덱 문제 중, 5430번 AC 문제를 풀기로 했습니다. 알고리즘 스터디에서 선정한 문제에요! https://www.acmicpc.net/problem/5430 큐(Queue)와 덱(Deque, Double-ended Queue의 약자)은 스택(Stack)과 같이 알고리즘 풀이에 많이 활용되는 자료 구조입니다. 덱은 이름에서 알 수 있듯이 큐의 한 종류입니다. 스택과 큐의 차이점은 스택은 정보를 넣고 뺄 수 있는 입구가 하나임과 다르게 큐는 입구가 두 개라는 것입니다. 그 중, 큐는 정보가 들어가고 나가는 방향이 결정이 되어 있고 덱은 결정이 되어 있지 않고 입구 양쪽에서 넣거나 뺄 수 있습니다. 아래 그림을 참고해주세요! Hint! 5430번 AC 문제는 Deque 자료 구조를 활용하는..
알고리즘 스터디의 이번 주차는 스택/큐/덱을 공부하기로 했고, 이번 포스트는 스택 문제 중, 1874번 스택 수열 문제를 풀기로 했습니다. https://www.acmicpc.net/problem/1874 1874번 스택 수열 문제는 백준 알고리즘 단계별 문제 중, 스택(Stack) 단계에 있는 문제입니다. 알고리즘 스터디에서 자료구조에 대해서 같이 공부를 하며 진행을 하자고 얘기가 됐고, 좋은 것 같아서 차근차근 단계별로 있는 자료구조 문제 세트를 풀기로 했어요. 문제의 선정 기준은 제출한 횟수가 많은 문제 중, 정답률이 제일 낮은 문제로 결정했네요. 당연한 말이지만, 스택 수열은 스택이라는 자료 구조를 활용하여 풀 수 있는 문제입니다. 스택이란 간단히, 입구가 하나인 통에 정보를 넣고 꺼낼 수 있는 ..
