B_log

📎 간략한 문제 정리 N개의 좌표 X1~XN이 있을 때 X1'는 X1보다 작은 서로다른 요소의 개수를 의미합니다. 📈 문제 분석 주어진 배열을 정렬한 후 문제를 처리하면 쉽게 접근할 수 있습니다. 🙋‍♂️ 내가 처음 생각한 해결 방법 가장 단순하게 생각해보면 전체를 순회하며 기준을 세우고, 자신을 제외한 다른 요소들을 검색해보며 더 작은 값이면 count += 1의 로직을 구현할 수 있습니다. 하지만 이것은 O(N^2)이며 주어진 조건 1 Stack의 전형적인 문제 중 특정 요소의 왼쪽 값 중 자신보다 크면서 인덱스가 가장 큰 요소를 찾는 문제가 있습니다. 이 문제처럼 왼쪽만 관찰하며 더 큰 값일때만 pop하는 해결방식을 활용한다면 O(N)이 가능할 수 있을 것 같습니다. Counting Sort..

📎 간략한 문제 정리 Back Tracking에서 가장 유명한 문제 중 하나인 N-Queen을 다시 풀어보았습니다. 체스에서 Queen은 수직, 수평, 대각선 방향으로 거리의 제한없이 이동할 수 있을 때, N개의 Queen을 배치할 수 있는 모든 경우의 개수를 출력하는 문제입니다. 📈 문제 분석 이 문제의 포인트는 크게 두가지 입니다. BackTracking을 어떻게 구현할 것인가 Queen을 배치 가능한지 여부 판단하기 Back Tracking 부분은 N과 M 문제와 크게 다르지 않습니다. 반복을 하며 조건을 확인하는 BackTracking의 기본 구조를 가지고 있습니다. 방문 여부를 체크하고, 배치가 완성되면 배치 가능한 모양이 한개 생성되므로 결과에 +1을 해줍니다. 더 까다로운 포인트는 2번인데,..

📎 간략한 문제 정리 자연수 N과 M이 주어지고, 아래 조건을 만족하는 길이가 M인 수열을 모두 구합니다. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 고른 수열은 오름차순이어야 한다. 📈 문제 분석 N과 M(1)과 거의 비슷한 문제입니다. 오름차순을 이루는 부분 수열을 찾는 문제로 중복이 없고, 부분 수열의 크기가 정해진 것이 포인트입니다. 🙋‍♂️ 내가 처음 생각한 해결 방법 사실 파이썬에는 모듈인 itertools에 combination 함수가 존재합니다. 그래서 N의 요소에서 M개를 뽑는 것은 어렵지 않지만 일부러 이 방법을 사용하지 않았습니다. 이 모듈을 사용하지 않을 때 필요한 것은 모든 요소를 접근하며 조건에 만족할 경우 결과에 넣는 작업입니다. 이 때 사용되는 백트래킹(Back..

📎 간략한 문제 정리 위의 그림처럼 한 변의 길이가 2의 거듭제곱꼴인 N의 정사각형(NxN)이 존재합니다. 이 사각형은 길이가 1인 단위 정사각형으로 이루어져 있으며 색깔을 가집니다. 만약 이 정사각형이 모두 색깔이 같다면 자르지 않지만, 하나라도 색깔이 다른 부분이 있다면 종이 가로 세로의 가운데를 잘라 4등분하여 위의 작업을 반복합니다. 모든 작업이 완료되면 흰 종이(0으로 마킹)의 개수과 파란 종이(1로 마킹)의 개수를 출력합니다. 📈 문제 분석 전형적인 분할 정복 문제입니다. 특정 시점에서 조건에 맞는지 확인(모두 같은 색)한 후, 조건에 맞으면 추가 작업을 진행하지 않고, 조건을 만족하지 않으면 재귀적으로 문제를 다시 해결해나가는 구조입니다. Merge Sort(병합 정렬)처럼 개념으로 배울 때..

문제 www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제 상황 - 앞서 풀이한 오큰수에서 크기로 비교하는게 아니라 출현 횟수를 기준으로 판단하는 차이밖에 없다. 해결 전략 - stack을 활용하여 왼쪽을 쳐다봐서 횟수의 내림차순을 유지하는 구조로 코딩한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 from sys import stdin from collections import Counter input = stdin.readline n = ..

문제 www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제 상황 - 배열 A가 주어지고 특정 인덱스 i를 기준으로 i보다 큰 수 중 A[i]

문제 www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 문제 상황 - 탑의 높이가 주어지고 각 탑이 발사한 레이저 신호는 해당 탑의 왼쪽에 존재하는 탑들 중 더 높고, 가장 가까운 탑에서 수신 가능하다. 각 탑이 발사한 신호를 수신하는 탑의 순서를 반환하여 출력한다. 해결 전략 - 단순히 생각하면 하나의 기준 탑을 잡고, 그 왼쪽을 순회하며 봐야하므로 O(N^2)으로 해결 가능하다. 하지만 문제 조건이 최대 500,000개의 탑 이므로 N^2, 혹은 N*M의..

문제 www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 문제 상황 - 주어진 입력값들의 산술평균, 중앙값, 최빈값, 범위를 구하는 문제이다. 해결 전략 - 단순한 계산문제이지만 최빈값을 어떻게 구하는지의 문제가 있다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 from collections import Counter from sys import stdin input = stdin.readline n = int(..