알고리즘 PS/알고리즘8 [Python] 재귀함수 재귀함수란? 아마 다들 어디선가 이 글을 한 번쯤은 읽어봤을 것이다. (이거 보고 웃으면 빼빡 개발자...) 개발자들이 썰렁 개그에 진심인지라 개발자 커뮤니티에 재귀에 관해서 물어보면 꼭 이 농담이 나온다. 심지어 백준에는 이런 문제도 있다. 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net 필자도 처음에는 저게 무슨 소리야 했는데 지금 다시 보니 재귀에 대해서 꽤나 잘 설명한 유머다. 이렇게 개발자화가 되는 것인가... 그래서 진짜 재귀란? 재귀함수는(이하 재귀) 자기 자신을 호출하는 함수다. 맞는 정의이지만.. 2022. 6. 12. [Python] DFS & BFS DFS & BFS 란? 먼저 읽으면 좋은 글: [Python] 그래프 (인접 행렬, 인접 리스트) + DFS/BFS를 배우기 앞서 알아야 할 개념들 (탐색 알고리즘, 자료구조) 위에 글에서도 언급했듯, DFS(Depth-First Search)와 BFS(Breadth-First Search)는 그래프 탐색 알고리즘(Graph traversal algorithm)이다. 그래프 탐색 알고리즘이란, 그래프의 모든 꼭짓점(Node 또는 Vertex라 한다)을 방문하는 알고리즘을 의미한다. DFS vs BFS DFS와 BFS의 차이점은 바로 노드 방문 순서이다. DFS DFS는 깊이 우선 탐색이라는 그 이름답게 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 스택 자료구조를 사용하여 그래프의 가장 깊은 곳.. 2022. 3. 19. [Python] 이분/이진 탐색 이분/이진 탐색이란? 이분 또는 이진 탐색이라 불리는 이 탐색은(이하 이분 탐색) 탐색 범위를 반씩 좁혀가는 탐색하는 알고리즘이다. 이분 탐색은 결정 문제의 답이 이분적일 때, 그리고 데이터가 정렬되어 있을 때 사용할 수 있다. 보통 정렬되지 않은 리스트를 탐색해야 할 때 앞에서부터 순차적으로 확인하는 탐색인 순차 탐색을 쓰지만, 원소를 하나씩 확인해야 하기에 시간 복잡도가 O(n)이다. 그러나 이분 탐색은 계속해서 탐색 범위를 반으로 줄여나가기에 O(logN)으로 순차 탐색보다 빠르다. 구현 이분 탐색을 구현하는 방법에는 2가지가 있다. 하나는 재귀 함수, 그리고 다른 하나는 반복문을 사용하는 것이다. 재귀 함수로 구현 def binary_search(array, target, start, end): .. 2022. 3. 2. [Python/C] 반례/테스트 케이스 생성기 만들기 가끔 문제를 풀다 보면 예제도 다 통과했는데 도대체 왜 틀렸는지 알 수 없는 문제들이 있다. (왜맞틀?????) 그럴 때 진짜 답답해서 미쳐버릴 거 같은 심정으로 반례를 찾아 헤매는데 이게 찾기 쉽지 않다. 그럴 때는 반례 생성기를 만들어서 찾으면 된다. 이 반례 생성기는 백준 1654문제를 기준으로 만들었다. 1. 예제 생성 함수 우선 example()이라는 예제 생성 함수를 만든 뒤, 문제에 맞춰서 randint()으로 최소 값, 최대 값 주고 예제를 생성하면 된다. 원래 1 2022. 2. 26. [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. 이전 1 2 다음
