누에나방애벌레

1. 중위 표기법(Infix Notation)과 후위 표기법(Postfix Notation)중위 표기법 (Infix Notation)일반적으로 우리가 사용하는 수식 표현 방식입니다. 연산자가 피연산자 사이에 위치합니다.(3 + 4) * 510 + 2 * 6후위 표기법 (Postfix Notation)후위 표기법은 연산자가 피연산자 뒤에 위치하는 표현 방식입니다.3 4 + 5 *10 2 6 * +후위 표기법은 괄호 없이도 연산자의 우선순위를 명확하게 정의할 수 있습니다.  2. Shunting Yard Algorithm의 동작알고리즘의 목적은 중위 표기법으로 된 수식을 후위 표기법으로 변환하는 것입니다. 알고리즘은 두 개의 주요 자료 구조를 사용합니다:출력 큐: 결과로 나올 후위 표기법을 저장하는 큐.연산..

1. LIS (Longest Increasing Subsequence)의 정의최장 증가 부분 수열(LIS)이란, 주어진 수열에서 몇 개의 숫자를 골라서 만들 수 있는 가장 긴 증가하는 부분 수열을 의미합니다. 단, 부분 수열은 원래 수열에서 순서를 유지해야 합니다. 예를 들어, 수열이 {6, 2, 5, 1, 7, 4, 8, 3}이라면, 이 수열에서 LIS는 {2, 5, 7, 8}로 길이가 4가 됩니다.LIS 문제는 다양한 알고리즘으로 해결할 수 있지만, 이 중 이진 탐색을 활용하여 O(N log N) 시간 복잡도로 해결하는 방법이 가장 효율적입니다.2. 문제 해결 코드아래는 LIS 문제를 해결하는 C++ 코드입니다. 이 코드는 이진 탐색을 통해 효율적으로 LIS의 길이를 구하고 실제 LIS 수열을 추적하..

2차원 배열의 회전은 컴퓨터 과학에서 자주 사용되는 개념으로, 이미지를 회전하거나 게임 보드의 상태를 바꾸는 등 다양한 응용 사례에서 사용됩니다. 이번 포스트에서는 2차원 배열을 회전시키는 방법을 살펴보겠습니다. 이 방법은 주로 시계 방향과 반시계 방향의 90도 회전에 집중합니다.2차원 배열 회전의 기본 원리2차원 배열을 회전시키는 기본 개념은 특정 규칙에 따라 배열의 요소들을 이동시키는 것입니다. 회전 방향에 따라 요소들의 위치가 변경되며, 회전의 결과로 새로운 배열이 만들어집니다. 1. 시계 방향 90도 회전 (Clockwise 90-degree Rotation)2차원 배열을 시계 방향으로 90도 회전시키면, 배열의 각 요소는 다음과 같은 규칙에 따라 새로운 위치로 이동합니다.원래 배열의 좌표: (i..

배열을 회전시키는 방법에는 왼쪽 회전과 오른쪽 회전이 있습니다. 배열 회전은 배열의 요소들을 일정한 방향으로 이동시키고, 배열의 끝 요소들을 다시 시작 부분으로 이동시키는 작업입니다.i는 원래 배열의 인덱스입니다.k는 회전할 단계 수입니다.n은 배열의 길이입니다.왼쪽 회전 (Left Rotation)배열을 왼쪽으로 k만큼 회전시키면 각 요소의 새로운 위치는 (i - k + n) % n으로 계산됩니다.  오른쪽 회전 (Right Rotation)배열을 오른쪽으로 k만큼 회전시키면 각 요소의 새로운 위치는 (i + k) % n으로 계산됩니다.Code#include #include using namespace std;// 왼쪽 회전 함수void leftRotate(vector& arr, int k) { ..

재귀 함수는 프로그래밍에서 강력하고 유용한 도구입니다. 특히 DFS(깊이 우선 탐색)와 같은 알고리즘에서 재귀를 사용하여 문제를 해결할 수 있습니다. 이번 포스트에서는 재귀 함수의 기본 개념과 사용 시 주의사항, 그리고 실제 활용 예제를 소개하겠습니다.재귀 함수란?재귀 함수는 함수가 자신을 호출하는 함수입니다. 함수가 자신의 문제를 해결하기 위해 동일한 방식으로 자신을 호출함으로써 문제를 점진적으로 해결합니다. 재귀 함수는 주로 다음과 같은 두 가지 조건을 충족해야 합니다:기저 조건(Base Case): 함수가 더 이상 자기 자신을 호출하지 않고 직접 결과를 반환하는 조건입니다. 이를 통해 무한 호출을 방지합니다.재귀 조건(Recursive Case): 함수가 자신을 호출하여 문제를 더 작은 단위로 나누..

Greedy 알고리즘은 문제를 해결하는 데 있어 매우 빠르고 효율적인 방법 중 하나입니다. 이 알고리즘은 매 단계마다 현재 상황에서 가장 좋은 선택을 하는 방법을 택합니다. 그러나 Greedy 알고리즘이 항상 정답을 보장하지는 않기 때문에 사용 시 주의가 필요합니다.Greedy 알고리즘의 특징정답이라는 확신이 필요: Greedy 알고리즘을 사용할 때는 매 선택이 최종 결과에 대해 최적임을 확신할 수 있어야 합니다. 각 단계에서의 최적 선택이 전체 문제의 최적 해결책으로 이어지지 않는다면 Greedy 알고리즘은 올바른 결과를 보장하지 못합니다.반례가 있으면 사용 불가: Greedy 알고리즘을 사용하기 전에 반례가 있는지 확인해야 합니다. 만약 반례가 존재한다면, 이 알고리즘을 사용하면 올바른 해결책을 찾을..

1. 버블 정렬 (Bubble Sort)버블 정렬은 인접한 두 요소를 비교하여 정렬하는 간단한 알고리즘입니다. 두 요소를 비교하여 순서가 맞지 않으면 교환하는 방식으로, 배열의 끝까지 반복합니다. 이 과정이 전체 배열을 한 번 순회할 때마다 가장 큰 값이 맨 끝으로 이동합니다.동작 원리첫 번째 요소와 두 번째 요소를 비교합니다.두 번째 요소가 더 작으면 두 요소를 교환합니다.두 번째 요소와 세 번째 요소를 비교하여 같은 작업을 반복합니다.배열의 끝까지 이를 반복합니다.마지막 요소까지 도달하면 처음부터 다시 시작하여 이 과정을 반복합니다.코드 예제#include #include using namespace std;void bubbleSort(vector &arr) { int n = arr.size()..

방향 배열방향 배열은 2차원 평면에서 상하좌우 및 대각선 이동을 쉽게 구현하기 위한 배열입니다. 이를 통해 특정 좌표의 상하좌우 또는 대각선 방향으로의 이동을 간편하게 처리할 수 있습니다.상하좌우 방향 배열상: dy[0] = -1, dx[0] = 0하: dy[1] = 1, dx[1] = 0좌: dy[2] = 0, dx[2] = -1우: dy[3] = 0, dx[3] = 1#include using namespace std;int dy[4] = {-1, 1, 0, 0};int dx[4] = {0, 0, -1, 1};struct Point { int y; int x;};int map[4][4] = { {1, 3, 7, 2}, {2, 2, 6, 1}, {1, 4, 5, 1}, ..