알고리즘 PS19 [2021] 11월 PS 기록 2021.11.20 - PS 기록 시작 실버랑 프로그래머스 레벨 1 문제 풀 수 있을 정도... 코딩 테스트에서 떨어지고 보니 내가 얼마나 안일하게 준비했는지 알겠다. 구현하기만 급급해 히든 케이스는 물론 다 풀지도 못했다. 내년에 다시 도전하기까지 매일 문제 하나씩 풀기가 목표다. 2022. 2. 1. [PS] PS 기록 목차 2021.11.20 - PS 기록 시작 2021-12월 기록 실버 2까지 레벨이 올랐다. 17일째 연속으로 문제 풀고 있는 중. 총 29문제 품. 12문제는 답안 안 보고 혼자서 품. 2022 2022-1월 기록 총 33문제 풀이, 13문제 스스로. 48일째 연속 문제 풀이. 2022. 1. 31. [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. [코테] 코딩테스트 cheat sheet (작성중) 목차 1. 입력 - 런타임 에러 (IndexError) 1. 입력 입력 범위를 잘 확인하자. 가끔씩 자연수 300 이하 이런 식으로 입력 범위가 주어지는 경우가 있다. 자연수: 양의 정수 (1, 2, 3...) 또는 음이 아닌 정수 (0, 1, 2, 3...)로 정의된다. 런타임 에러 (IndexError) 보통 백준에서 런타임 에러 (IndexError) 뜨는 이유가 이거다. 입력으로 0이 들어올 것을 예상 못 했거나, 재귀 또는 DP의 점화식이 3인데 3 이하의 수가 들어올 것을 예상 못하는 경우 런타임 에러 중 IndexError가 생긴다. 2022. 1. 20. [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: retu.. 2022. 1. 15. 이전 1 2 3 4 다음
