알고리즘 문제 풀이: 제곱 정렬, 최소 부분 배열, 나선형 행렬
997. 정렬된 배열의 제곱 계산
입력된 비내림차순 정수 배열의 각 원소 제곱값을 오름차순으로 반환하는 문제입니다. 원소에는 음수가 포함될 수 있습니다.
무차별 대입 방식: 각 원소의 제곱을 계산한 후 Arrays.sort()로 정렬합니다.
양방향 포인터 방식: 제곱값이 가장 큰 값이 배열 양 끝에 위치한다는 특성을 활용합니다. 두 포인터를 배열 양 끝에 두고 비교하며 결 ...
8월 20일 05:50에 게시됨
동적 계획법을 이용한 최댓값 및 경우의 수 문제 해결
동적 계획법(Dynamic Programming)은 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 강력한 기법입니다. 특히 최댓값이나 경우의 수를 구하는 문제에서 효율적입니다. 다음은 동적 계획법을 활용하여 두 가지 유형의 문제를 해결하는 방법입니다.
1. 최댓값 문제: 중복 문자가 없는 가장 긴 부분 문자열
문제 설명: 주어진 문자열에서 중복 문자가 없는 가장 긴 부 ...
8월 16일 02:39에 게시됨
2023년 6월 상하이 컴퓨터 학회 경기 플랫폼 삼급 문제 분석
T1 - 차분 누적 계산
정수 배열에서 모든 쌍에 대해 후항과 전항의 차를 구한 후, 이 차들의 합을 다시 계산한다. 예를 들어 수열 a₁, a₂, a₃, a₄에 대해 다음과 같은 결과를 도출해야 한다:
(a₂−a₁) − (a₃−a₁) − (a₃−a₂) − (a₄−a₁) − (a₄−a₂) − (a₄−a₃)
입력: 첫째 줄에 정수 n, 둘째 줄에 n개의 정수 a₁~aₙ
출력: 최종 결과값 (정수)
제약 조건:
- 50% 데이터: 1 ≤ n ...
8월 16일 01:00에 게시됨
최대공약수와 최소공배수 곱의 수학적 동등성 및 알고리즘 최적화
문제 정의 및 수학적 배경
주어진 $n$개의 정수 배열에 대해, 전체 원소의 최대공약수(GCD)와 최소공배수(LCM)의 곱이 모든 원소의 곱과 일치하는지 판별해야 합니다. 이를 수식으로 표현하면 다음과 같습니다.
$$ \text{LCM}(a_1, a_2, \dots, a_n) \times \gcd(a_1, a_2, \dots, a_n) = a_1 \times a_2 \times \dots \times a_n $$
직접 계산 방식의 한계
가장 직관적인 ...
8월 14일 12:44에 게시됨
BFS를 활용한 말 이동 최단 경로 분석
문제 요약
크기 n×m의 체스판에서 특정 위치 (x,y)에 있는 말이 각 위치로 이동하는 최단 거리를 계산해야 한다.
입력 형식
입력은 n, m, x, y 네 정수로 구성된다.
출력 형식
n×m 행렬 형태로 각 지점 도달 최단 거리를 출력한다(도달 불가 시 -1).
입력 출력 예시
입력 #1 ```
3 3 1 1
출력 #1 ```
0 3 2
3 -1 1
2 1 4 <br></br&g ...
8월 12일 10:18에 게시됨
C 언어를 활용한 다양한 알고리즘 구현
랜덤 숫자 생성 및 학번 출력
이 프로그램은 1부터 65 사이의 랜덤 숫자를 생성하고, 이를 기반으로 특정 형식의 학번을 출력합니다.
코드 보기
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define COUNT 5
int main() {
int randNum;
int index;
srand(time(0)); // 현재 시간을 시드로 설정
for (index = 0; ...
8월 11일 13:51에 게시됨
AtCoder Beginner Contest 386 문제 풀이
ABC386 문제 분석 및 풀이
A - Full House 2
주어진 네 개의 정수 A, B, C, D에 대해 추가로 하나의 정수 E를 선택하여 3+2 패턴을 만들 수 있는지 판단하는 문제입니다. 가능한 조합은 다음과 같습니다:
A = B, C = D, 그리고 B ≠ C인 경우
A = B = C, 그리고 C ≠ D인 경우
정렬 후 비교 로직을 통해 결과를 도출합니다. 아래는 구현 코드입니다:
// Problem: A - Full ...
8월 8일 11:53에 게시됨
양방향 정렬 문제 해결: Chtholly Tree 활용
Chtholly Tree를 사용할 수 있는데 와선 세그먼트 트리를 쓰겠는가?
:::align{right}
——저우 슈겐
:::
평균 \(O((n + m) \log m)\) 시간 복잡도를 가지는 Chtholly Tree 기반 해결 방안을 제시합니다.
문제 개요
초기 수열 \([1 \dots n]\)이 주어지며, m번의 정렬 연산을 수행합니다:
\(p = 0\): 앞 \(q\)개를 내림차순 정렬
\(p = 1\): \(q\)부터 \(n\)까지를 오름 ...
8월 6일 17:10에 게시됨
고정밀도 연산 기법
일반적으로 프로그래밍에서 정수형 타입(int, long long 등)으로 표현할 수 없는 매우 큰 수를 다룰 때 고정밀도 연산이 필요합니다.
고정밀도 연산의 핵심은 큰 수를 배열이나 문자열 등을 사용하여 각 자릿수를 개별적으로 저장하고, 이를 바탕으로 덧셈, 뺄셈, 곱셈, 나눗셈 등의 산술 연산을 직접 시뮬레이션하는 것입니다. 이는 마치 사람이 연필과 종이를 사용하여 ...
8월 6일 14:50에 게시됨
2차원 편순 문제를 활용한 레몬의 행복도 계산
레몬 나무에 n개의 레몬이 매달려 있으며, 각각은 두 가지 속성인 시각적 아름다움(a_i)과 신맛 강도(b_i)를 가진다. 특정 레몬 i를 섭취했을 때 얻는 기쁨 값 e_i는 자기 자신을 제외하고, 아름다움과 신맛 모두가 자신 이하인 다른 레몬들의 개수로 정의된다.
즉, 다음 조건을 동시에 만족하는 인덱스 j의 수이다:
j ≠ i
a_j ≤ a_i
b_j ≤ b_i
모든 레몬에 대해 ...
8월 4일 07:24에 게시됨