개발하는 멍정이야기

* 잘못된 내용에 대한 피드백은 언제나 환영입니다. *컴퓨터 구조란 무엇일까?컴퓨터에 대한 구조를 이해하는 것.그렇다면 그 안에는 무엇이 있는가.1. 상위 수준 언어와 기계어가 어떤 과정을 거쳐서 이해하는가.2. 프로세서3. 메모리와 구조..?2랑 3은 아직 안봐서? 모르겠어요. 1부터 봅시다.상위 수준 언어에서 기계어까지컴퓨터가 이해하는 언어는 이진수(10010101 etc.)이기 때문에 이를 이해할 수있는 어셈블러(assembler)를 개발했다.어셈블리 언어는 add A, B의 형태로 생겼는데 이것도 기계식 사고 방식을 요구하니까 새로운 언어를 개발했다.그게 바로 상위 수준 언어(c, java ..)!그렇기 때문에상위 수준 언어(c 등) -> 어셈블리 언어(RISC-V 등등) -> 이진수(binary..

* 잘못된 내용에 대한 피드백은 언제나 환영입니다. * 멍하멍정이에요.오늘은 STL컨테이너 두번째 시간!연관 컨테이너(Associative Container)에 대해 알아보아요! 연관 컨테이너에서 요소는 미리 정의된 순서(예: 오름차순 정렬)로 삽입됩니다. 순서가 지정되지 않은 연관 컨테이너도 사용할 수 있습니다. 연관 컨테이너를 맵 및 집합의 두 하위 집합으로 그룹화할 수 있습니다.Microsoft Learn - STL 컨테이너 문서  말 그대로 컨테이너에 값을 넣을 때 정의된 순서를 따라서 삽입한다고 할 수 있습니다.하나하나 천천히 살펴보아요. map container각 요소가 정렬 키와 데이터 값을 갖고 있는 쌍으로 삽입됩니다.키 값은 고유하며(이미 값이 있는 경우에는 다시 삽입 불가) 키 값을 기..

* 잘못된 내용에 대한 피드백은 언제나 환영입니다. *  멍하멍정이에요.오늘은 STL컨테이너에 대해 정리해보아요. STL 컨테이너란 무엇인가?표준 라이브러리는 관련 개체 컬렉션을 저장할, 형식이 안전한 다양한 컨테이너를 제공합니다. 컨테이너는 클래스 템플릿입니다. 컨테이너 변수를 선언할 때 컨테이너가 보유할 요소의 형식을 지정합니다. 컨테이너는 이니셜라이저 목록을 사용하여 생성할 수 있습니다. 요소를 추가 및 제거하고 다른 작업을 수행하기 위한 멤버 함수가 있습니다.https://learn.microsoft.com/ko-kr/cpp/standard-library/stl-containers?view=msvc-170 C++ 표준 라이브러리 컨테이너자세한 정보: C++ 표준 라이브러리 컨테이너learn.mic..

멍하멍정이에요.티스토리 정말 오랜만이네요.티스토리 편집툴이 너무 구려서 요즘은 노션을 자주 이용했는데 아무튼앞으로 열심히 할 수 있길 바라며. 오늘은 c++ 을 조금 준비하려고 합니다.저번학기에 1일 1백준을 했었는데c++은 처음이라 처음 보는 개념 같은걸 깃허브에 메모했던걸 좀 정리해보려고 합니다.깃허브는 요기https://github.com/258xsw/BaejoonAlgorithm : c++ 표준 입출력 클래스c++은 객체지향이기 때문에 입출력을 담당하는 수단도 객체로 다루게 된다.std::cout- 표준 c 출력 스트림- cout std::setprecision(n)- cout의 출력 포맷을 지정한다.- cout의 기본 정밀도는 6이기 때문에 원하는 소수점을 늘리고 싶을 때 사용!-> 포맷을 변경..

멍하멍정이에요나름 바빴던 4학년 1학기를 끝내고 이제 정말로 취준을 준비하면서..git/github에 대해 다시 한 번 정리해보려고 해요깃허브 계정은 오백년 전에 만들었는데 아직도 기본 기능만 사용하는 것 같아서천천히 git부터 배워가려고 해요그런 의미에서 오늘은 간단하게 많이들 헷갈리는 Git/Github에 대해서 짚고 가려고 해요. 들어가기에 앞서..잘못된 정보는 언제든지 알려주시면 수정하겠습니다 0Git과 Github란?저도 처음에 그랬듯이 많은 분들이 git과 github에 대한 개념을 헷갈리시는데 간단하게 짚고 넘어가자면 Git : 내 컴퓨터(local)에서 진행 상황 정리GitHub : 내 컴퓨터(local)에서 저장한 진행 상황을 온라인(global)으로 올려서 관리간단하게 닌텐도 게임 젤다..

Merge Sort Revisited : 잘게 쪼개서 합치면서 비교하며 정렬 worst case time complexity = n lg n + n + 1 -> 합치는 과정에서 2개 이상을 한 번에 처리할 수 있기 때문에 아까보다 좋아짐! - 더욱 개선 할 수 있는 방법? 1. Dynamic programming 2. LInked list 3. More complex merge algorithm merge sort의 자세한 알고리즘은 요기... [알고리즘] Binary Search, Mergesort(DIvide and Conquer) DIvide and Conquer Approach - Divide : 인스턴스가 너무 커서 계산이 힘들다면 작게 쪼개서 계산한다. - Conquer : 작아진 인스턴스를 ..

Two Types of Complexity Analysis Algorithm Analysis : 효율적인 알고리즘을 찾기 위한 접근법 -> time complexity & space complexity problem Analysis : 좀 더 본질적인 문제의 복잡성에 대한 분석 -> matrix multiplication의 경우 n^3이 되는 경우, n^2.81(스트라센) 아무튼 이런저런 방식이 있음 -> 계산 복잡도에 대한 분석을 해보자? (computatuinal complexity analysis) Computational Complexity Objective Ω(f(n))에 대해 Θ(f(n))을 개발하는 방법? -> 하지만 문제의 하한보다 낮은 알고리즘을 개발하는 것은 불가능!! ex. sorti..

The Traveling Salesperson Problem -> 비행기타고 여기저기 출장 다녀오기 (ง˙∇˙)ว + 최소값으로 다녀와야함 Input - 값이 있는 방향 그래프 - 음수 x - 행과 열이 1부터 n까지인 2차원 배열 W - W[i][j] : i번째 정점에서 j번째 정점까지의 간선 위의 가중치 Output - 최적 투어의 길이를 값으로 하는 변수 minlength, 그를 구성하는 행렬 P Dynamic Programming for TSP - Brute force algorithm(전부 찾기) : (n - 1)! - The length of the optimal path(최적 경로 방법?) 아무튼 최단 거리를 찾는게 목표 일반적으로 i가 1이 아니고 vi가 A가 아니라면 a가 0이 아니면(내..

Branch and Bound Algorithm - backtracking을 개선한 알고리즘 - state space tree은 backtracking처럼 그대로 사용됨 - 최적화 문제에 사용 What is a bound? : 바운드는 노드를 넘어 확장하여 얻을 수 있는 해의 값? - 노드의 경계를 계산하여 노드가 유망한지 여부를 확인 - 경계값이 지금까지 발견된 최상의 솔루션의 값보다 크지 않으면 non-promising => k - 1까지의 가장 큰 값이 bound라서 다음 노드의 bound가 Maxprofit보다 작으면 확인 할 필요 없음! -> 내가 찾은 값이 더 크니까! The 0/1 Knapsack Problem Revisited : 가방에 최대한 많은 물건을 훔치자!-> 얼마짜리를 몇키로까지..

Monte Carlo Algorithm - 확률적 알고리즘으로 확률적 분포에 따라 무작위로 결정된다. In backtracking Algorithm - backtracking 알고리즘의 효율성을 추정할 때 사용할 수 있다. - state space tree의 동일한 level에서는 동일한 promising function을 사용 - 동일한 level의 node에는 동일한 수의 자식 노드가 있어야 함. Monte Carlo Algorithm in 4 - queens problem 4-queens problem에서 monte carlo algorithm으로 backtracking algorithm의 효율성 측정하기 -> 실제 방문해야할 노드를 추정 1. i 번째 노드에서 n개 중에 3개정도를 조사하였을 때 ..