제이티의 코딩 블로그 제이티의 코딩 블로그

학교에서 진행하는 수업에서 공유받은 알고리즘 문제를 풀어보았다. 문제의 난이도는 골드 4로, 투 포인터를 활용해 푸는 것을 권장받은 문제이다. 문제 링크 https://www.acmicpc.net/problem/1806 문제 분석 이번 문제는 입력으로 길이 N짜리 수열이 주어진다. 해당 수열에서 연속된 수들의 부분 수열의 합에서 그 합이 S 이상이 되는 것 중 가장 짧은 부분 수열의 길이를 구하는 프로그램을 작성해야 한다. 시작점과 끝점이 있을 때, 시작점부터 끝점까지의 부분 수열의 합은 끝점이 시작점에서 멀어질 수록 점점 커지는 경향이 있다. 만약 수열에 음수가 포함된다면 이러한 성질을 갖지 못하지만, 해당 문제에서는 '10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다'고 조건에 나와있..

학교에서 진행하는 수업에서 공유받은 알고리즘 문제를 풀어보았다. 문제의 난이도는 실버 1로, BFS(너비 우선 탐색)를 활용해 푸는 것을 권장받은 문제이다. 문제 링크 https://www.acmicpc.net/problem/2178 문제 분석 주어진 미로에 대해 (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성해야 한다. 이 때, 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 자료 구조 1. 큐 (Priority Queue) 큐는 먼저 들어온 데이터가 먼저 나가는 FIFO형 자료구조이다. BFS를 구현할 때에는 큐를 사용하여 구현한다. 2. BFS 알고리즘 BFS는 그래프 탐색 알고리즘 중 하나이다. DFS와 달리 ..

학교에서 진행하는 수업에서 공유받은 알고리즘 문제를 풀어보았다. 문제의 난이도는 실버 5으로, 우선 순위 큐를 활용해 푸는 것을 권장받은 문제이다. 문제 링크 https://www.acmicpc.net/problem/1417 문제 분석 다솜이가 국회 의원에 당선되도록 하기 위해 다른 사람에게 간 득표를 자신, 기호 1번에게 오도록 사람들을 매수하는 최소 횟수를 구하는 문제이다. 예를 들어 기호 1번이 5표, 기호 2번이 7표, 기호 3번이 7표라고 한다면, 다솜이는 2번 후보를 찍으려고 하던 사람 1명과, 3번 후보를 찍으려고 하던 사람 1명을 돈으로 매수하면 기호 1번이 7표, 기호 2번이 6표, 기호 3번이 6표이므로 국회 의원에 당선된다. 자료 구조 1. 우선순위 큐 (Priority Queue) ..

학교에서 진행하는 수업에서 공유받은 알고리즘 문제를 풀어보았다. 문제의 난이도는 실버 3으로, 투 포인터를 활용하여 푸는 것을 권장받은 문제이다. 필자는 투 포인터 방식과 Hash Map을 활용한 방식, 두 가지로 풀어보았으므로 두 가지 모두 서술하도록 하겠다. 문제 링크 https://www.acmicpc.net/problem/3273 문제 분석 서로 다른 양의 정수 중 두 개를 골랐을 때, 두 수의 합이 x가 되도록 하는 조합의 수를 구하는 문제이다. 해당 문제는 기본적으로 투 포인터 문제로 분류되어 있다. 문제 풀이 이 문제의 핵심 키워드는 'n개의 서로 다른 양의 정수', '두 수의 합'이다. 1. 투 포인터 먼저 투 포인터 방식으로 푼 것에 대해 설명하기 전에 투 포인터가 무엇인지부터 작성하겠다..

학교에서 진행하는 수업에서 공유받은 알고리즘 문제를 풀어보았다. 문제의 난이도는 프로그래머스 레벨 2으로, DFS로 해결하려 하였을 때에는 해결책이 도저히 보이지 않아 풀지 못할 것으로 예상하였으나 DFS를 포기하고 백트래킹을 활용하여 문제를 풀 수 있었다. 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/150368 문제 분석 문제를 풀기 위해서 수업 시간에는 힌트로 DFS가 주어졌으나, 필자는 DFS를 사용하는 대신 백트래킹을 통해 문제를 해결하였다. 백트래킹을 활용하여 이모티콘의 할인도의 경우의 수를 모두 찾아내 문제를 해결할 수 있었다. 문제 풀이 문제를 풀 때에 백트래킹을 적극적으로 활용하였다. void backtracing(in..

학교에서 진행하는 수업에서 공유받은 알고리즘 문제를 풀어보았다. 문제의 난이도는 프로그래머스 레벨 1으로, 난이도를 보았을 때 간단히 풀 수 있는 문제로 예상하였으나 문제의 길이가 길어 읽고 이해하는 데에만 오랜 시간이 걸렸고, 시간을 들여 문제를 풀어냈다. 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/118666 문제 분석 문제를 구체적으로 분석하기 앞서 간단히 설명하면, 카카오 방식의 MBTI 검사를 만든 문제라고 할 수 있다. 각 검사지 "RT", "CF", "JM", "AN" 유형 중에서 높은 점수가 나온 쪽이 검사 결과로 나타나는 방식이다. 예를 들면 누군가는 검사 결과 "RCJN"이 나올 수 있다. 문제 풀이 문제를 풀 때에..

학교에서 진행하는 수업에서 공유받은 알고리즘 문제를 풀어보았다. 문제의 난이도는 실버 4로, 스택 자료구조를 활용하여 푸는 문제이다. 수업 시간에 발표를 들으며 알게된 것이지만, 사실 스택 자료구조를 사용하지 않고도 문제를 풀 수 있다. 하지만 여기서는 스택 자료구조를 활용하여 푼 방식을 작성할 것이다. 문제 링크 https://www.acmicpc.net/problem/9012 문제 분석 괄호 쌍이 적절하게 맞는지 확인하는 문제이다. 괄호 쌍이 맞는다는 건 단순히 '('와 ')'의 갯수가 같으면 되는 것이 아니라, '('와 ')'의 순서도 맞아야 하기 때문에 갯수를 세는 방식으로 문제를 풀면 답이 틀리게 된다. 문제 풀이 스택 자료구조를 활용하여 문제를 해결하였다. 입력값을 순회하며 char형 ch에 ..

학교에서 진행하는 수업에서 공유받은 알고리즘 문제를 풀어보았다. 문제의 난이도는 브론즈 1이다. 문제 링크 https://www.acmicpc.net/problem/1546 문제 분석 입력된 모든 점수의 합을 구한 뒤, 평균을 두하고 입력값 중 최댓값인 M으로 평균값을 나누고 100을 곱하면 되는 문제이다. 전체 코드 #include #include using namespace std; int scores[1001]; int N; int max_score = 1; double avg_score = 0.0; int main(void) { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> N; for (int i = 0; i > s..