Processing math: 100%
깊이 우선 탐색(DFS)/너비 우선 탐색(BFS)
·
Algorithm/알고리즘 이론
깊이 우선 탐색(DFS; Depth-First search) 그래프의 시작 노드에서 출발하여 탐색할 한쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘 재귀 함수로 구현 스택 자료구조 이용 시간 복잡도(노드 수: V, 에지수: E) O(V+E) 풀 수 있는 문제: 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기 인접 리스트로 그래프 표현하기 방문 리스트 초기화하기 시작 노드 스택에 append()로 삽입하기 2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기 pop()으로 노드 꺼내기 꺼낸 노드를 탐색 순서에 기입 인접 리스트의 인접 노드를 스택에 삽..
백준 1967, 1167 | DFS/BFS | 트리의 지름 [파이썬 python]
·
Algorithm/백준
트리의 지름 트리의 지름이라는 것은 1967번 문제에도 나와 있듯이 어떤 두 노드를 선택해서 당겼을 때, 가장 길게 늘어나는 경우의 두 정점 사이의 거리를 말하는 것이다. 즉, 아래 그림의 9번, 12번 노드 사이의 거리는 45로 어떤 두 노드보다 가장 긴 거리를 가지므로, 이 두 노드 사이의 거리가 주어진 트리의 지름이다. 따라서 우리가 이 문제에서 구해야 하는 것은 두 노드 사이의 최대 길이이다. 백준 1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 두 노드 사이의 최대 거리를..
정렬
·
Algorithm/알고리즘 이론
버블 정렬(bubble sort) 두 인접한 데이터의 크기를 비교해 정렬하는 방법 시간 복잡도 O(N2) 다른 정렬 알고리즘보다 속도가 느린 편 루프를 돌면서 인접한 데이터 간의 swap 연산으로 데이터 정렬 💡 버블 정렬 과정 ① 비교 연산이 필요한 루프 범위 설정 ② 인접한 데이터 값을 비교 ③ swap 조건에 부합하면 swap 연산을 수행 ④ 루프 범위가 끝날 때까지 ②~③을 반복 ⑤ 정렬 영역을 설정. 다음 루프를 실행할 때는 이 영역을 제외함 ⑥ 비교 대상이 없을 때까지 ①~⑤를 반복 선택 정렬(selection sort) 대상 데이터에서 최대 또는 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법 구현 방법이 복잡함 시간 복잡도 O(N2) 코딩 테스트에서는 많이 사용하지 ..
KT 에이블스쿨 AIVLE school 5기 모집합니다! (이벤트도 있어요)
·
KT에이블스쿨
KT 에이블스쿨 AIVLE school 5기를 모집합니다! 5기 모집 공고가 뜨자마자 '에이블스쿨' 검색으로 엄청 많은 분들이 블로그에 방문해 주셨어요(최고 방문자수 ㄷㄷ;;) 저도 지원할 때 많은 선배 에이블러 분들의 블로그들을 참고했던 지라 북다닥 달려왔습니다 🏃‍♀️🏃‍♂️🏃 5기 모집 이미지가 너무 기니까 맨 마지막에 보시고 궁금해하실 만한 부분들을 제가 먼저 요약해 드릴게요 ^__^ 1. 모집 기간: 23년 11월 27일(월) ~ 23년 12월 28일(목) 14시까지 2. 어디로 지원하나요?: 에이블스쿨 공식 홈페이지 → https://aivle.kt.co.kr/home/main/indexMain 대학생인 경우 본인 학교에서 지역추천제로 지원이 가능한지 먼저 알아보세요. 서류 심사 면제 됩니다!..
스택(Stack)/큐(Queue)/우선순위 큐(Priority Queue)/힙(Heap)
·
Algorithm/알고리즘 이론
스택(stack) 삽입과 삭제 연산이 후입선출(LIFO)로 이뤄지는 자료구조 LIFO(Last In Frist Out) 가장 마지막에 삽입된 데이터가 가장 먼저 나오는 구조 삽입과 삭제가 한쪽에서만 일어남 💡 파이썬 스택(stack) 연산 s.append(n): top 위치에 새로운 데이터(n)를 삽입 s.pop(): top 위치에 현재 있는 데이터를 삭제하고 확인 s[-1]: top 위치에 현재 있는 데이터를 단순 확인하는 연산 큐(Queue) 삽입과 삭제 연산이 선입선출(FIFO)로 이뤄지는 자료구조 FIFO(First In First Out) 가장 먼저 삽입된 데이터가 가장 먼저 나오는 구조 삽입과 삭제가 양방향에서 이뤄짐 💡 파이썬 큐(queue) 연산 s.append(n): rear 위치에 새로..
KT 에이블스쿨 AIVLE school 4기 AI트랙 14주차 후기
·
KT에이블스쿨
14주차 일정 11/06 IT 인프라 11/07 - 11/08 웹프로그래밍 11/09 - 11/10 WEB/WAS/DB 11/06 IT 인프라 몰아쳤던 미프기간이 끝나고 STEP 2 시작! IT 인프라는 말 그대로 인프라에 관련된 서버, 스토리지, 네트워크, 클라우드, 보안 등등등 모든 것을 배웠습니다.(?) 난 분명히.. 학교에서 전공 수업 열심히 들었는데.. 왜 이렇게 새로운 내용이지.. 시험지에 소설을 쓰고 나왔나.. 한 학기 내용을 하루 만에 다루다 보니 내용이 너무 많아서 어떻게 정리해야 할 지도 잘 모르겠다.. 이걸로 퉁! 11/07 - 11/08 웹프로그래밍 웹프로그래밍부터 WEB/WAS/DB까지는 하나의 프로젝트를 가지고 실습을 했다. 먼저, 웹 프로그래밍에서는 프론트엔드 개발을 위한 ht..