이진 탐색과 다양한 활용 사례
704. 이진 탐색 기본
정렬된 배열에서 특정 값을 찾을 때 이진 탐색을 사용할 수 있습니다. 중앙값을 기준으로 탐색 범위를 절반씩 줄여나가는 방식입니다.
class BinarySearch:
def find_index(self, nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid ...
9월 27일 20:41에 게시됨
이진 탐색과 요소 제거 알고리즘 실습
기초 개념
자료구조: 배열
알고리즘: 이진 탐색, 양방향 포인터(투포인터)
주요 오류 피하기 팁
변수의 활용을 최대한 활용하고, 목적에 맞게 명확하게 정의하세요.
조건 비교 연산자(==, !=)의 논리는 항상 명확히 처리하세요.
배열 인덱스 접근 시 범위를 초과하지 않도록 주의하세요. 특히 반복문의 종료 조건을 신중히 설정해야 합니다.
704. 이진 탐색 (Binary ...
9월 25일 00:48에 게시됨
여행 계획과 동전 문제 해결
여행 계획
여행 경로 최적화 코드를 살펴보겠습니다.
#include <iostream>
using namespace std;
long long capacity[1000200], demand[1000200], sum[1000200], queue[1000200], visited[1000200];
int main() {
int n;
cin >> n;
for (long long i = 1; i <= n; i++) cin >> capacity[i] >> demand[i];
for (long long i = ...
9월 21일 16:42에 게시됨
데이터 구조와 알고리즘의 기본 개념
데이터 구조의 핵심 개념
데이터 구조 관련 용어
데이터
정의: 정보를 담는 매체로, 기호들의 집합입니다. 컴퓨터 프로그램이 처리하는 원재료 역할을 합니다.
데이터 요소
정의: 데이터의 기본 단위로, 일반적으로 하나의 완전한 개체를 의미합니다.
데이터 항목: 데이터 요소를 구성하는 더 이상 분할할 수 없는 최소 단위입니다.
예시: 학생 정보는 하나의 데이 ...
9월 15일 09:19에 게시됨
알고리즘 문제 해결: ACM 천재
수학적 분석
이 문제의 중요한 성질은 다음과 같습니다: 만약 \(0<a<b<c<d\)라면, \((a-d)^2+(b-c)^2 > (a-c)^2+(b-d)^2\)
증명:
두 식을 각각 1식과 2식으로 설정합니다.
\((a-d)^2+(b-c)^2 = a^2+b^2+c^2+d^2-2ad-2bc\), \((a-c)^2+(b-d)^2 = a^2+b^2+c^2+d^2-2ac-2bd\)
\(a*(c-d) > b*(c-d)\)이므로, \(-2ad-2bc > -2ac-2bd\)
따라서 \(a^2+b^2+c ...
9월 1일 05:07에 게시됨
배열에서 최대값과 최소값 효율적으로 찾기
배열은 가장 기본적인 선형 데이터 구조입니다. 배열에서 최대값과 최소값을 찾아야 할 때, 어떤 방법으로 효율적으로 찾을 수 있을까요? N개의 정수로 이루어진 배열에서 최대값과 최소값을 찾기 위해 몇 번의 비교가 필요할까요?
예를 들어 N=8인 배열 {5, 6, 8, 3, 7, 9, 1, 2}가 있다고 가정해 봅시다.
방법 1: 개별 탐색
최대값 찾기와 최소값 찾기를 별개의 문제로 ...
8월 30일 18:36에 게시됨
LeetCode 문제 풀이: 두 수의 합
두 수의 합 문제:
주어진 정수 배열 nums와 대상 값 target에서 배열 중 두 수를 찾아 합이 target인 두 수의 인덱스를 반환해야 합니다. 배열의 같은 원소를 반복해서 사용할 수 없습니다.
주어진 입력값은 하나의 정답을 가지며, 하나의 정답만 있을 것입니다.
예제:
nums = [2, 7, 11, 15], target = 9
nums[0] + nums[1] = 2 + 7 = 9
따라서 [0, 1]을 반환합니다. ...
8월 30일 04:58에 게시됨
알고리즘 문제 해결: Codeforces A-E 문제 분석 및 해법
이 문서는 Codeforces 경쟁 프로그래밍 플랫폼의 특정 라운드에서 제시된 문제들(A부터 E까지)에 대한 해설과 해결 전략을 다룹니다. 각 문제의 접근 방식과 구현 코드를 상세히 설명합니다.
A. 파이값 일치 확인
주어진 문자열이 원주율(π)의 특정 자릿수와 얼마나 일치하는지 찾아야 하는 문제입니다. 여기서는 π 값의 문자열 표현이 미리 정의되어 있으며, ...
8월 28일 08:30에 게시됨
백트래킹을 활용한 IP 복원 및 부분집합 문제 해결
93. 유효 IP 주소 복원하기
문제는 주어진 숫자 문자열에서 올바른 IP 주소를 생성하는 것입니다. 유효한 IP는 다음과 같은 조건을 만족해야 합니다:
총 네 개의 정수로 구성되며 각각은 0~255 범위에 있어야 함
각 정수는 선행 0을 포함할 수 없음 (예: "01", "00")
정수 간에는 점(.)으로 구분됨
이 문제는 문자열을 분할하는 형태로 백트래킹 알고리즘을 적용하여 모 ...
8월 27일 00:11에 게시됨
알고리즘 문제 풀이: 제곱 정렬, 최소 부분 배열, 나선형 행렬
997. 정렬된 배열의 제곱 계산
입력된 비내림차순 정수 배열의 각 원소 제곱값을 오름차순으로 반환하는 문제입니다. 원소에는 음수가 포함될 수 있습니다.
무차별 대입 방식: 각 원소의 제곱을 계산한 후 Arrays.sort()로 정렬합니다.
양방향 포인터 방식: 제곱값이 가장 큰 값이 배열 양 끝에 위치한다는 특성을 활용합니다. 두 포인터를 배열 양 끝에 두고 비교하며 결 ...
8월 20일 05:50에 게시됨