자유로운 개발자 FDEE

"그래프 이론"이란 코딩 테스트에서 자주 등장하는 기타 그래프 이론 공부하기 이론의 마지막 챕터로 그래프 이론에 대해 정리한다. 1. 서로소 집합 공통 원소가 없는 두 집합을 의미하며, 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 즉, 겹치지 않게 집합을 나누는 자료구조이다. 이때 두가지 연산이 사용된다. 1) union연산 : 두 원소를 하나의 집합으로 묶는다. 2) find연산 : 해당 원소가 어떤집합에 속하는지를 찾아준다. 이 연산을 통해 서로소 집합을 구현할 수 있다. 이때, 트리 자료구조를 사용하여 동일한 루트로 묶는것으로 집합을 나누게 된다. 1) union 연산 : 두 원소의 루트 중 작은원소를 루트로 삼아 묶는다. 2) find연산 : 해당 원소의 루트 원소를 반..

"최단 경로"란 특정 지점까지 가장 빠르게 도달하는 방법을 찾는 알고리즘 이번에는 DFS, BFS와는 별개로 최단경로에 관련하여 "다익스트라"와 "플로이드 워셜" 알고리즘에 대하여 알아보겠다. DFS, BFS와 차별점은 "간선의 값이 존재하며, 간선값에 따라 경로가 달라진다는 점이다" 그렇기에 GPS에서 소프트웨어의 기본 알고리즘으로 채택되는 중요한 개념이다. 먼저 "다익스트라" 알고리즘부터 알아보겠다. 1. 다익스트라 알고리즘 특정한 노드에서 출발하여 각 다른 노드까지의 최단 경로를 구해주는 알고리즘 다만, 음의 간선이 없을때 정상작동이 된다. 이때, 최단 거리 테이블 개념이 사용된다. import heapq import sys INF = int(1e9) input = sys.stdin.readline..

"다이나믹 프로그래밍"이란 한번에 계산한 문제는 다시 계산하지 않도록 하는 알고리즘 즉, 중복 계산하는 비효율적인 방법이 아닌, 한번만 계산하는 효율적인 알고리즘이 되겠다. 여기서 그러면 비효율적인 방법에 대한 대표적인 예시로 "피보나치 수열의 재귀함수" 방식을 보겠다. def fibo(x) : if x == 1 or x == 2 : return 1 return fibo(x-1) + fibo(x-2) 여기서 fibo(4)를 구한다고 보면 fibo(4) = [fibo(3) + fibo(2)] = [ [fibo(2) + fibo(1)] + [fibo(1) + fibo(0)] ] = [ [ [fibo(1) + fibo(0)] + fibo(1)] + [fibo(1) + fibo(0)] ] 즉, 같은연산이 중복된..

"이진 탐색" 이란 탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘 앞서 정렬의 방법에 대해 알아보았다. 정렬은 사실 "탐색"을 쉽게 하기 위한 선과정에 속하기도 하다. 그 이유에 대해서는 조금뒤에 알아보겠다. 먼저 탐색에 대해 알아보겠다. 1. 순차 탐색 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 이 방법은 구현하기 간단하며, 시간이 충분하다면 원하는 값을 찾을 수 있다. def sequential_search(n, target, array) : for i in range(n) : if array[i] == target : return i+1 n개의 데이터를 앞에서부터 하나씩 확인하기 때문에 최대 n번 확인한다는 점이 특징이다 시간복잡도 :..

"정렬" 이란 연속된 데이터를 기준에 따라서 순서대로 나열하기 위한 알고리즘 정렬의 경우 항상 사용하게 되는 기법중 하나이다. 최소값, 최대값을 구하기 위하여 정렬 후 맨앞, 맨뒤 데이터를 접근하기 때문이다. 또한, 정렬이 되면 뒤에서 배울 "이진탐색"이 가능하여 진다. 여기서 정렬의 방법이 다양하지만, 그중 4가지 정렬에 대하여 알아보겠다. 1. 선택 정렬 정렬이 안된 부분 중 가장 작은값을 맨 앞으로 보내는 방법이다. 이중 for문을 통해 구현한다. array = [7,5,9,0,3] 배열이 이렇게 주어져 있다면 for i in range(len(array)) : #작은값의 인덱스 min_index = i for j in range(i+1, len(array)) : if array[min_index]..

