알고리즘6 [2022] 6 & 7월 PS 기록, 그리고 현재 (+PS 어떻게 공부했는지) 오랜만에 PS 기록을 쓴다. 왜 이렇게 오랜만에 쓰냐... 실은 여기에 슬픈 사정이 있다. PS기록만 안 올렸지, 8월까진 열심히 1일 1PS를 지키고 있었는데 8월 8일 폭우가 온 날, 딱 서울에 있었어서 정신없어서 백준 문제를 못 풀었고 그렇게 내 스트릭은 끊겼다... 그리고 다시 PS를 시작하지 않은 이유는 내가 7월에 42서울을 시작하고 여기에 집중하느라 백준 문제를 풀 시간이 없어서 브론즈 문제들로 스트릭을 "연명"하고 있던 것이나 마찬가지였다. 예시로, 6월에는 골드 문제들도 푸는 등 차근차근 어려운 문제들을 풀고 그랬는데 7월에는 거의 브론즈 문제들만 풀었다. 스트릭이 아까워서 풀고는 있었지만, 스스로도 이것이 과연 맞는 것일까, 이게 나에게 도움이 되는 일인가 생각하고 있었다. PS를 하다.. 2023. 2. 25. [Python] 이분/이진 탐색 이분/이진 탐색이란?이분 또는 이진 탐색이라 불리는 이 탐색은(이하 이분 탐색) 탐색 범위를 반씩 좁혀가는 탐색하는 알고리즘이다. 이분 탐색은 결정 문제의 답이 이분적일 때, 그리고 데이터가 정렬되어 있을 때 사용할 수 있다. 보통 정렬되지 않은 리스트를 탐색해야 할 때 앞에서부터 순차적으로 확인하는 탐색인 순차 탐색을 쓰지만, 원소를 하나씩 확인해야 하기에 시간 복잡도가 O(n)이다. 그러나 이분 탐색은 계속해서 탐색 범위를 반으로 줄여나가기에 O(logN)으로 순차 탐색보다 빠르다. 구현이분 탐색을 구현하는 방법에는 2가지가 있다. 하나는 재귀 함수, 그리고 다른 하나는 반복문을 사용하는 것이다. 재귀 함수로 구현def binary_search(array, target, start, end): .. 2022. 3. 2. [Python] 그래프 (인접 행렬, 인접 리스트) + DFS/BFS를 배우기 앞서 알아야 할 개념들 (탐색 알고리즘, 자료구조) 탐색 알고리즘DFS(Depth-First Search)와 BFS(Breadth-First Search)는 탐색 알고리즘이다. 그렇담, 탐색이란 무엇일까? 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 탐색 알고리즘의 종류는 굉장히 다양한데 그중 DFS와 BFS는 그래프 탐색 알고리즘(Graph traversal algorithm)에 속한다. 그래프 탐색 알고리즘이란, 그래프의 모든 꼭짓점(Node 또는 Vertex라 한다)을 방문하는 알고리즘을 의미한다. 트리 탐색은(Tree traversal) 그래프 탐색의 특수한 일종이며, 방문한 노드는 다시 방문하지 않는다. 그래프그래프는 노드(Node)와 간선(Edge)으로 이루어진 자료구조의 일종이다. 자료구조 & 알고리즘이란:더보.. 2022. 1. 30. [Python] 백트래킹 (+ DFS와 차이) 백트래킹이란?백트래킹이란 현재 상태에서 가능한 모든 경로를 따라 들어가 탐색하다, 원하는 값과 불일치하는 부분이 발생하면 더 이상 탐색을 진행하지 않고 전 단계로 돌아가는, 즉 이름 그대로 방금 왔던 길을 되짚어가는, backtrack 하는 알고리즘이다. 백트래킹과 DFS의 차이처음 백트래킹을 접했을 때, 아래와 같이 생각했다. 그런데 공부하면 공부할 수록 아래에 더 알맞다는 걸 깨달았다. 백트래킹이랑 DFS(Depth First Search) 모두 탐색하는 알고리즘이라 혼동하기 쉽다. 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 백트래킹이랑 DFS 모두 원하는 값을 찾기 위해서 다양한 방법을 사용하는데 여기에서 차이가 발생한다. 우선 백트래킹은 불필요한 탐색을 하지 않는.. 2022. 1. 18. [Python] 다이나믹 프로그래밍 (DP) 다이나믹 프로그래밍이란?복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 의미한다. 문제를 여러 개의 하위 문제로 나누어 푼 다음, 그 결과들을 결합하여 답을 구한다. 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는, 메모리 공간을 조금 더 사용함으로 연산 속도를 늘릴 수 있는 알고리즘 설계 기법이다. 예시이렇게 글로만 보면 확 와닿지 않는다. 그럼 예시를 한 번 보도록 하자. 다이나믹 프로그래밍(이하 DP)으로 해결할 수 있는 대표적인 문제 예시로 피보나치 수열이 있다. n번째 피보나치 수는 n-1번째 수 더하기 n-2번째 수이다. 이걸 정리하면 f(n) = f(n-1) + f(n-2)이다. def fibo(n): if n == 0: .. 2022. 1. 15. [Python] 소수 찾기 알고리즘 소수란?1보다 큰 자연수 중, 1과 자기 자신 외에는 나누어지지 않는 수 누가 알고리즘 문제를 만드는지 모르겠으나 이 사람들 소수 찾기에 진심이다. 학교에서 수학 배울 때 빼고 단 한 번도 신경 쓰지 않았던 소수, PS 하다가 소수 문제가 하도 많이 나와, 한 번 정리해야겠다 싶어 정리한다. 소수 찾기 알고리즘소수 찾는 방법은 여러 가지가 있다. 소수인지 판별이 필요한 수를 n이라고 하겠다.1. 숫자 n 나누기2부터 n-1까지 나누기def isPrime(n): if n n-1까지, n이 1과 자기 자신 외의 수로 나누어지는지 판단하는 알고리즘이다. 만약 나누어진다면 바로 false를 리턴한다. n-1까지 걸리지 않는다면 True가 리턴된다. 가장 간단하고, 기초적이지만 오래 걸린다. 2부터 n-1까지의 .. 2021. 12. 20. 이전 1 다음
