전체 글

2주차가 끝났습니다!이젠 몸도 마음도 슬슬 주 6일 하루 11시간 이상 공부하는 데에 적응이 된 것 같습니다. 2주차 퀴즈는 아래와 같은 문제들이 나왔습니다. 1. 캐시메모리를 사용하면 컴퓨터 시스템의 성능이 왜 향상되는지 지역성(locality) 개념을 포함하여 설명2. 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)을 파이썬 혹은 pseudocode로 구현3. 프로세스와 스레드의 차이에 대해 설명4. 가중치가 할당된 그래프를 주고 다익스트라 알고리즘을 적용하였을 때 그래프를 단계별로 그리기5. B-Tree 인덱스를 사용했을 때와 사용하지 않았을 때의 데이터 검색 시간 복잡도를 Big O 표기법으로 표현하기 1번~4번까지는 미리 공부한 게 있어서 풀긴 풀었는데, 다 풀고 답을 확인해 보니 스스로에게..

포인터포인터란 C언어에서 메모리 주소를 가리킬 때 사용되는 사용되는 변수입니다. 일반적으로 C언어에서 사용되지만, 많은 언어가 C언어에서 파생/발전되었기 때문에 메모리 주소를 다루는 대부분의 언어가 사용하는 개념이라고 이해하시면 편할 것 같습니다.  🔴포인터를 직접 사용/활용할 수 있는 언어: C, C++, 파스칼, 어셈블리어 등 하위 레벨까지 제어할 수 있는 언어🔵포인터가 숨겨져서 직접 사용할 수 없는 언어: 자바, 파이썬, 자바스크립트, C#, 코틀린 등 📝포인터를 잘못 사용할 경우 메모리 누수, 버퍼 오버플로우 등의 문제들이 발생할 수 있습니다. 따라서 자바와 같은 언어에서는 GC(가비지 컬렉션) 등의 자동 메모리 관리 기법을 사용하여 메모리 해제와 할당을 프로그래머가 하는 것이 아닌, 시스템..

냅색 문제냅색 문제는 최적의 조합을 찾기 위한 일종의 최적화 문제입니다. 냅색문제의 기본 개념은 주어진 물품들을 배낭에 담아 최대 가치를 얻는 것입니다. 아래와 같은 15kg 무게 한도의 배낭이 있을 때, 무게 한도 내로 물품을 가방에 넣는다는 가정하에 물건 가치의 합이 최대가 되게 담는 것입니다. 냅색 문제는 몇 가지 변형이 존재하는데, 문제의 변형 형태에 따라 사용할 수 있는 알고리즘이 다릅니다. 냅색 문제의 대표적인 형태는 2가지가 있습니다. 분할 냅색 문제(Fractional Knapsack Problem)- 물품을 쪼개서 배낭에 담을 수 있습니다.- 무게당 가치가 높은 물품을 우선적으로 담으면 됩니다.- 가치 높은 물품을 우선적으로 담기만 하면 되기 때문에 그리디 알고리즘(Greedy Algor..

🎮LCS만 검색하면 롤 북미 프로 리그가 나오던데,,, 이거 아닙니다! LCS 알고리즘LCS 알고리즘은 문자열 혹은 배열 내에서 가장 긴 공통 부분 수열을 찾는 알고리즘입니다. 여기서 공통 부분 수열이란 수열(문자열/배열) 내의 원소 내에서 순서대로 나타나지만 반드시 연속될 필요는 없는 부분 수열을 뜻합니다. LCS는 두 문서가 얼마나 비슷한지를 확인하는 코드 비교 도구, 버전 관리 시스템에 응용되거나 생물정보학의 서열 간 유사성 조사를 위해 DNA, RNA 서열 분석에 응용됩니다. 설명을 위해 그림으로 설명하겠습니다. 아래와 같이 두 문자열이 존재한다고 가정해봅시다.두 문자열 내에서 공통으로 존재하는 문자열은 ABEFG입니다. 해당 문자열은 두 문자열 내에서 반드시 나타나지만 반드시 연속해서 나타나지..

다익스트라 알고리즘(Dijkstra Algorithm)다익스트라 알고리즘은 그래프의 한 정점에서 다른 정점으로의 최단 경로를 찾기 위해 사용되는 최단 경로 알고리즘입니다. 최단 경로를 찾는 알고리즘 하면 BFS를 떠올릴 수도 있지만, 다익스트라는 BFS(넓이 우선 탐색) 알고리즘과는 다르게 가중치가 존재하는 그래프에서 최단 경로를 찾을 때 사용됩니다. 이 때 그래프의 가중치는 음수가 될 수 없습니다.  특정 노드에서 각 노드까지의 최단 경로를 찾기 위해 사용하는 알고리즘인 만큼 실생활의 활용 예시로는 1. 지도의 특정 지점에서 다른 지점까지의 최단 경로 찾기2. 컴퓨터 네트워크에서의 데이터 패킷의 최적 경로를 찾기 위한 네트워크 라우팅 등 에서 사용됩니다. 다익스트라 알고리즘 구현다익스트라 알고리즘의 핵..

그리디 알고리즘그리디 알고리즘의 핵심은 문제를 해결할 때 각 단계에서 매번 최선의 선택을 하는 것입니다. 당장 눈 앞의 선택지 중에 최선을 선택을 하여 결과적으로 최고/최적의 결과값을 도출해 내는 기법입니다. 이름이 Greedy Algorithm(탐욕 알고리즘)인 것을 생각해 보면 어느 정도 쉽게 이해가 됩니다. 그리디 알고리즘은 단계별로 그냥 최적의 선택만 하면 되기 때문에 단순하여 구현이 쉽다는 장점이 있습니다.  그리디 알고리즘에도 치명적인 단점이 존재합니다. 바로 매 순간 현재 단계에서 최선의 선택을 하더라도, 전체 문제의 관점에서 보았을 때 최선의 선택이 아닐 수 있다는 점입니다. 이런 점 때문에 그리디 알고리즘을 사용할 때는 아래의 조건을 충족하는 문제에서만 사용하여야 합니다. 1. 현재의 선..