티스토리

A Game Programmer
검색하기

블로그 홈

A Game Programmer

devshovelinglife.tistory.com/m

Main skill stack => Unity C# / Unreal C++ Studying Front / BackEnd, Java Python

구독자
16
방명록 방문하기
공지 Source Code 좌측 상단에 복⋯ 모두보기

주요 글 목록

  • 외판원 순회 (TSP) 알고리즘 개념 외판원 순회 문제 (Traveling Salesman Problem)는 조합 최적화 문제의 일종이다. 브루트 포스로 해결한가지 정말정말 무식한 방법이 있긴 하다. n개의 점들을 도는 순서를 순열을 통해 구해놓고, 그 경로를 따라 가면서 거리를 구하는 것이다. 하지만 알다시피, n개 점들의 순열의 경우의 수는 n!개이다... n이 20만 되어도 2,432,902,008,176,640,000가지, 한국말로 '243경' 개의 경우의 수를 따져 주어야 한다.동적 계획법으로 해결1~n번 도시가 있고, 이 중 몇 개의 도시를 거친 후에 지금 판매원이 i번 도시에 있다.그럼, 이 중에서 거쳐오지 않았던 도시들 중에서 다음 도시를 정해야 한다.우리는 다음 도시로 이동했다고 '가정' 하는 방식을 사용할 것이다.좀 더 이.. 공감수 0 댓글수 0 2025. 4. 2.
  • 실수형 (float) 자료형의 메모리 구조, 실제로 변환해보기 exponent : 지수부 (지수 부분)matissa : 기수부 (분수 부분) float형 실수의 전체 구조 IEEE 754 표준은 binary32에 대해 다음과 같이 명시한다.부호 비트 : 1 비트지수부 비트 : 8 비트가수부 비트 : 정밀도는 24 비트 (실제로 메모리엔 23 비트로 표현) 부호부 1 비트는 실수값이 양수일 때 0, 음수일 때 1로 표현된다. 지수부 8 비트를 unsigned char로 봤을 때, 실제 값에서 127을 더한 값을 저장하며 저장된 값의 범위는 다음과 같다.stored bits :    0    actual value :  -127 (실제 지수값을 표현하는 것이 아닌 특정 의미가 있음)stored bits :    1    actual value :  -126stored .. 공감수 0 댓글수 0 2025. 3. 23.
  • float 자료형의 메모리 구조 (컴퓨터의 실수 표현) 실수형은 IEEE의 부동소수점 형식을 사용하는데 4바이트(32비트) 표현의 경우 아래와 같이 이루어져 있다. 정수의 경우 2의 보수법을 이용해서 간단하게 메모리에 저장된 비트를 확인할 수 있지만 실수는 조금 더 복잡하다.아래의 단계를 거치면 실수가 메모리에 어떻게 표현이 되는지 알 수 있다. 위에 나와있는 -101.625를 컴퓨터의 표현 방법으로 바꿔보겠다1단계 - 이진수로 바꾸기이진수로 바꾸기 위해서는 나눗셈과 곱셈을 하면 된다. 일단 부호를 제외하고, 정수 부분은 2로 나누기를 연속으로 해서 2진수로 바꿔주자 101/2 = 50 ... 150/2 = 25 ... 025/2 = 12 ... 112/2 = 6 ... 06/2 = 3 ... 03/2 = 1 ... 1 정수 부분은 1100101 이다. 소수.. 공감수 1 댓글수 0 2025. 3. 23.
  • [C++] 조합 (Combination) 구할 수 있는 알고리즘 개념n개의 값 중에서 r 개의 숫자의 순서를 고려하지 않고 나열한 경우의 수, 순열은 반대로 고려한다. 예시) [1,2] 와 [2,1] 이 있을 때 동일하게 여긴다는 의미계산식으로는 nCr 이라고 표현한다.nCr= nPr / r!= n! / ((n-r)! * r!)예시로 서로 다른 3개의 숫자(1,2,3) 중 중복되지 않으면서 순서와 관계 없이 2개를 뽑는다고 가정해보자3C2= 3! / 1! * 2!= 3! / 2!= (3x2x1) / (2x1)= 3로 총 3개의 경우의 수가 나오게 된다 (1,2 / 1,3 / 2,3) 조합의 점화식 n-1Cr-1 + n-1Crn-1Cr-1 : 어떤 특정한 원소를 포함시키고 뽑았을 때n-1Cr : 어떤 특정한 원소를 포함시키지 않고 뽑았을 때예시){1,2,3} 에서 3C.. 공감수 0 댓글수 0 2025. 3. 12.
  • [C++] multimap 값 가져오기 #include #include using namespace std;int main(){ multimap a; a.insert(pair(1, 2)); a.insert(pair(1, 2)); a.insert(pair(2, 4)); cout ::iterator it = a.begin(); it != a.end(); ++it) cout first second first second 공감수 0 댓글수 0 2025. 3. 3.
  • 논 블로킹 알고리즘 (Non-blocking Algorithms) 개념동시성에서의 논 블로킹 알고리즘이란 쓰레드간의 공유된 상태(자원)로의 접근을 서로 중단없이 수행하는 것이다. (어떤 알고리즘에서 한 쓰레드의 정지가 여기에 관련된 다른 쓰레드의 정지를 유발하지 않는다)블로킹 동시성 알고리즘A: 쓰레드에 의해 요청된 동작을 수행 - 또는B: 쓰레드가 동작을 수행할 수 있을 때까지 대기 많은 종류의 블로킹 알고리즘과 동시성 블로킹 자료구조가 있다. 예를 들어, java.util.concurrent.BlockingQueue 인터페이스의 구현체들은 모두 블로킹 자료구조이다. 쓰레드가 BlockingQueue에 요소를 삽입하려 하는데 큐에 공간이 없다면 쓰레드는 공간이 생길 때까지 대기한다. 다음 다이어그램은 공유된 자료구조를 보호하는 블로킹 알고리즘의 동작을 보여준다.논 블.. 공감수 1 댓글수 1 2025. 2. 16.
  • 블로킹과 논블로킹 큐 (Blocking/Non-Blocking Queue) 1. BlockingQueue- Queue가 꽉 찼을 때의 삽입 시도 / 비어 있을 때의 추출 시도를 막는다- 구현체 모두 Thread-safe 하다 1) ArrayBlockingQueue- 고정 배열에 일반적인 Queue를 구현한 클래스- 생성 후 크기 변경 불가 2) LinkedBlockingQueue- 선택적으로 Bound가 가능한 LinkedList로 구현한 Queue 3) PriorityBlockingQueue- PriorityQueue와 같은 정렬 방식을 지니는 용량 제한이 없는 Queue 4) SynchrousQueue- Queue 내부로의 insert 작업이 다른 쓰레드의 remove 작업과 반드시 동시에 일어나야 한다.  2. Non Blocking Queue1) ConcurrentLin.. 공감수 0 댓글수 0 2025. 2. 16.
  • 최장 증가 수열 (LIS, Longest Increasing Subsquence) 최장 증가 수열, 정확히 최장 증가 부분 수열은 어떠한 수열에서 오름차순으로 증가하는 가장 긴 부분수열을 의미한다. 이 때, 부분 수열의 각 수는 서로 연속할 필요는 없다.아래의 예시 수열을 보자. 위 수열에서 최장 증가 수열을 찾으면 아래와 같다. 그림에서 붉은 칸으로 칠해진 부분 수열 (1, 2, 3, 6, 7, 9) 는 전체 수열 중 오름차순으로 증가하는 가장 긴 부분수열이다.이제 주어진 수열에서 LIS의 길이를 구하는 두 가지 방법을 알아보자.다이나믹 프로그래밍을 이용한 방법 : O(N^2)이러한 최장 증가 수열을 찾는 가장 단순한 방법은 완전 탐색일 것이다.하지만 수열에 존재하는 수의 개수가 k개일 때, 1개 이상의 원소를 갖는 모든 부분수열의 가짓수는 2^k개이므로, 모든 부분수열을 확인해 이.. 공감수 0 댓글수 0 2024. 11. 8.
  • RIP, OSPF, BGP 장단점 RIP (Routing Information Protocol), OSPF (Open Shortest Path First) 및 BGP (Border Gateway Protocol)는 모두 동적 라우팅 프로토콜이다.RIP - 거리 벡터 라우팅 프로토콜라우터가 인접한 이웃과 정보를 교환하면서 전체 네트워크에 대한 정보를 점차 완성해 나가는 방식이다. 장점)구성이 간단하다작은 네트워크에서 잘 작동한다단점)홉수 제한이 15개로 작다수렴 속도가 느리다무한 계산 문제가 발생할 수 있다OSPF - 링크 상태 라우팅 프로토콜라우터가 전체 네트워크의 상태 정보를 가지고 있으며, 이를 기반으로 최단 경로 트리를 계산하여 최적의 경로를 결정하는 방식이다. 장점)VLSM (Variable Length Subnet Mask)을 .. 공감수 0 댓글수 0 2024. 9. 24.
  • 라우팅 알고리즘 1. 동적 라우팅에 사용되는 알고리즘① 거리벡터(Distance Vector) : RIP, IGRP가. 개요- 모든 이웃 라우터들에게 자신이 가진 모든 정보(불완전한 정보 포함)를 주기적으로 알려준다.- 목적지 네트워크의 distance vector 정보를 서로 교환하여 라우팅 테이블을 작성- 목적지까지 경로를 제공하지 않으며, 단지 목적지까지의 최소비용(홉수)만 제공 나. 특징- 노드 변경 시 주기적으로 이웃한 노드와 자신의 라우팅 테이블을 공유 [산기, 14년3회]- 소규모 네트워크에 적합, 라우팅 테이블을 서로 교환 다. 장단점- 장점 : 네트워크의 distance 값에 대한 정보만 저장하기 때문에 장비의 메모리를 적게 사용- 단점 : 일정 시간마다 주기적으로 라우팅 정보를 발송함으로 네트워크 트래.. 공감수 0 댓글수 0 2024. 9. 24.
  • 암호화 알고리즘 정보를 안전하게 전송하거나 저장하기 위해 사용되는 수학적인 절차다.대칭 키 암호화 (Symmetric Key Encryption)빠르고 효율적이지만, 키를 안전하게 공유해야 한다AES (Advanced Encryption Standard)현재 가장 널리 사용되는 대칭 키 암호화 알고리즘 중 하나미국 국립표준기술연구소(NIST)에 의해 2001년에 공식적으로 표준으로 채택AES는 128비트, 192비트, 256비트 세 가지 키 길이를 지원하며, 블록 암호화 방식을 사용블록 암호화는 고정된 크기의 데이터 블록을 암호화하는 방식으로, AES에서는 128비트 블록 크기를 사용DES (Data Encryption Standard)초기 미국 국립표준기술연구소(NIST)에서 정한 표준으로 사용현재는 보안성이 약해짐에.. 공감수 1 댓글수 0 2024. 8. 28.
  • 휴리스틱 알고리즘 (Heuristic Algorithm) 우리가 문제 해결 시 흔히 사용하는 동적 계획법(DP) 또는 분할 정복과 같은 완전 탐색에 기초한 디자인 패러다임은 사실 실생활에서 쓰기엔 매우 한정적이다. 예를 들어, 인공지능 체스 프로그램을 알고리즘으로 짠다고 할 때 우리가 가장 먼저 떠올릴 수 있는 것은브루트 포스(brute force) 방식이다. 즉, 가능한 모든 말의 움직임을 다 해보는 것이다. 하지만 이 방식은 어림도 없는게 움직일 수 있는 말과 이동 가능한 칸이 너무 많기 때문에 만약 이 방식으로 프로그램을 개발했다고 하면, 죽을 때까지 게임이 끝나지 않을 것이다. (경우의 수가 10^120 가지라고 한다.)그렇다고 해서 분할 정복 기법을 사용하자니 적절한 분할 방법이 생각나질 않고 동적 계획법을 사용하자니 메모리가 턱없이 모자르다. 결국 .. 공감수 0 댓글수 0 2024. 7. 17.
  • 알고리즘과 휴리스틱의 차이 테스트 케이스의 효율성소프트웨어의 높은 품질을 위해 테스트를 진행할 때, 테스트 케이스를 작성하여 이에 따라 테스트를 실행하고, 실패율로 품질을 측정하는 방식을 선택하는 회사들이 많다. 하지만 현재까지 제품의 모든 경우의 수가 고려되고 전부 테스트 케이스로 옮겨지는 것은 사실상 현실적으로 불가능하며, 이러한 부분은 따라서 수치로 계산되지 못한다. 그렇다면, 이러한 테스트 결과 수치가 소프트웨어의 품질을 증명한다고 할 수 있을까?   테스트 케이스는 시간이 지나며 제품의 기능이 발전하고 늘어날 수록, 같이 늘어난다. 그만큼 테스트 수행 시간도 늘어나기 때문에, 결국 부분적 회귀 테스트를 테스트 전략을 많이 선택한다. 이러다 보면, 오랫동안 건드려지지 않는 위험요소가 적은 부분도 있을 테고, 그 부분의 테스.. 공감수 0 댓글수 0 2024. 7. 17.
  • 힙 (Heap) / 이진 힙 (Binary Heap) 정의힙 (heap)은 이진 힙 (binary heap)이라고도 하며, 최댓 값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리(complete binary tree)를 기본으로 한 자료구조다. 힙은 다음과 같은 속성을 가지고 있다.완전 이진트리(Complete Binary Tree) 이다.부모노드의 키값과 자식노드의 키값 사이에는 대소관계가 성립한다.키값 대소관계는 오로지 부모자식 간에만 성립되며 형제사이에는 대소관계가 정해지지 않음.힙의 종류1. 최대 힙 (Max Heap)부모 키값이 자식노드 키값보다 큰 힙Key(parent) ≥ Key(child)가장 큰 값이 루트노드에 있음2. 최소 힙 (Min Heap)부모 키값이 자식노드 키값보다 작은 힙Key(parent) ≤ Key(ch.. 공감수 0 댓글수 0 2024. 6. 13.
  • 우선 순위 큐 - Priority Queue 속성1. 모든 항목에는 우선 순위가 있다2. 우선 순위가 높은 요소는 우선 순위가 낮은 요소보다 먼저 queue에서 제외된다.3. 두 요소의 우선 순위가 같으면 queue의 순서에 따라 제공된다. 4 → 8 → 2 순으로 데이터가 들어간다고 했을 때 큐와 우선순위 큐의 처리 순서는 다음과 같다.(여기서 높은 값이 높은 우선순위를 갖는다고 가정.)input : 4 → 8 → 2큐 : 4 → 8 → 2우선순위 큐 : 8 → 4 → 2기본 동작enqueue()- queue에 새 요소를 삽입.dequeue() - queue에서 최대 우선 순위 요소를 삭제하고 그 값을 반환.peek() - queue에서 최대 우선순위 요소를 반환.구현  힙 방식이 최악에 경우라도 O(logN)을 보장하기 때문에 일반적으로 힙을 .. 공감수 0 댓글수 1 2024. 6. 13.
  • 스택 포인터와 프레임 포인터 스택 프레임 (Stack Frame) 기본적으로 함수가 호출될 때마다 전달한 인자와 정의한 지역(자동) 변수가 높은 주소부터 낮은 주소의 방향으로 차례대로 저장되는 구조이다. 이외에도 다른 함수를 호출할 때 복귀할 주소(다음 실행할 명령어의 주소), 프레임 포인터 및 보존되는 레지스터들이 스택에 저장된다. 스택 포인터는 함수 호출 시작부터 피호출 프로그램이 실행되는 단계 차례대로 저장되는 값들을 저장하기 위해 현 시점에서 저장할 메모리의 위치를 가리킨다. 스택 프레임에 저장되는 값 - 복귀 주소 - 호출자 루틴의 프레임 포인터 - 사용하던 보존 레지스터 - 피호출자에 전달하는 인자 - 피호출자에서 사용되는 지역 변수들 프레임 포인터 (Frame Pointer) 함수 호출이 끝난다면 상위 호출로 돌아기전에.. 공감수 0 댓글수 0 2024. 4. 16.
  • 에이전트의 정의 에이전트(Agent)는 인공지능 분야에 있어서 핵심 개념이 될 수 있다. 다음과 같이 정의를 내릴 수가 있다 "복잡한 동적 환경에서 목표를 달성하려 시도하는 시스템" 특징 특정 목적에 대해 사용자를 대신하여 작업을 수행하는 자율적 프로세스이다. 독자적으로 존재하지 않고 어떤 환경(운영 체제, 네트워크 등)의 일부이거나 그 안에서 동작하는 시스템이다. 지식 기반(Knowledge Base)과 추론 기능을 가지며, 자원 또는 다른 에이전트와의 정보 교환과 통신을 통해 문제를 해결한다. 스스로 환경의 변화를 인지하고 그에 대응하는 행동을 취하며, 경험을 바탕으로 학습하는 기능을 가진다. 분류 Simple Reflex Agents Condition-Action Rule을 내부에 가지고 있으며, 환경으로부터 받는.. 공감수 0 댓글수 0 2024. 4. 8.
  • [C++] 라운드 로빈 스케줄링 구현 (우선순위 큐 이용) EHProcess.h #pragma once #include #include using namespace std; class EHProcess { string pname; //프로그램 이름 const int tjob; //전체 작업량 const int cjob; //cpu 점유 시 수행가능 최대 작업량 int ntjob = 0; //현재 남은 작업량 int ncjob = 0; //현재 cpu 점유 시 수행가능 최대 작업량 public: EHProcess(string pname, int tjob, int cjob); //Idle 상태에서 Ready 상태로 전이 void IdleToReady(); //CPU를 점유하여 실행, 남은 작업량 반환 int Running(); //프로세스 종료 void EndPro.. 공감수 0 댓글수 0 2024. 3. 6.
  • [C++] lower bound, upper bound lower bound lower bound는 찾고자 하는 값 이상이 처음 나타나는 위치다. lower bound의 경우에는 같은 원소가 여러개 있더라도 상관없다. 찾고자 하는 값 이상의 값이 처음 나타나는 위치를 찾아내기 위해, 이분탐색 방법에서의 조건을 조금 변경하면 된다. [문제] n개로 이루어진 정수 집합에서 원하는 수 k이상인 수가 처음으로 등장하는 위치를 찾으시오. 단, 입력되는 집합은 오름차순으로 정렬되어 있으며(이분 탐색 가능), 같은 수가 여러개 존재할 수 있다. 입력) 첫 줄에 한 정수 n이 입력된다. 둘째 줄에 n개의 정수가 공백으로 구분되어 입력된다. 셋째 줄에는 찾고자 하는 값 k가 입력된다. (단, 2 0) { m = (s + e) / 2; if (A[m] < k) s = m + .. 공감수 0 댓글수 0 2023. 12. 19.
  • [C++] 계단 오르기 알고리즘 예로 들어서 n이 3이라면 꼭대기에 도달 하는데까지 총 3가지의 방법이 존재한다. 다른 예시로는 n = 1 // 한 가지의 방법만 존재하므로 1을 출력 n = 2 // 2, (1 , 1)과 (2) n = 4 // 5, (1, 1, 1, 1), (1, 1, 2), (2, 1, 1), (1, 2, 1), (2, 2) 재귀를 사용한 방식 방법의 수(n) = 방법의 수(n - 1) + 방법의 수(n - 2) 피보나치 수열을 이용하여 구할 수가 있다. 방법의 수(1) = 피보나치(2) = 1 방법의 수(2) = 피보나치(3) = 2 방법의 수(3) = 피보나치(4) = 3 int fib(int n) { if (n 공감수 0 댓글수 0 2023. 12. 18.
  • sort() 함수에서 쓰여지는 정렬 알고리즘 (Intro 인트로, Tim 팀) 일반적으로 시간 복잡도를 기준으로 sort 알고리즈므이 성능을 판단하지만, 실제로는 지역성이나 실 데이터의 분포 등 고려할 것들이 많다. 언어마다 default로 사용하는 sort들이 정해져있다. C++ : Intro Sort c++의 std::sort로 사용되고 퀵 정렬, 삽입 정렬, 힙 정렬로 이루어져 있다. 특징 기본적으로 퀵 정렬로 시작을 한다. 정렬할 element가 Threshold(일반적으로 16) 미만일 때는, 삽입 정렬로 수행된다. 재귀 depth가 정렬되는 element 수(n)과 비교해 log N보다 많아지면 힙 정렬로 수행된다. 퀵, 삽입 정렬은 지역성의 이점을 얻는 알고리즘(배열의 경우)으로 유명하다. 특히, 삽입 정렬은 참조 지역성을 아주 잘 만족한다고 한다. 삽입 정렬의 경우 .. 공감수 0 댓글수 0 2023. 12. 11.
  • [C++] Radix Sort (기수 정렬) 기수정렬은 정말 신기하게도 비교를 하지 않고 정렬을 하는 방법이기에 시간 복잡도가 O(n)이다. 구체적인 정렬 법을 알기 전에 이름인 '기수'가 뭔지 부터 알아보자. 여기서 '기수'라는 것은 '자릿수'를 의미한다. 자릿수로 뭘 어떻게 하는 것일까?? 방법은 다음과 같다. 1. 1의 자릿수를 보면서 각각의 버킷에 알맞게 담아준다. 버킷에서 순차적으로 뺀다면 1의 자릿수에 맞게 정렬이된다. 2. 1)에 의해서 정렬된 배열에서, 10의 자릿수를 비교해서 버킷에 담고 순차적으로 빼준다. 3. 2)에 의해서 정렬된 배열에서, 100의 자릿수를 비교해서 버킷에 담고 순차적으로 빼준다. 4. 최대 자릿수까지 계속해서 반복한다.. 구체적인 과정을 알아보자. 먼저 최대자릿수 까지 위의 과정을 반복해야 하므로 우리는 최대.. 공감수 0 댓글수 0 2023. 12. 4.
  • [C++] Trie (트라이) 소스코드 trie.h #ifndef TRIE_H #define TRIE_H #include #include #include #include #include #include #include #include #include namespace trie { struct SetCounter { }; namespace detail { template struct TrieNode : public PrefixHolderT { private: typedef TrieNode self_type; typedef self_type * self_pointer; self_pointer * data = nullptr; uint32_t size = 0; /* Will still be 64 bit due to alignment */ public.. 공감수 0 댓글수 0 2023. 12. 1.
  • [C++] Trie (트라이) 개념과 구현방법 트라이는 "문자열을 빠르게 탐색하게 해주는 자료구조" 이다. 즉, '문자열'을 관리하는 방법 중의 하나다 작동 원리 트라이는 주어진 문자열을 이루고 있는 문자를 앞에서 부터 하나씩 노드를 생성해가면서 만들어 진다. 이 과정에서 반복된 재귀 호출이 이루어지는데, 말로는 무슨 말인지 모르겠으니, 이 과정을 구체적으로 알아보자. 먼저, 문자열을 트라이로 생성하는 과정부터 알아보자. 간단하게 순서를 붙여보자면 다음과 같이 진행된다. ( 지금부터 '루트(Root)' 라는 말이 나올 수 있는데, 이는 가장 초기 노드라 생각하면 된다. 즉, 연결되어 있는 어떠한 노드도 없는 초기 노드이다. ) 1. 주어진 문자열에서 현재 문자를 가져온다. 2. 현재 문자로 이루어진 노드가 존재한다면, 그 노드로 그 다음 문자열을 탐.. 공감수 0 댓글수 0 2023. 11. 28.
  • [C++] const map 객체에 [key] 접근시 에러 map 클래스의 객체 a가 있고 이 객체가 const 화 되고 b라는 변수로 reference 됐다고 해보자. b에 대한 value 를 접근함에 있어 b["key"] 이런식으로 접근하면 에러가 난다. 내용은 error : passing '~' as 'this' argument discards qualifiers 이하 생략. 이유는 const 화 된 map 객체에 ["key"]로 접근하면 그 값을 수정할 여지가 발생하기 때문이다. value를 접근하는 다른 방법이 있다. 바로 .at를 쓰면 된다 b.at("key") 이렇게 접근하면 에러 없이 const화 된 map 객체의 value에 접근 가능하게된다. #include #include #include #include using namespace std; .. 공감수 0 댓글수 0 2023. 11. 22.
  • [C++] vector resize 시 주의할 점 기존보다 더 작게 할당하게 될 경우 만약 1 라는 값을 5 개 가진 벡터를 3 의 크기로 resizing 하며 2 로 채운다면 #include #include using namespace std; void Print_Vec(const vector vec) { for (auto const &it : vec) { cout 공감수 0 댓글수 0 2023. 11. 22.
  • Brute Force (브루트 포스) 알고리즘 개념 브루트 포스를 사전적 의미로 찾아본다면 아래와 같다. 브루트(Brute) : 무식한 + 포스(Force) : 힘 즉, 발생할 수 있는 모든 경우를 무식하게 탐색한다는 뜻이다. 전체를 탐색한다는 의미에서 전체 탐색, 완전 탐색이라고도 한다. 브루트 포스 알고리즘을 설계할 때는 해가 하나 이상 존재한다는 가정을 세우고 모든 범위를 탐색하기 때문에 무조건 정답을 찾을 수 있다. 장단점 장점) 알고리즘을 설계하고 구현하기 매우 쉽다. 복잡한 알고리즘 없이 빠르게 구현할 수 있다. 단점) 알고리즘의 실행 시간이 매우 오래 걸린다. 메모리 효율면에서 매우 비효율적이다. 종류 선형 구조) 순차 탐색 비선형 구조) 백트래킹, dfs, bfs 예시 만약 10자리 비밀번호 자물쇠가 있다고 가정해보자. 이 자물쇠를 풀.. 공감수 0 댓글수 0 2023. 11. 22.
  • [C++] 개인적인 (MST 알고리즘) 크루스칼 & 프림 구현 사용할 데이터는 다음과 같다. 결과) 17 1 2 2 2 6 7 3 2 3 3 6 8 4 3 5 4 2 3 4 1 1 5 1 4 5 4 9 공통으로 쓰여짐 // 간선 개수 const int edge = 9; struct sNode { public: int from = 0, to = 0, weight = 0; /*sNode() = default; sNode(int from, int to, int weight) : from(from), to(to), weight(weight) { }*/ bool operator(const sNode& ref) const { return weight > ref.weight; } bool operator==(const sNode& ref) const { return from =.. 공감수 0 댓글수 0 2023. 11. 16.
  • [C++] 삼항 트리를 이중 연결된 목록으로 변환 삼항 트리가 주어지면, 제자리에서 이중 연결된 목록으로 변환한다. 삼항 트리는 각 노드가 왼쪽, 중간, 오른쪽으로 구분되는 세 개의 자식 노드를 갖는 트리 데이터 구조다. 변환은 삼항 트리 노드의 왼쪽 자식 포인터가 이중 연결된 목록 노드의 이전 포인터 역할을 하고 오른쪽 자식 포인터가 이중 연결된 목록 노드의 다음 포인터 역할을 하고 중간 트리 노드가 자식 포인터는 아무 것도 가리키지 않아야 한다. 변환은 이중 연결된 목록의 노드에 추가 메모리를 할당하지 않고 삼항 트리 노드 포인터만 교환하여 수행해야 한다. Input: Ternary Tree 1 / | \ / | \ / | \ 2 9 12 / | \ / \ | \ 3 6 8 10 11 13 16 | \ / \ | 4 7 14 15 17 \ 5 Out.. 공감수 0 댓글수 0 2023. 11. 6.
  • [C++] Palindrome (팰린드롬 회문)에 대한 모든것 1. 팰린드롬이란? 팰린드롬(Palindrome, 회문)은 처음부터 끝까지 거꾸로 읽어도 똑같이 읽히는 수 또는 문자열을 의미한다. 예를 들면, "racecar"나 "abcdcba", 한글로 하면 "수박이박수", "다시합창합시다" 정도가 되겠다. 이 팰린드롬을 판별하는 것은 여러 방법이 있다. 2. 팰린드롬 판별 1 - Naive 팰린드롬을 판별하려면, 처음 글자부터 마지막 글자까지 거꾸로 셌을 때 같은 수거나 문자열이면 가능하다. 입력이 문자열일 경우 다음과 같이 함수를 작성할 수 있다. #include using namespace std; bool is_palindrome(string str) { bool flag = true; for (int i = 0; i < str.size(); i++) { /.. 공감수 0 댓글수 0 2023. 11. 6.
    문의안내
    • 티스토리
    • 로그인
    • 고객센터

    티스토리는 카카오에서 사랑을 담아 만듭니다.

    © Kakao Corp.