✔ 문제 난이도 : 실버2 🥈 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net ✔ 문제 풀이 입력값의 범위가 n(1 ≤ n ≤ 100,000)이기 때문에 단순히 이중 for문을 통해 계산하게 되면 시간초과가 됩니다. 동적 계획법(DP)을 적용하여 시간복잡도를 낮추어 풀어야합니다. 위 문제에서는 '연속되는 몇 개의 수'라는 조건이 주어졌기 때문에 연속되는 수의 누적합을 배열에 저장하여 비교하면서 중복되는 연산을 줄일 수 있습니다. Bottom-Up과 Top..
🤔 동적 계획법 DP? 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법입니다. 즉, 문제 해결을 위해 설계하는 방법이나 접근 방식을 말합니다. 💡 메모이제이션(Memoization) 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다. wikipedia 동적 계획법(DP)의 핵심이 되는 기술로 가장 큰 특징이라고 할 수 있습니다. 상향식, 하향식 접근 방식을 통해 문제를 작은 하위 문제로 나누어 이를 해결하면서 하위 문제의 결과를 메모이제이션 즉 메모리에 저장함으로써 중복 연산을 줄일 수 있습니다. 🔎 상향식(bottom-up) 접근 작은 하위 ..
✔ 문제 난이도 : 골드4 🥇 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net ✔ 문제 풀이 실제 스도쿠 규칙과 같이 가로줄, 세로줄, 작은 정사격형 안의 수들이 1부터 9까지 하나씩 있어야합니다. 숫자가 입력 되었을 때 가로줄, 세로줄, 작은 정사각형을 탐색하여 중복된 숫자가 있는지 체크하는 로직은 쉽게 머리속에 떠올릴 수 있었지만, 어떤 흐름으로 어떤 조건을 사용하여 재귀호출하며 백트래킹 과정을 거칠지는 많이 고민이 필요한 문제였습니다. 🔎 isChecked 가로와 세로체크는 모든 9개의 범위를 탐색하여 ..
✔ 문제 난이도 : 골드4 🥇 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net ✔ 문제 풀이 N x N의 체스판 위에 N개의 퀸을 서로 공격할 수 없게 놓는 경우의 수를 구하는 문제입니다. 🤔 처음 접근 처음 접근할 때에는 첫번째 퀸을 두고 그 퀸의 공격범위를 모두 체크(방문처리)한 후 공격범위가 아닌 부분 부터 두번째 퀸을 두고 공격범위를 체크하며 나아가다 퀸 N개 즉 깊이(depth)가 N이 되었을때 리턴하여 백트래킹을 수행하려고 했습니다. 하지만 공격범위를 모두 체크하는 과정에서 이중 for문을 사용하였고 재귀호출이 끝..
🤔 Brute force 브루트포스 알고리즘? '무식한 힘' 으로 해석할 수 있겠습니다, 이 뜻 처럼 주어진 문제를 무식하게 하나하나 탐색하는 알고리즘 입니다. 모든 경우의 수를 전부 탐색하여 조건에 맞는 답을 찾기 때문에 정확한 답을 보장합니다. 하지만 모든 경우의 수를 탐색하기 때문에 시간복잡도가 높다는 단점이 있습니다. 그렇기 때문에 브루트포스 알고리즘은 시간복잡도를 고려하여 사용해야합니다. 또한 브루트포스 알고리즘은 정형화된 틀이 없기때문에 주어진 문제 유형에 따라 다양한 방법으로 풀이합니다. 단순 Brute force ( for문 ) 재귀호출 비트마스크 순열 DFS / BFS 💡 하지만 비효율적으로 보이는 브루트포스 알고리즘을 왜 사용할까요? 입력되는 범위가 작고, 탐색해야할 경우의 수가 적은 ..
✔ 문제 난이도 : 골드5 🥇 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net ✔ 문제 풀이 주어진 예제 처럼 첫째 줄에 NxN의 배열에 해당하는 N이 주어지고 각 칸에 R,G,B중 하나를 색칠한 그림이 둘째 줄부터 주어집니다. 이때 각 색들이 차지하는 구역과, 적록색약인 사람이 봤을 때의 구역을 구하는 문제입니다. 적록색약은 R(빨강)과 G(초록)이 잘 구분되지 않기 때문에 같은 구역으로 생각하여 카운트하도록 코드를 짠다면 쉽게 풀 수 있습니다. 💡 단순하게 R과 G일 경우 조건을 주어 탐색을 진행하려..
