Computer Science/자료구조,알고리즘

📘 10주완성 C++ 코딩테스트 강의를 수강한 후 정리한 글입니다. 깊이 우선 탐색 ( DFS, Depth First Search ) DFS는 그래프를 탐색할 때 쓰는 기법이다. 어떤 노드부터 시작해 인접한 노드들은 재귀적으로 방문하며 방문한 정점은 다시 방문하지 않는다. 각 분기마다 가능한 가장 멀리 있는 노드까지 탐색하는 알고리즘이다. DFS를 구현하는 방법 1️⃣ visited를 확인하고 함수 호출 2️⃣ 함수 호출 후 기저조건으로 함수 return ⬇ 수도코드 DFS( u , adj ) u.visited = true // 해당 노드 방문처리 for each v in adj[u] if v.visited == false //방문 여부 확인 DFS( v, adj )// 방문하지 않은 경우 방문( 재귀 ..

📘 10주완성 C++ 코딩테스트 강의를 수강한 후 정리한 글입니다. ※ 비트 연산자 활용법 1. idx번째 비트 끄기 ex) S = 10010 (18) 에서 1번째 비트를 끄려면, 먼저 00010을 만든다. ( 1

❣ 인프런 루키스 님의 [C++과 언리얼로 만드는 MMORPG 게임 개발 시리즈] Part3: 자료구조와 알고리즘 강의를 바탕으로 작성 되었습니다. ✔ Big-O 표기법 두 알고리즘 A와 B의 효율을 객관적으로 비교하기 위해서 사용. 1단계 : 대략적인 계산 - 수행되는 연산(산술, 비교 대입 등)의 개수를 '대략적으로' 판단한다. ex ) 이중 for 문 = N^2 2단계: 대장만 남긴다. 규칙1) 영향력이 가장 큰 대표 항목만 남기고 삭제. 규칙2) 상수 무시(ex. 2N ➡ N) ✔ Big-O 표기법의 의의

✅ C언어로 쉽게 풀어 쓴 자료구조 : p.206-208 LAB 연결리스트를 역순으로 만드는 프로그램을 작성하여 보자. 이 함수에서는 세 개의 포인터 p,q,r 포인터를 사용하여 연결 리스트를 순회하면서 링크의 방향을 역순으로 바꾸면 된다. 새로운 연결 리스트를 만들지 않고 이와 같이 3개의 포인터를 사용하여 현재의 연결 리스트 안에서 문제를 해결하는 기법은 상당히 흥미롭다. 다만 주의할 점은 링크의 방향을 역순으로 바꾸기 전에 미리 뒤의 노드를 알아 놓아야 한다. p는 역순으로 만들 리스트이고 q는 현재 역순으로 만들 노드를 가리키며, r은 이미 역순으로 변경된 리스트를 가리킨다. r은 q, q는 p를 차례로 따라간다. ListNode* reverse(ListNode *head) { ListNode *..