https://www.acmicpc.net/problem/2667 2667번은 DFS/BFS 단계별 문제에 있는 정답률 약 38%의 문제입니다. 정답률에 비해 DFS의 개념을 잘 적용할 수만 있으면 그렇게 어렵지는 않은 문제였습니다. DFS는 깊이 우선 탐색이라는 뜻의 Deep-First Search 의 줄임말입니다. 정점과 간선으로 이루어진 그래프에서 모든 정점을 방문하는 방법인데, 정확한 정의는 한 임의의 노드에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법입니다. 즉, 한 정점에서 간선을 따라 이동한다고 할 때, 이동한 정점에도 간선이 있을 경우 더이상 연결된 정점이 없을 때까지 계속해서 연결된 정점을 탐색합니다. 더 이상 다른 정점으로 연결된 간선이 없는 마지막 정점에 ..
이번 포스트는 큐/덱 문제 중, 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) 단계에 있는 문제입니다. 알고리즘 스터디에서 자료구조에 대해서 같이 공부를 하며 진행을 하자고 얘기가 됐고, 좋은 것 같아서 차근차근 단계별로 있는 자료구조 문제 세트를 풀기로 했어요. 문제의 선정 기준은 제출한 횟수가 많은 문제 중, 정답률이 제일 낮은 문제로 결정했네요. 당연한 말이지만, 스택 수열은 스택이라는 자료 구조를 활용하여 풀 수 있는 문제입니다. 스택이란 간단히, 입구가 하나인 통에 정보를 넣고 꺼낼 수 있는 ..
https://www.acmicpc.net/problem/1025 1025번 문제는 제곱수 찾기입니다. 문제 해석부터 꽤 어려운 문제였습니다. 다행히 저만 그런 것은 아니었는지, 이 문제에 대한 질문 게시판에서 무슨 말인지 겨우 이해하게 됐네요. 걸어둔 링크를 참고해주시길 바랍니다. Hint! 그러니까, 행과 열 번호가 모두 등차수열을 이루면서 만들어지는 제곱수 중 최대를 구하라는 것이네요. 다행히 입력받는 수의 개수가 최대 9 * 9 = 81개라서 크게 무리가 되는 양은 아니라서 전수조사를 하는 방향으로 했습니다. 전수 조사를 하는 요소는 (1) 행의 시작 위치, (2) 열의 시작 위치, (3) 행에 적용되는 공차, (4) 열에 적용되는 공차입니다. 한 가지 주의할 점은 공차가 음수와 0도 가능하다는 ..
제가 이번 주부터 친구들과 알고리즘 스터디를 진행하고 있습니다! 이번 주차는 Dynamic Programming(DP)을 공부하기로 했고, DP 문제 중, 1912번의 연속합 문제를 풀기로 하였습니다. https://www.acmicpc.net/problem/1912 1912번 연속합 문제는 DP의 한 문제로 소개가 되어 있었습니다. 정답률이 높지 않아서, 어려운 문제를 도전하자고 스터디원들과 선택해서 풀게 되었습니다. 저는 DP에 대한 개념을 탄탄하게 알고 있는 편은 아니었고, 개념을 설명해둔 글들을 마구마구 보아도 이해가 잘 안가서 결국 DP로 푸는 문제들을 대부분 포기를 하거나 하는 그런 상황이었습니다. 이번 문제로 DP를 활용해봐서 아 이런 느낌이구나 하는 것을 알았습니다! 이전에 스킵해둔 문제들..
https://www.acmicpc.net/problem/1024 1024번 문제는 수열의 합이라는 이름으로 소개되어 있습니다. 여기서 수열은 연속된 음의 정수가 아닌 수로 이루어진 수열로 한정되어 있고, 수열의 합이 되어야 하는 값과 최소한으로 가져야 하는 수열의 길이가 주어집니다. 문제 설명은 여기까지 하고 풀이 설명 들어갈게요! Hint! 고등 수학 과정에서 등차 수열이라는 개념이 있습니다. 연속된 수로 이루어진 수열은 대표적인 등차 수열이고, 그래서 이 문제에서는 등차 수열의 성질을 이용해서 문제를 풀 수가 있습니다. 등차 수열에 대한 개념은 여기서 다루지 않을 테니 만약 모르신다면 검색을 통해 간단히 공부를 하고 오시면 될 것 같습니다! 여기서 사용된 연속된 수열의 성질은 두 가지 케이스로 구분..
https://www.acmicpc.net/problem/1022 1022번은 소용돌이 예쁘게 출력하기 입니다. 아! 이제부터 문제 설명은 위 페이지에 있으니 생략하려고요...ㅎㅎ 풀이 위주로 설명할게요! Hint! 자잘하게 생각할거리가 많아서 차근차근 보도록 하겠습니다. 먼저 소용돌이는 문제에서 알려준 것처럼 중앙에서 출발해 숫자를 늘리며 나선형으로 배열되어 만들어집니다. 이해하는데 크게 어렵지는 않으나, 제 풀이에는 이 소용돌이를 어떻게 바라보느냐가 중요합니다. 행 번호는 r로, 열 번호는 c로 표현할 때, 아래는 -10 < r < 10, -10 < c < 10 까지 출력한 소용돌이의 모습입니다. 저는 level이라는 것을 먼저 정의하려고 합니다. level은 현재 소용돌이가 중심으로 부터 얼마나 떨..
https://www.acmicpc.net/problem/1021 * 1020번은... 생각보다 어렵네요 ㅠㅠ 공부를 좀 더 해보고 기회가 되면 다시 풀어보려 합니다. 1021번은 회전하는 큐라는 이름의 문제로 소개되어 있습니다. N개의 원소를 포함하고 있는 양방향 순환 큐에서 원하는 원소를 정해진 연산 법칙에 맞게 뽑아내는 데요, 그 연산 법칙은 다음과 같습니다. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ..
https://www.acmicpc.net/problem/1019 1019번 문제는 설명이 짧아서 간단할 것 같았는데 정답률(이 글을 쓸 땐 36%네요.)을 보고 뭔가 있군... 했던 문제입니다. 문제는 첫 페이지가 1쪽이고 마지막 페이지가 N쪽인 책에서 0~9까지 각 숫자가 몇번 등장할 것인지 출력하는 것입니다. 간단하지만... 간단하진 않습니다. 입력받을 수 있는 수가 최대 10억이기 때문이죠. 입력받은 수를 그대로 반복문을 돌려 각 자리 숫자를 센다면, 꼼짝 못하고 시간초과를 받을 수 있는 문제입니다. 문제에서는 11이 예시로 들어져 있는데요, 11쪽까지 있는 책의 페이지는 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 이렇게 이루어져있고, 1은 총 4번, 나머지 숫자들은 모두 1번씩..
https://www.acmicpc.net/problem/1018 1018번 문제는 체스판 다시 칠하기 문제입니다. 엄청 어렵지는 않지만, 차근차근 코드를 짜는 것이 중요한 문제라고 생각합니다. 문제를 간단히 설명하자면, 지민이가 흰색이나 검정색으로 색칠되어 있는 단위 정사각형으로 이루어진 N * M 크기의 보드를 찾았고, 이 보드를 8 * 8 크기로 잘랐을 때 체스판이 되기 위해 추가적으로 칠해야할 부분의 최소 개수를 구하는 문제입니다. 체스판의 정의는 우리가 잘 알고 있는 체스판처럼 흰색과 검정색으로 번갈아져 색칠되어 있으면 되어져 있는 보드를 의미합니다. 이 때, 체스판은 제일 왼쪽 상단 정사각형의 색이 흰색 혹은 검정색으로 칠해져 있는 총 두가지의 종류로 이루어질 수 있습니다. 저는 이 점을 힌트..
