정치,경제 블로그

글

라벨이 알고리즘인 게시물 표시

기술면접 - 문자열 뒤집기

4월 18, 2025

이 글에서는 C 언어를 사용해 문자열을 뒤집는 알고리즘을 설명합니다. 특히, 추가 메모리 없이 in-place로 해결하는 방법에 초점을 맞춥니다. 난이도: 1/10 근거: 투 포인터로 O(n) 시간, O(1) 공간. 가장 기본적인 알고리즘 문제로 구현이 매우 직관적. 문제 정의 주어진 문자열(예: "hello")을 뒤집어서 "olleh"로 만드는 알고리즘을 작성합니다. 추가 메모리를 최소화하거나 사용하지 않고 in-place로 해결할 수 있는지 알아봅니다. In-Place 문자열 뒤집기 C에서 문자열은 일반적으로 char 배열로 표현되며, 문자열의 끝은 널 문자( \0 )로 표시됩니다. In-place 알고리즘은 추가적인 배열을 할당하지 않고, 기존 배열 내에서 요소를 교환하여 문자열을 뒤집습니다. 아이디어는 다음과 같습니다: 문자열의 양 끝에서 시작해 중앙으로 이동하며 문자 쌍을 교환합니다. 문자열 길이가 n 일 때, n/2 번의 교환으로 충분합니다. 넓 문자( \0 )는 교환하지 않습니다. 알고리즘 코드 #include <string.h> void reverseString(char* str) { if (str == NULL) return; // 문자열 길이 계산 int len = strlen(str); if (len <= 1) return; // 양 끝에서 시작해 중앙으로 이동 for (int i = 0, j = len - 1; i < j; i++, j--) { // 문자 교환 char temp = str[i]; str[i] = str[j]; str[j] = temp; } } 코드 설명 ...

전체글 보기 »

기술면접 - Two Sum 문제 해결

4월 18, 2025

Two Sum 문제란? 난이도: 3/10 해시 테이블로 O(n) 해결 가능. 기본적인 자료구조 활용 문제로 초보자도 접근 가능. 최적화는 간단. Two Sum 은 대표적인 알고리즘 문제로, 정수 배열 nums 와 목표 합 target 이 주어졌을 때, 배열에서 두 숫자를 찾아 그 합이 target 이 되도록 하고, 해당 숫자들의 인덱스 를 반환하는 문제입니다. 조건은 다음과 같습니다: 각 입력에는 정확히 하나의 해답이 존재합니다. 같은 요소를 두 번 사용할 수 없습니다. 예시: 입력: nums = [2, 7, 11, 15] , target = 9 출력: [0, 1] (왜냐하면 nums[0] + nums[1] = 2 + 7 = 9 ) 왜 O(n) 시간 복잡도가 필요할까? 가장 직관적인 방법은 배열의 모든 숫자 쌍을 확인하는 것입니다. 하지만 이는 O(n²) 시간 복잡도를 가지므로 큰 배열에서는 비효율적입니다. 이를 개선하기 위해 해시 테이블 을 사용하면 O(n) 시간 복잡도로 문제를 해결할 수 있습니다. 해시 테이블은 숫자와 그 인덱스를 저장하여 빠른 조회를 가능하게 합니다. 해시 테이블의 작동 원리 해시 테이블을 사용한 Two Sum 해결 과정은 다음과 같습니다: 배열을 한 번 순회합니다. 각 숫자 nums[i] 에 대해: 보수 (complement, 즉 target - nums[i] )를 계산합니다. 해시 테이블에서 보수가 존재하는지 확인합니다. 보수가 있으면 해당 숫자의 인덱스와 현재 인덱스 i 를 반환합니다. 보수가 없으면 현재 숫자 nums[i] 와 그 인덱스 i 를 해시 테이블에 추가합니다. 이 방식은 배열을 단 한 번만 순회하므로 O(n) 시간 복잡도를 달성합니다. 코드 분석 위의 C 코드는 선형 탐사 (linear probing)를 사용한 해시 테이블로 Two Sum 문제를 해결합니다. 코드를 하나씩 살펴보겠습니다. 1. 해시 테이블 구조 typedef struct { ...

전체글 보기 »

정치,경제 블로그

글

추천글

2025 타임지 세계 영향력 100인에 포함된 한국인

기술면접 - 문자열 뒤집기

기술면접 - Two Sum 문제 해결