은학의 코딩 일기장

DFS의 기본 개념 BFS 알고리즘은 너비 우선 탐색이라고도 불리며 그래프에서 시작 노드에 인접한 노드부터 탐색하는 알고리즘 BFS 구현 방식 BFS 알고리즘은 그래프에서 가까운 노드부터 우선적으로 탐색한다는 점에서, 선입선출 방식의 큐(Queue) 자료구조를 활용 BFS 동작 과정 1️⃣ 탐색 시작 노드 정보를 큐에 삽입하고 *방문 처리합니다. 2️⃣ 큐에서 노드를 꺼내 방문하지 않은 인접 노드 정보를 모두 큐에 삽입하고 방문 처리합니다. 3️⃣ 2번의 과정을 더 이상 수행할 수 없을 때까지 반복합니다. 파이썬 구현

DFS 개념 (1) DFS의 기본 개념 DFS란 Depth first search의 약자로서 그래프 자료에서 데이터를 탐색하는 알고리즘 위에서 아래로 찾는 방식이 바로 DFS (2) DFS의 기본 원칙 DFS에서 데이터를 찾을 때는 항상 "앞으로 찾아야 가야할 노드"와 "이미 방문한 노드"를 기준으로 데이터를 탐색을 합니다. 이 원칙을 반드시 기억해주셔야 해요. 그래서 특정 노드가 "앞으로 찾아야 가야할 노드"라면 계속 검색을 하는 것이고, "이미 방문한 노드"면 무시하거나 따로 저장하면 됩니다. (3) DFS의 구현 방식 DFS를 구현할 때는 기본적으로 "스택/큐"를 활용할 수도 있고, "재귀함수를 통해 구현할 수도 있습니다. 스택 / 큐를 사용한 DFS 구현 (1) 리스트를 활용한 DFS 구현 여기서..

다이나믹 프로그래밍이란? 다이나믹 프로그래밍(Dynamic Programming, DP) 알고리즘은 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다. 방식은 분할정복과 같으나 분할정복은 계산한 부분문제를 단 한번만 쓰고 더이상 사용하지않는다. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 다이나믹 프로그래밍의 구현은 일반적으로 탑다운(top-down) 방식과 보텀업(bottom-up) 방식이 있다. 메모이제이션(Memoization) 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나다. 한 번 계산한 결과를 말 그대로 메모리 공간에 메모하는 기법이다. 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다. 값을 기록해 놓는다는 점에서 캐싱이라고도..

BoxModel weight = 가로 height = 세로 padding = 안쪽 여백 border = 테두리 (크기 형태 색깔 3개다 정해줘야됨!!!!) margin = 바깥 여백 Box-sizing css의 boxmodel의 box-sizing 은 content-box으로 지정되는데 이렇게 되면 padding값을 바꿀 때 Box 자체의 크기까지 변경되어 좀 귀찮아질 수 있음 그러므로 초기설정 때 *{ box-sizing = border-box; } 로 해주면 편함 Block ( 길막) 다른 박스가 자신의 라인에 침범 못하고 다음 줄로 넘어감 따로 width를 설정하지 않은경우 width = 부모의 content-box의 100% 따로 width를 설정한 경우 남은 공간은 margin으로 자동으로 채움..

선택자의 종류 Type : 과 같은 타입을 나타내는 선택자 Class : Id : Type p{ color : "black"; } 처럼 활용 3번째 우선순위를 가짐 Class .abc{ color : "black"; } 처럼 활용 .을 붙이는게 포인트 !! 2번째 우선순위를 가짐 Id #abc{ color : "black"; } 처럼 활용 #을 붙이는게 포인트 !! 1번째 우선순위를 가짐 자식 자손 형제 선택자 html => p의 자식 => p의 자손 => p와 div는 형제 자식 선택자를 선택할 때 p > li { color : "black"; } 자손 선택자를 선택할 때 p li { // 띄어쓰기 한번만 해주면 됨! color : "black"; } 형제 선택자 html css .active ~ p{..

그리디 알고리즘 그리디 알고리즘은 Greedy(탐욕, 욕심쟁이)라는 이름처럼 지금 당장 최적인 답을 선택하는 과정을 반복하여 결과를 도출하는 알고리즘이다. 그리디 알고리즘은 말 그대로 각 단계에서 미래를 생각하지 않고, 그 순간 가장 최선의 선택을 하는 기법이기 때문에 종합적인 결과에 대해서는 최적의 해를 보장할 수 없다. (지역적(local)으로는 최적의 선택이지만 이를 반복하더라도 전체적(global)으로는 최적의 해가 아닐 수 있음) 그리디 알고리즘의 장점 탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다. 탐욕 알고리즘을 적용해도 언제나 최적해를 구할 수 있는 문제(매트로이드)가 있고, 이러한 문제에 탐욕 알고리즘을 사용..