본문 바로가기

CS Study

 (29)
정렬 정렬이란?? - 데이터를 특정한 기준에 따라 순서대로 나열하는 것. - 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용됨. 1. 선택 정렬 - 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다. #직접 작성한 초기 코드 array=[7,5,9,0,3,1,6,2,4,8] for i in range(len(array)-1): min_num=array[i] num=array[i+1] index=i+1 for j in range(len(array)): if(jarray[j]: index=j num=array[j] if min_num>num: array[index]=min_num array[i]=num print(array) #답안 for i ..
DFS vs BFS 그래프를 탐색하는 방법에는 DFS, BFS가 있다. DFS는 Depth-First Search 즉 깊이 우선 탐색을 말하고, BFS는 Breadth-First Search 너비 우선 탐색을 말한다. (그래프란 node와 node를 잇는 edge로 이루어진 자료구조를 말한다.) 그럼 DFS와 DFS의 차이점을 알아보자. ✅ DFS의 개념 루트 노드에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 먼저 다 탐색하는 방식을 말한다. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다. BFS보다 간단하지만 느리다. ✅ BFS의 개념 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동한다. 루트 노드에서 시작해서 인접한 노드를 먼저 탐색을 하는 방식이다. 시작 정점으로부터 가까운 정점을 먼저..
DFS & BFS 그래프 탐색 알고리즘: DFS/BFS - 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다. * DFS/BFS는 코딩 테스트에서 매우 자주 등장하는 유형이다! - 스택 자료구조 stack = [] stack.append(5) stack.pop() # 최상단 원소부터 출력 print(stack[::-1]) # 최하단 원소부터 출력 print(stack) - 큐 자료구조 from collections import deque queue=deque() queue.append(5) queue.append(2) queue.popleft() print(queue) queue.reverse() print(queue) - 재귀 함수 자기 자신을 다시 호출하는 함수, 종료 조건을 무조건 포함해야한다. ..
구현: 시뮬레이션과 완전 탐색 구현이란? - 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 그럼 알고리즘 대회에서 구현 유형의 문제란? - 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭한다. ex. 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제 적절한 라이브러리를 찾아서 사용해야 하는 문제 1. 일반적으로 알고리즘 문제에서 2차원 공간은 행렬의 의미로 사용된다. 그리고 2차원 공간에서의 방향 벡터가 자주 활용된다. # 동, 북, 서, 남 dx = [0,-1,0,1] dy = [1,0,-1,0] # 현재 위치 x, y = 2, 2 for i in range(4): # 다음 위치 nx =..
그리디 그리디 알고리즘이란? - 현재 상황에서 지금 당장 좋은 것만 고르는 방법 - 정당성 분석이 중요 ➡️ 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토가 필요한 기법이다. (일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다.) EX. 거스름 돈 문제 문제: 1260원을 거슬러주어야 할 때 가장 적은 숫자의 화폐를 이용해 거슬러주는 경우에 대해서 찾아본다. 답: 최적의 해를 빠르게 구하기 위해 가장 큰 화폐 단위부터 돈을 거슬러주면 된다. N원을 거슬러줘야할 때, 가장 먼저 500원으로 거슬러 줄 수 있을만큼 거슬러 준다. 이후로 100원, 10원으로 거슬러주기 ➡️ 정당성 분석 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은..

티스토리툴바