컴공댕이 공부일지

🔎 DFS란? BFS와 DFS를 쉽게 설명하자면,가까운 이웃부터 좀좀따리 파면서 탐색. 한 단계씩 나아가며 가까운 정점들을 다 방문함 - 큐로 구현드라마 정주행하듯 끝까지 깊이 탐색. 더이상 못 파면 이전으로 돌아가 다른 경로 탐색. - 스택과 재귀로 구현 BFS: 가까운 것부터 차례대로 탐색 → 큐 사용 → 최단 경로 탐색에 유리DFS: 깊게 탐색 후 되돌아감 → 스택 또는 재귀 사용 → 경로를 깊이 있게 탐색 지난 글에서 BFS를 다루며 언급했던 내용이다.  DFS는 BFS와 크게 다를 것 없지만, 스택을 사용해 구현한다. BFS는 FIFO인 큐를 사용해서, 인접한 노드들을 우선적으로 처리하며 점차 퍼져나갔다면, DFS는 LIFO인 스택을 사용하기에 가장 최근에 들어갔던 마지막 노드가 우선 처리되므..

🔎 BFS란? BFS와 DFS를 쉽게 설명하자면, 가까운 이웃부터 좀좀따리 파면서 탐색. 한 단계씩 나아가며 가까운 정점들을 다 방문함 - 큐로 구현드라마 정주행하듯 끝까지 깊이 탐색. 더이상 못 파면 이전으로 돌아가 다른 경로 탐색. - 스택과 재귀로 구현 BFS: 가까운 것부터 차례대로 탐색 → 큐 사용 → 최단 경로 탐색에 유리DFS: 깊게 탐색 후 되돌아감 → 스택 또는 재귀 사용 → 경로를 깊이 있게 탐색  이번 글에서는 바킹독 선생님의 강의를 기반으로, BFS의 문제 유형 여러 가지를 풀이해볼 것이다.      📝  BFS 기초 예제 백준 1926번 그림  - 영역 탐색. 2차원 배열에서 가장 넓은 영역 면적 찾기. BFS의 기본 예제 !https://www.acmicpc.net/probl..

[ 정수 자료형 ]short (2byte) int (4byte) - 최댓값 21억 long long (8byte) - 최대 19자리 (2^63-1)[ 실수 자료형 ]float (4byte) : 1 + 8 + 32bitdouble (8byte)  : 1 + 11 + 52bit부호 + 지수(exponent) + 유효숫자(fraction) 필드로 실수를 저장함 ex) -6.75의 이진수 표현 부호 : 1 정수 : 6 = 110 소수 : .75 = 0.5 + 0.25 = .11 -> 110.11 -> 1.1011 * 2^2  [ ⭐ 실수 자료형의 특징 ]1. 실수의 저장/연산 과정에서 반드시 오차가 발생할 수 밖에 없다..컴퓨터는 실수를 근사값으로 저장함 ! => 실수가 필요하다면 가능한 오차 범위가 훨씬 더 ..

보호되어 있는 글입니다.

보호되어 있는 글입니다.

🔎 우선순위 큐란? 기존의 큐는 먼저 넣은 요소가 먼저 나오는 FIFO( first in - first out )이지만, 우선순위 큐는 들어간 순서 상관없이, 우선순위가 높은 데이터가 먼저 나온다 ! (ex.위급한 사람부터 처치하는 응급실) 우선순위 큐는 힙(Heap)이라는 자료구조로 구현하며, 모든 연산에 대한 시간 복잡도가 O(log n)이다. 📖 완전 이진 트리와 힙 🔎 완전 이진 트리 (complete binary tree) - 이진 트리(자식이 최대 2개인 트리)의 한 종류 - 마지막 레벨 제외하고는 모든 레벨이 다 채워져있어야 함 - 마지막 레벨의 모든 노드는 왼쪽부터 빈공간없이 채움 📍 힙(Heap)의 조건 1) 완전 이진 트리 2) 힙은 상위노드가 모든 하위노드보다 우선순위가 크거나 같다 ..

🔎 그리디 알고리즘(탐욕법)이란? 전체 문제를 여러 조각으로 분할하고, 각 단계별 최적해를 결합해 최종 최적 해를 만들어가는 알고리즘인데, 쪼갠 작은 단계마다 욕심쟁이처럼, 미래는 보지 않고 그저 눈 앞에 보이는 가장 좋은 방법만을 늘 선택합니다. 단순히, 현재 내릴 수 있는 최선의 선택에만 집중하는 알고리즘입니다. 📖 그리디 알고리즘 문제 출제 경향 단순히 각 단계에서 가장 최적의 값을 고르는 그리디 알고리즘이 늘 최적해를 구해내진 못합니다. 근사한 해만을 구할 수 있는 경우가 대부분입니다. 그리디 알고리즘은 계산 속도가 빠르기에, 시간 및 공간적 제약으로 최적해를 구하지 못해서 최적해 대신 근사해를 구해야 할 때 사용됩니다. 그러나, 이 경우는 주로 코딩테스트에서 출제되진 않고, " 탐욕법을 사용해도..

보호되어 있는 글입니다.

📌 맵(Map)맵은 키(key)와 값(value) 사이의 연관성을 나타내는 자료구조맵은 일반적으로 이진 검색 트리를 기반으로 구현되고, 키의 *정렬된 순서를 유지합니다. * 문제에 따라, 정렬된 순서가 필요없다면, 순서없는 맵도 사용하곤 하는데, 밑에서 문제 풀며 자세히 다룸 !!맵(Map)의 주요 특징:키와 값 사이의 일대일 관계 유지마치 한영사전같은 느낌.. key는 사과, value는 apple. 둘이 짝지어져서 사과라는 키 값으로 apple을 서치 가능.키는 중복 X. 즉, 각 키는 유일해야 합니다.한영사전에 사과가 여러개일 순 없져 ㅎㅅㅎ키를 기준으로 정렬됨📌 셋(Set)중복된 값을 허용하지 않는 자료구조집합(set)과 유사하며, 고유한 값들을 저장하고 조회할 수 있음셋도 내부적으로 이진 검..

📝 에라토스테네스의 체 소수를 구하는 쉽고 빠른 방법 소수를 판별할 때, 아래와 같이 배수들을 지워나가면서 남은 수들을 소수로 판별하는 과정 ! 이거 중딩? 때 다 해봤을거다ㅎㅎ 위의 그림에서 우린 1부터 50까지 소수를 판별하려고 한다. 그래서 1부터 50까지 다 하나하나 배수를 지워야할 것 같지만, 실제로는 √50 이하의 수들만 확인하면 된다. 왜일까? 왜 하필 루트를 씌운 제곱근 값일까? 🔍 소수 판별 시에 제곱근 이하만 확인하면 되는 이유 🤔 1과 자기 자신이 아닌 약수가 하나라도 있다면, 그것은 소수가 아니다. 8 = 1 * 8 = 2 * 4 = 4 * 2 = 8 * 1 곱해서 8이 되는 조합들이다. 즉, 약수가 1,2,4,8이므로 소수가 아니다. 근데 여기서, 2가 나누어떨어지는 걸 봤는데, ..