JaehyeonByun

계산 복잡도 분석은 문제를 해결할 수 있는 모든 알고리즘의 효율성을 평가하고, 해당 문제의 하한(Ω)을 결정하는 과정이다. 예를 들어, 행렬 곱셈 문제의 일반 알고리즘은 Θ(n3)의 시간복잡도를 가지며, 개선된 알고리즘으로는 쉬트라쎈 알고리즘 (Θ(n2.81))과 위노그라드 알고리즘 (Θ(n2.38))이 존재한다. 하지만, 이 문제의 계산 복잡도 하한은 Θ(n2)로 알려져 있으나, 이만큼 효율적인 알고리즘은 아직 발견되지 않았다. 이는 하한보다 효율적인 알고리즘을 만드는 것이 불가능함을 의미하며, 예를 들어 3×3 행렬 곱셈에서는 기존 방식으로는 27번의 연산이 필요하지만, 개선된 알고리즘은 이를 줄일 수 있음을 보여준다. 계산 복잡도에서 문제의 복잡도 하한이 Ω(f(n))인 경우, 시간 복잡도가 Θ(f..

1. 백트레킹 (Back Tracking) 백트래킹(backtracking) 알고리즘은 탐색 문제를 해결하는 기법으로, 상태공간트리를 깊이우선탐색(DFS) 방식으로 탐색하면서 유망하지 않은 노드(non-promising node)를 가지치기(pruning) 하여 탐색 범위를 줄인다. 이 알고리즘은 탐색 중간에 해답이 나올 가능성이 없는 경로를 제거해 효율성을 극대화한다. 더보기깊이 우선 탐색 (Depth-First Search, DFS)  깊이우선탐색(Depth-First Search; DFS)은 트리나 그래프 구조에서 루트 노드(또는 시작 노드)부터 시작하여, 자식 노드를 깊게 탐색한 후 더 이상 자식 노드가 없을 때 부모 노드로 되돌아오는 방식으로 진행하는 탐색 알고리즘이다. 이는 주로 재귀적으로 구..

1. 동적 계획법 (Dynamic Programming) 지금까지 알고리즘의 기본 원리와 분할 정복 알고리즘에 대해 배웠다. 분할 정복 알고리즘은 하향식(top-down) 접근 방식을 통해 문제를 해결하며, 나누어진 부분 문제들 간에 상관관계가 없는 경우에 적합하다. 그러나 피보나치 수열 계산과 같은 경우, 분할된 문제들이 서로 연관되어 있어 같은 항 f(i)를 여러 번 계산하게 된다. 이로 인해 효율성이 저하되므로, 분할 정복법은 피보나치 알고리즘과 같은 연관된 문제를 해결하는 데 적합하지 않다.  동적 계획법(dynamic programming)은 상향식(bottom-up) 접근 방식을 사용하는 알고리즘으로, 문제를 나눈 후 각 부분 문제를 먼저 해결하는 방식이다. 이 방법은 인덱스를 효과적으로 설정..

지금까지 C++ 문법을 통해 프로그래밍 언어의 기본적인 구문과 기능을 익히고, 객체지향 프로그래밍을 통해 소프트웨어의 구조와 설계를 이해하며, 자료구조를 통해 데이터를 효율적으로 관리하는 방법을 배웠다. 이제는 알고리즘을 통해 실제로 어떻게 데이터를 어떻게 문제를 해결할 것인지 배울 차례이다. 이를 통해 문제 해결에 필요한 논리적 사고와 최적화 기술을 더 깊이 있게 적용하여 효율적이고 유지보수 가능한 소프트웨어를 개발할 수 있을 것이다.  알고리즘(Algorithms)은 특정 문제를 해결하기 위해 명확하게 정의된 일련의 절차나 단계들을 의미한다. 알고리즘은 주어진 입력을 처리하여 원하는 출력으로 변환하는 방법을 체계적으로 설명하며, 컴퓨터 과학, 수학, 데이터 처리, 인공지능 등 다양한 분야에서 사용된다..

List​리스트는 순서가 있는 값들의 모음이다.선형 관계 (Linear Relationship) : 첫 번째 요소를 제외 한 각 요소에는 고유한 선행 요소가 있고 마지막 요소를 제외한 각 요소에는 고유 한 후속 요소가 있다길이 (Length) : list 안의 아이템의 개수; 길이는 프로그램 실행에 따라 달라질 수 있다.​Unsorted list vs Sorted list​1. Unsorted list : 데이터 항목들이 특정 순서 없이 저장되며 데이터 요소 간의 유일한 관계는 앞 요소과 뒤 요소 간의 관계이다. 즉, 어떤 데이터 뒤에 어떤 데이터가 있는지만 알 수 있고, 데이터 자체의 값에 따라 어떤 순서로 배열되어 있는지 알 수 없다.2. Sorted list : 데이터 항목들이 특정 키(key) 값..

Data Design and Implementation​Data type​Data : 데이터는 프로그래밍 세계의 명사로 객체는 조작되는 대상, 정보는 처리되는 대상이다. C++는 다양한 데이터 유형을 제공하며 기본적인 데이터 유형은 크게 내장 유형과 복합 유형이 있다.​내장 유형내장 유형은 프로그래밍 언어에 기본적으로 제공되는 데이터 유형이다. 프로그래머가 직접 정의하지 않고도 사용할 수 있는 유형이며, 일반적으로 언어의 가장 기본적인 데이터 요소를 나타낸다. 숫자형 , 문자열형, 논리형 , 불린형, 배열형, 객체형 등이 있다.​복합 데이터 유형(Composite Data Type)복합 데이터 유형은 여러 개의 기본 데이터 유형을 결합하여 만들어진 데이터 유형으로 기본 데이터 유형을 조합하여 더 복잡한 ..

기존의 절차지향 프로그래밍은 데이터와 함수가 분리되어 있어 프로그램의 구조가 복잡해지고 유지보수가 어려워지는 단점이 있었다. 이러한 문제를 해결하기 위해 객체지향 프로그래밍(OOP)이 등장하였으며, 이는 객체를 중심으로 소프트웨어를 구성하는 방법이다. OOP는 데이터를 포함한 객체를 통해 관련된 기능을 묶어 관리함으로써 코드의 재사용성과 모듈화를 촉진하고, 프로그램의 이해도를 높인다. Unity를 예를 들면, Player라는 클래스를 정의하고 이 클래스에 체력이나 점수같은 멤버 변수들을 포함시키고 TakeDamage()와 IncreaseScore()와 같은 멤버 함수를 통해 플레이어의 상태와 행동을 관리할 수 있다. 이러한 방식으로 각 객체는 자신만의 속성과 기능을 가지게 되어, 복잡한 게임 시스템을 보..

C++는 1979년 Bjarne Stroustrup이 개발한 객체지향 프로그래밍 언어로, C 언어의 성능을 유지하면서도 고급 언어 기능을 확장해 더 효율적이고 구조적인 코드 작성을 가능하게 한다. C++는 클래스, 상속, 다형성, 캡슐화 같은 객체지향 프로그래밍(OOP) 개념을 도입해 코드의 재사용성과 유지보수성을 높이며, 템플릿 기능을 통해 제네릭 프로그래밍을 지원해 코드의 유연성을 강화한다. C++는 또한 저수준 메모리 관리가 가능해 운영체제, 게임 엔진, 그래픽 처리 등 고성능 응용 프로그램 개발에 널리 사용되며 표준 라이브러리(STL)를 통해 다양한 자료구조와 알고리즘을 내장하여 개발 효율을 높인다. 본격적인 시작에 앞서 C++의 기본 문법을 정리할 것이다.1. 변수와 자료형 변수(Variable..

객체지향 프로그래밍(OOP)과 자료구조, 알고리즘은 프로그래밍의 기반을 구성하는 중요한 개념으로, 이를 이해하는 것은 복잡한 소프트웨어 시스템을 설계하고 효율적인 문제 해결을 가능하게 한다. 객체지향 프로그래밍(OOP)은 코드 재사용과 유연한 확장을 돕는 방법론이다. 예를 들어, C++에서 Animal이라는 추상 클래스를 정의한 후, 이를 상속받아 Dog, Cat 등 세부적인 동물 클래스를 만들면 코드 중복을 줄이고 특정 기능을 확장할 수 있다. 이런 구조는 유지보수 시 변경 범위를 최소화하며, 각각의 객체가 데이터를 포함하면서 동작을 독립적으로 관리하므로 협업과 테스트 과정에서도 효과적이다. 자료구조는 데이터를 논리적이고 효율적으로 저장하고 관리할 수 있도록 돕는 구조를 제공한다. 각 자료구조는 용도에..