코딩 면접 문제 풀이 모음
두 수의 합 구하기
정수 배열이 주어졌을 때, 지정된 합계가 되는 두 개의 요소를 찾는 문제를 해결해 보겠습니다. 먼저 기본 접근법의 시간 복잡도를 분석한 후, O(n) 알고리즘으로 개선하겠습니다.
def solve():
data = [11, 7, 45, 67, 134, 5, 83, 55, 106, 33, 57, 82, 6, 24, 87, 61, 3, 39, 6, 26]
target = 13
result, a, b = find_pair(data, targe ...
6월 13일 22:41에 게시됨
ABC363 문제 풀이
A - 값의 범위
주어진 값 r이 어느 범위에 속하는지 확인하고, 그 범위의 상한에서 r을 뺀 값을 출력하면 된다.
100 미만이면 100-r, 200 미만이면 200-r, 300 미만이면 300-r을 출력한다.
코드 확인하기
#include<bits/stdc++.h>
using namespace std;
int main() {
int r;
cin >> r;
if(r < 100) {
cout << 100 - r;
...
6월 13일 16:20에 게시됨
AtCoder 초보자 대회 450 (ABC450)
A - 3,2,1,GO
값을 입력받은 후 1부터 입력값까지 반복하여 출력합니다.
코드 보기
#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
cin >> n;
for(int i = n; i > 1; --i)
cout << i << ',';
cout << 1;
return 0;
}
B - Split Ticketing
a, b, c를 모두 반복하며 조건을 검사합니다. 조 ...
6월 12일 19:32에 게시됨
행렬 곱셈과 고속 지수 연산
행렬의 기초
기본 개념
행렬은 행과 열로 구성되는 2차원 배열이다. n×m 행렬은 n개의 행과 m개의 열을 가진 구조를 의미한다.
두 행렬을 곱할 때는 첫 번째 행렬의 열 개수와 두 번째 행렬의 행 개수가 반드시 일치해야 한다. 예를 들어, 2×3 행렬과 3×4 행렬을 곱하면 결과는 2×4 행렬이 된다.
[A_{a \times n} \times B_{n \times m} = C_{a \times m}]
행렬 곱셈의 ...
6월 11일 19:01에 게시됨
동적 계획법을 활용한 상태 머신 기반 문제 해결 전략
동적 계획법(Dynamic Programming)에서 상태 머신(State Machine) 개념을 도입하면 복잡한 의사결정 과정을 간결한 상태 전이 방정식으로 변환할 수 있습니다. 각 단계에서의 선택지를 상태로 정의하고, 이전 상태로부터 현재 상태로 도달하는 최적 경로를 계산하는 세 가지 사례를 살펴봅니다.
1. 인접한 항목을 선택할 수 없는 경우 (도둑 문제)
연속된 상점을 ...
6월 10일 16:04에 게시됨
Xorshift 기반 난수 배열 생성과 선형 시간 선택 알고리즘 활용
알고리즘 대회에서 자주 등장하는 난수 배열 생성 방식과 std::nth_element를 활용한 효율적인 문제 해결 기법을 살펴본다. 특히 대용량 데이터에서 순위 기반 쿼리를 처리하는 방법이 핵심이다.
Xorshift RNG 구현
다음은 경량 의사난수 생성기(Pseudo-Random Number Generator)의 한 종류인 xorshift 계열 구현이다. 세 개의 상태 변수를 이용하며, 비트 연산으로 빠르 ...
6월 8일 21:35에 게시됨
그래프 순회 알고리즘: 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)
너비 우선 탐색 (Breadth-First Search, BFS)
너비 우선 탐색은 시작 정점으로부터 가까운 노드를 우선적으로 탐색하는 알고리즘으로, 이진 트리의 레벨 순회(Level-order traversal) 방식과 유사합니다. 탐색 과정에서 큐(Queue)를 사용하여 정점을 관리하고, 방문 여부를 기록하기 위한 불리언 배열을 사용합니다.
시작 정점을 큐에 넣고 방문 처리한 뒤, 큐가 ...
6월 8일 16:40에 게시됨
NOIP 2012 차량 여행 문제 해결: 양방향 연결 리스트와 이진 리프팅 최적화
문제 개요
NOIP 2012 심화 그룹의 '차량 여행' 문제는 두 운전자 A와 B가 번갈아 가며 동쪽(도시 번호가 증가하는 방향)으로 이동할 때의 경로를 시뮬레이션하고 최적의 출발지를 찾는 문제입니다.
운전 규칙: A가 먼저 운전하고 B가 다음에 운전하는 방식으로 번갈아 진행합니다.
도시 선택 기준:
운전자 B: 현재 도시와 해발 고도 차이의 절댓값이 가장 작은 도 ...
6월 8일 01:37에 게시됨
Java 알고리즘 풀이: 텐센트 2018 상반기 채용 기출 문제
문제 1: 교차 부호 수열의 합
길이 n의 연속된 정수 수열 1, 2, 3, ... n에 대해, 매 m개마다 부호를 교차시키는 수열을 정의합니다. 초기 부호는 음수(-)이며, 부호는 -, -, ..., +, +, -, -, ... 순서로 반복됩니다. 이때 처음 n개 항의 총합을 구하는 문제입니다.
입력 조건: 두 정수 n, m (2 ≤ n ≤ 10⁹, 1 ≤ m), n은 2m으로 나누어 떨어짐
출력: 처음 n개 항의 합
...
6월 6일 22:56에 게시됨
CrCPC 2024 알고리즘 솔루션 가이드
문제 A: 인공지능의 종료 시나리오
이 문제는 상태 간의 전이를 효율적으로 관리하는 것이 핵심입니다. 주어진 값들의 분포를 압축하여 중복을 제거하고 (좌표 압축), 각 단계마다 가능한 최소 이동 횟수를 계산합니다. 전체적인 시간 복잡도는 로그 스케일을 가지므로 \(O(N \log N)\) 입니다.
// 참조 구현 코드
#include <bits/stdc++.h>
using namespace std;
...
6월 5일 01:01에 게시됨