이진탐색 데이터가 정렬되어있는 배열에서 중간값과 비교하며 특정한 값을 찾아내는 탐색 방법 구현 재귀 //재귀적으로 표현한 이분탐색 //11이 어디있는지 찾는 이분탐색입니다. var binaryArray = [0, 1, 4, 6, 8, 11, 14, 23, 24, 26, 28, 31, 41, 50] func recursiveBinary(array: [Int], target: Int, start: Int, end: Int) -> Int? { //시작점이 끝점보다 커지면? 이미 모든 영역을 탐색했다는 뜻 이겠죠? 모든 영역을 탐색했는데 타겟 숫자를 //못 찾았다면 nil을 리턴해 주도록 합시다. if start > end { return nil } //일단 반으로 나눌거니까 중간을 찾아줍시다. var mid ..

비트마스킹 컴퓨터는 내부적으로 모든 자료를 이진수로 표현한다. 이런 특성을 이용해 정수의 이진수표현을 자료구조로 쓰는 기법 비트마스크를 이용하면 더 빠른 수행시간, 더 간결한 코드, 더 적은 메모리 사용이 가능하다. 비트 연산자 비트마스킹은 기본적으로 비트를 다뤄야 하므로, 비트 연산자에 대해서 먼저 알아보자. a & b a의 모든 비트와 b의 모든 비트를 AND 연산한다. 둘다 1이라면 1, 아니면 0 ex) 100 & 111 = 100 a | b a의 모든 비트와 b의 모든 비트를 OR 연산한다. 둘다 0이라면 0, 아니면 1 ex) 010 | 111 = 111 a ^ b a의 모든 비트와 b의 모든 비트를 XOR 연산한다. 둘이 다르다면 1, 아니면 0 ex) 011 ^ 101 = 110 ~a a의..

백트래킹 모든 경우의 수를 고려하는 알고리즘. 답이될 수 없는 후보는 더이상 탐색하지 않고 다시 돌아가는 알고리즘 백트래킹 절차 DFS - 유망한 노드 검토 - 서브트리 이동 - 백트래킹 수행 DFS 수행 : 재귀를 호출하면서 DFS를 그대로 수행 유망한 노드 검토 : 유망한 노드면 서브트리로 이동하고, 그렇지 않으면 백트래킹을 수행해야함 서브트리 이동 : 방문한 노드의 하위 노드로 이동하여 다시 재귀를 통해 DFS 수행 백트래킹 수행 : 더이상 유효한 노드라고 생각되지 않으면 상위 노드로 백하여 백트래킹 수행 백트래킹 대표 예제 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러..

이 게시글은 개인적인 공부를 위해 작성된 게시물입니다. 이 글의 모든 출처는 https://babbab2.tistory.com/100 입니다. 동적 계획법 상향식 접근법으로 가장 작은 부분의 해답을 구한 후, 이를 저장하여 저장한 값을 이용해 상위 문제를 풀어가는 방법 동적 계획의 핵심은 Memoization(메모이제이션)이라는 기법인데 설명은 아래와 같습니다. 메모이제이션 동일한 계산을 반복해야할 때, 이전에 계산한 값을 메모리에 저장한 후 반복수행을 제거하여 프로그램 실행속도를 빠르게 하는 기법 피보나치 수열로 이해하기 0, 1, 2, 3, 5, 8, 13 ... 이런식으로 가장 처음 0, 1을 제외하고 내 앞의 두 놈을 더해서 나를 만드는 것이 피보나치 수열입니다. 재귀함수를 이용한 구현 func ..

이 글은 비전공자 취준생이 개인적인 공부를 위해 작성한 글입니다. 자세한 내용을 원하실 경우 https://yurimac.tistory.com/30, https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%83%90%EC%9A%95%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-greedy-algorithm/ 이곳을 방문해주시기 바랍니다. 이글의 출처는 위의 링크입니다. 그리디 알고리즘 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미합니다. 최적 해에 가까운 값을 구할 때 사용합니다. 매 순간마다 최적의 방법을 선택하여 값을 구하지만 결과적으로 최적 해라는 보장은 없습니다. 합이 가장 큰 값을 구해야하는 예제에서 다음 그림을 그..

이글은 비전공자 취준생이 개인적인 공부를 위해 작성한 글입니다. 자세한 내용은 https://babbab2.tistory.com/101 이곳에서 확인해주세요! 모든 이미지의 출처는 위의 티스토리임을 밝힙니다. 분할 정복 문제를 나눌 수 없을 때까지 나누어서 풀고, 나누어서 푼 문제를 다시 합병하여 답을 얻는 알고리즘 하양식 접근법으로 일반적으로 재귀함수로 구현합니다. 퀵 정렬 하나의 리스트를 pivot(기준점)을 기준으로 2개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 2개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게하는 방법입니다. 쉽게 생각하면 배열을 분할하고 정렬한 다음, 다시합치는 방법인 것 같습니다. 퀵정렬의 순서는 아래와 같습니다. 1. 기준점(pivot)을 ..

이 글은 개인적인 공부를 위해 작성된 글임을 밝힙니다. 자세한 내용은 https://babbab2.tistory.com/107 이곳을 확인해주세요! 깊이우선탐색(DFS) 탐색하려는 노드의 자식 노드부터 우선 탐색하는 방식 탐색 노드의 인접 노드의 자식 노드들을 모두 탐색하고, 다시 돌아가서 다른 인접노드의 자식들을 모두 탐색합니다. 탐색 노드의 가장 깊은 높드까지 다 탐색해야 다음 인접노드를 탐색할 수 있습니다. 구현 탐색할 그래프 미리 만들어두기 let graph: [String: [String]] = [ "A" : ["B", "C"], "B" : ["A", "D", "E"], "C" : ["A", "F"], "D" : ["B"], "E" : ["B"], "F" : ["C"], ] 깊이우선탐색을 하는 ..

이 글은 개인적인 공부를 위해 작성된 글임을 밝힙니다. 자세한 내용은 https://babbab2.tistory.com/106 이곳에서 확인해주세요! 너비우선탐색(BFS) Breadth-First Search 인접한 노드를 우선하여 탐색하는 방식입니다. 탐색 노드로부터 인접한 노드를 먼저 탐색하고, 다 탐색하면 인접한 노드의 인접한 노드들부터 탐색합니다. 따라서 같은 레벨에 있는 노드들부터 탐색하는 것처럼 보입니다. 참고로 왼쪽부터 탐색할지, 오른쪽부터 탐색할지 같은 순서는 중요하지 않습니다. 구현 1. 탐색할 그래프 미리 만들어두기 let graph: [String: [String]] = [ "A" : ["B", "C"], "B" : ["A", "D", "E"], "C" : ["A", "F"], "D"..