정치,경제 블로그

문제 개요 정렬된 배열이 주어졌을 때, 중복된 요소를 제거하여 각 요소가 한 번씩만 나타나도록 하고 새로운 배열의 길이를 반환해야 합니다. 이 작업은 제자리(in-place) 알고리즘으로 수행해야 하며, 추가 메모리 사용은 O(1)로 제한됩니다. 제약 조건: 입력 배열은 오름차순으로 정렬되어 있습니다. 0 ≤ 배열 길이 ≤ 3 * 10⁴ -100 ≤ 배열 요소 ≤ 100 예제: 입력: nums = [1,1,2] 출력: 2, nums = [1,2,_] 입력: nums = [0,0,1,1,1,2,2,3,3,4] 출력: 5, nums = [0,1,2,3,4,_,_,_,_,_] C 언어 구현 아래는 정렬된 배열에서 중복을 제거하는 제자리 알고리즘의 C 언어 구현입니다. #include int removeDuplicates(int* nums, int numsSize) { // 예외 처리 if (numsSize == 0) return 0; // 고유 요소를 저장할 위치 포인터 int writeIndex = 1; // 두 번째 요소부터 배열 순회 for (int readIndex = 1; readIndex < numsSize; readIndex++) { // 현재 요소가 이전 요소와 다르면 if (nums[readIndex] != nums[readIndex - 1]) { // writeIndex 위치에 복사 nums[writeIndex] = n...

팰린드롬 확인 (Check if a String is a Palindrome) 이 글에서는 C언어를 사용하여 문자열이 팰린드롬인지 확인하는 방법을 자세히 설명합니다. 팰린드롬이란, 문자열을 뒤집어도 동일한 문자열을 의미합니다. 예를 들어, "radar"나 "A man a plan a canal Panama"는 팰린드롬입니다. 이 글에서는 공백과 대소문자 처리 방법, 그리고 코드 최적화 방안까지 다룹니다. 1. 팰린드롬이란? 팰린드롬(Palindrome)은 문자열을 처음부터 읽거나 끝에서부터 읽었을 때 동일한 결과를 내는 문자열입니다. 예를 들어: "racecar" → 팰린드롬 "A level eye level A" → 공백과 대소문자를 무시하면 팰린드롬 "hello" → 팰린드롬 아님 문제는 공백, 대소문자, 특수문자 등을 어떻게 처리할지에 따라 복잡도가 달라집니다. 2. 문제 정의 주어진 문자열이 팰린드롬인지 확인하는 프로그램을 작성해야 합니다. 다음 조건을 만족해야 합니다: 대소문자를 구분하지 않음 (예: 'A'와 'a'는 동일하게 처리). 공백과 특수문자를 무시 (알파벳과 숫자만 고려). 효율적인 알고리즘으로 처리 (O(n) 시간 복잡도 목표). 3. C언어 구현 아래는 위 조건을 만족하는 C언어 코드입니다. 이 코드는 입력 문자열을 받아 팰린드롬 여부를 판단합니다. #include <stdio.h>...

단일 연결 리스트를 역순으로 만드는 것은 컴퓨터 과학에서 중요한 문제로, 코딩 인터뷰와 데이터 구조 강의에서 자주 등장합니다. 단일 연결 리스트는 각 노드가 값과 다음 노드를 가리키는 포인터를 포함하는 선형 데이터 구조입니다. 마지막 노드는 NULL 을 가리킵니다. 리스트를 역순으로 만들면 마지막 노드가 첫 번째 노드가 되고, 그 다음 노드가 두 번째가 되는 식으로 순서가 바뀝니다. 이 글에서는 단일 연결 리스트를 역순으로 만드는 두 가지 일반적인 방법인 반복적 방법과 재귀적 방법을 C 언어로 구현합니다. C 코드 예제와 함께 두 방법의 차이점을 자세히 설명합니다. 난이도: 3/10 근거: 반복/재귀 모두 O(n) 시간. 포인터 조작이 약간 까다로울 수 있지만, 기본적인 링크드 리스트 문제. 1. 단일 연결 리스트 이해하기 알고리즘을 살펴보기 전에 단일 연결 리스트의 구조를 간단히 알아보겠습니다. 값이 1, 2, 3, 4인 노드로 구성된 리스트를 예로 들어 보겠습니다: 원래 리스트 : 1 -> 2 -> 3 -> 4 -> NULL 역순 리스트 : 4 -> 3 -> 2 -> 1 -> NULL 각 노드는 다음과 같은 필드를 가집니다: data : 노드의 값(예: 1, 2, 3, 4) next : 다음 노드를 가리키는 포인터(마지막 노드에서는 NULL ) 목표는 이 next 포인터의 방향을 바꿔 리스트를 역순으로 만드는 것입니다. 2. 반복적 방법 반복적 방법은 세 개의 포인터를 사용하여 리스트를 한 번 순회하며 링크를 역순으로 변경합니다. 이 방법은 메모리 사용이 적고 효율적입니다. 단계: 세 개의 포인터를 초기화합니다: previous :...

이 글에서는 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 문제란? 난이도: 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 {  ...