SEO

그리디(Greedy)란?문제를 해결할 때 각 단계에서 가장 최적인 선택을 하여 최종적인 해를 구하는 알고리즘입니다.이 알고리즘은 각 선택이 가장 좋은 선택이라고 믿고, 그 선택이 나중에 어떤 영향을 미칠지 고려하지 않습니다. 즉, 그 순간에 최적이라고 생각되는 답을 선택하는 방식입니다.그리디 알고리즘은 항상 최적의 해를 보장하지는 않지만, 특정 조건 하에서는 매우 효율적으로 작동합니다. 그리디 알고리즘의 특징부분 최적 해: 그리디 알고리즘은 각 단계에서 최적인 선택을 하는데, 이것이 전체 문제의 최적 해를 보장하는 것은 아닙니다.근사 해: 그리디 알고리즘은 때로는 전체 최적 해를 구하지 못하고 근사적인 해를 구하는 경우가 많습니다. 이 때문에 그리디 알고리즘은 최적화 문제에서 "근사 알고리즘"으로 분류되..

힙이란?완전 이진 트리 O 1 / \\ 2 3 / \\ / 4 5 6완전 이진 트리 O 1 / \\ 2 3 / \\ / \\ 4 5 6 7완전 이진 트리 X 1 / \\ 2 3 / / \\ 4 6 7(5가 없어서 완전 이진 트리가 아님)트리의 일종으로, 완전 이진 트리 형태의 자료구조입니다. 다음과 같은 특징을 가집니다.피라미드처럼 생긴 트리 구조부모 노드와 자식 노드 간의 특별한 규칙 존재가장 크거나 작은 값을 빠르게 찾을 수 있음더보기더보기완전 이진 트리마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있음마지막 레벨의 노드들은 왼쪽부터 차례대로 채워..

동적 프로그래밍(Dynamic Programming)이란?동적 프로그래밍(Dynamic Programming)은 작은 하위 문제로 나누어 그 결과를 저장해가며, 전체 문제를 해결하는 알고리즘 설계 기법입니다. 이를 통해 중복 계산을 줄여 계산 속도를 높이고 효율적으로 계산할 수 있습니다.  DP 기법을 적용시킬 수 있는 조건1. 중복되는 부분 문제(Overlapping Subproblems)동일한 작은 문제들이 반복하여 나타나는 경우, 반복적으로 같은 문제를 해결하는 성질입니다.2. 최적 부분 구조(Optimal Substructure)부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 성질로, 작은 문제의 최적해를 통해 큰 문제의 최적해를 구할 수 있습니다.  DP 문제 풀이 방법..

정렬이란? Key 값의 대소 관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업. - 오름차순정렬 : 키 값이 작은 데이터를 앞쪽에 놓은 경우 - 내림차순정렬 : 키 값이 큰 데이터를 앞쪽에 놓은 경우 안정된 정렬 : 같은 값의 키를 가진 요소의 순서가 정렬 전후에도 유지되는 것. 아래의 예시로 설명하자면 키란 5를 의미하고 요소는 하트와 스페이드를 의미한다. 오름차순으로 정렬하였음에도 (5,하트) 는 여전히 (5, 스페이드) 앞에 위치해있다. 내부 정렬 : 하나의 배열에서 작업할 수 있는 경우 사용하는 알고리즘 (버블, 선택, 삽입, 셸, 퀵, 병합, 힙, 도수 정렬 등등은 모두 내부정렬이다.) 외부 정렬 : 하나의 배열에서 작업할 수 없는 경우 사용하는 알고리즘 (외부 정렬은 내부..

재귀란? 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 '재귀적' 이라고 함. 직접 재귀와 간접 재귀 직접 재귀란 자신과 같은 함수를 호출하는 것. 간접 재귀란 함수 a가 함수 b를 호출하고, 다시 함수 b가 함수 a를 호출하는 구조이다. 재귀 알고리즘에 알맞은 경우 - 풀어야 할 문제가 재귀로 정의되는 경우 - 계산 할 함수가 재귀로 정의되는 경우 - 처리할 데이터 구조가 재귀로 정의되는 경우 유클리드 호제법 최대공약수는 y가 0이면 x이고, y가 0이 아닐 경우 gcd(y, x%y) 이다. 하향식 분석과 상향식 분석 하향식 분석이란 가장 위쪽의 함수 호출부터 시작해 계단적으로 자세히 조사해 가는 분석 기법으로 같은 함수의 호출이 여러번 나올 수 있기 때문에 경우에 따라 효율적..

1. 스택 스택이란? 데이터를 일시적으로 저장하기 위해 사용하는 자료구조로 후입선출 구조이다. 2. 큐 큐란? 데이터를 일시적으로 쌓아 두기 위한 자료구조로 선입선출 구조이다. - 인큐(enqueue) : 데이터를 넣는 작업 - 디큐(dequeue) : 데이터를 꺼내는 작업 - 프런트(front) : 데이터를 꺼내는 쪽 - 리어(rear) : 데이터를 넣는 쪽 링 버퍼란? 베열의 처음과 끝이 연결되어있는 자료구조로 기존 큐에서 발생하는 요소 이동 문제를 해결할 수 있다. - 요소의 개수가 n인 배열에 계속해서 데이터가 입력될 때 가장 최근에 들어온 데이터 n개만 저장하고 오래된 데이터는 버리는 용도로 사용 가능.

※ 용도나 목적, 실행 속도, 자료구조 등을 고려하여 알고리즘 선택 1-1. 검색 알고리즘 배열 검색에 사용되는 알고리즘 - 선형 검색 : 무작위로 늘어놓은 데이터 모임에서 검색을 수행 - 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행 - 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행 방법 1) 체인법 : 같은 해시 갑스이 데이터를 선형리스트로 연결하는 방법 방법 2) 오픈 주소법 : 데이터를 위한 해시 값이 충돌할 때 재해시하는 방법 1-2. 선형 검색 선형 검색(순차 검색)이란? 배열에서의 검색 : 원하는 키 값을 갖는 요소와 만날 때까지 맨 앞부터 순서대로 요소를 검색 ▷ 일반적으로 배열의 요소 개수가 n개일 때, 조건을 판단하는 횟수..

자료구조 : 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법. - 배열 : 같은 자료형으로 이루어진 요소가 모여 직선 모양으로 줄지어 있는 자료구조. | 상수식 : 상수만을 포함하는 식, 실행 시점이 아닌 컴파일 시점에 계산. | int a[5]; -> a[0]의 자료형은 int, 배열 a의 자료형은 int[5]형. - C언어 메모리 구조 : 프로그램이 실행될 때마다 RAM(메모리 영역)에 할당. | 데이터 영역 : 전역 변수와 정적 변수 할당, 프로그램 시작 시 할당하고 종료 시 메모리에서 해제. | 스택 영역 : 지역 변수와 매개변수 저장, 함수 호출 완료 시 사라짐. | 힙 영역(빈 공간) : 필요에 따라 동적 메모리 할당. - 난수 생성 | rand() : 이 함수가 반환하는 값은 0 ..