"DFS, BFS" 이란 그래프를 탐색하기 위한 대표적인 두 가지 알고리즘 여기서 탐색이란 "원하는 데이터를 찾는 과정"을 말하기에 그래프 탐색이란 "그래프 내에서 원하는 데이터를 찾는 과정"을 일컬는다. 여기서 기초적으로 그래프 탐색 전에 알아야 하는 자료구조 개념이 필요하다. 1. 스택 Stack 스택은 선입후출 구조로 쌓이는 구조라 생각하면 된다. 재귀함수에서 사용되며, 재귀함수는 DFS에서 사용된다. 2. 큐 Queue 큐는 선입선출 구조로 차례로 들어온대로 나가는 구조라 생각하면 된다. BFS에서 사용된다. 3. 재귀함수 Recursive function 재귀함수는 함수가 함수를 다시 부르는 경우이다. 보통 연쇄적으로 계산되는 경우 종료조건을 만족할때까지 재귀가 이뤄지다가 다시 반환되며 종료되는..

"구현" 이란 머릿속에 있는 알고리즘을 정확하고 빠르게 프로그램으로 작성하기 구현 파트는 다른 파트와는 다르게 별다른 특별한 방법없이 "묵묵히 주어진대로 구현" 하는 파트이다. 하지만 그래도 몇가지 특징이 있다. ✓ 완전탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 ✓ 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례로 직접 수행 일명 "피지컬" 이라고 불릴만큼 차근차근 잘 풀어내는 스킬이다. 여기서 개인적으로 느낀 키포인트는 " 반복문을 통해 전체 케이스를 올바르게 잘 나눌 수 있는가? " 이렇게 느껴진다. 여기서 중요한점은 " 입력 숫자의 범위 "와 " 제한된 용량 ", " 제한된 시간 "을 주의해야 한다는 점이다. 다른언어의 경우 int형을 벗어나는 경우 long long 형 ..

앞으로 한챕터가 끝나면 해당 챕터의 내용에 대해 간략하게 요약정리를 하며 글을 남기겠다. "그리디" 알고리즘이란 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘 이렇게 부제목이 달려있다. 보통 탐욕법(욕심쟁이 알고리즘) 으로 불리기도 한다. 그러면 이제 어떤상황에서 그리디가 사용되는가? ✓ 거스름돈 -> 가장 큰 화폐부터 지급 방법 ✓ 특정 수를 가장적은 횟수로 쪼개기 -> 정렬이 함께 사용되어 큰수 먼저 쪼개는 방법 사실 읽어보면 당연한거 아닌가? 싶은 느낌이 들기도 한다. 여기서 개인적으로 느낀 키포인트점은 반복문(while) 내에서 각 케이스에 해당되겠금 접근하는것도 맞는 방법이지만 "빼거나 나누는 큰수의 규칙을 찾아 한번에 계산되는 방법이 있을까?" 이것부터 생각해보는게 중요한 것 같다...

어제로부터 2020학년도 2학기가 종강되었습니다. 그리고 이제 방학이 시작되었습니다. 이번 방학때는 나동빈 저자의 "이것이 코딩 테스트다 with 파이썬" 책을 공부할 생각입니다. 내년 3학년부터는 인턴 및 코딩테스트를 지원해볼 생각이기 때문입니다. 따라서 공부를 하되 "1일1커밋"을 목표로 할 것 입니다. 책의 표지는 아래와 같이 생겼습니다. 오늘은 코딩을 공부하기에 앞서 저자가 코딩테스트에 대해 다룬 내용을 정리하겠습니다. 우선 이 책의 공부순서는 다음과 같습니다. 저는 지금까지 C++ 언어를 사용해 왔지만, 이번부터 파이썬을 새로 익힐 생각이기 때문에 부록 A부터 시작할 예정입니다. " 사이트 소개 " 다음으로는 소개한 사이트에 대해 포인트를 찾아봤습니다. 백준의 경우 "삼성 SW 역량테스트 대비 ..