Algorithm
이진탐색
본 내용은 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 기반으로 포스팅 하였습니다. 이진 탐색에 대해 공부하기 전 가장 기본 탐색 방법인 순차 탐색에 대해 먼저 이해가 필요하다. 순차 탐색이란? 배열 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 보통 정렬되지 않는 배열에서 데이터를 찾아야 할때 사용한다. 순차 탐색 시간 복잡도 순차 탐색 알고리즘은 데이터 정렬 여부와 상관 없이 가장 앞에 있는 원소부터 하나씩 확인해야 하는 특징이 있다. 따라서 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하므로 순차 탐색의 최악의 경우 시간 복잡도는 O(N)이다. 코드 구현 let nameArr = ["Haneul","Jonggu","Dongbin"..
DFS/BFS
본 내용은 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 기반으로 포스팅 하였습니다. DFS란? 깊이 우선 탐색이라고도 부르며, 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘이다. 탐색을 수행함에 있어서 데이터의 개수가 N개인 경우 O(N)의 시간 복잡도를 가진다. DFS를 스택 자료구조를 이용하여 구체적인 동작 과정은 다음과 같다. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 2번의..
그래프
본 내용은 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 기반으로 포스팅 하였습니다. 그래프란? 노드(정점)와 간선(브랜치)으로 이루어진 자료구조이다. 그래프의 탐색이란? 하나의 노드를 시작으로 다수의 노드를 방문 하는 것을 말하며, 두 노드가 간선으로 연결되어 있다면 두 노드는 인접하다라고 표현한다. 간단하게 도시를 노드, 도로를 간선이라고 생각하면 이해하기 쉽다. 그래프의 종류 1. 방향 그래프 -. 간선에 방향이 있는 그래프로 간선 그래프 방향으로만 갈 수 있다. 2. 무방향 그래프 -. 간선에 방향이 없는 그래프로 노드는 양방향으로 갈 수 있다. 3. 가중치 그래프 -. 노드를 이동할 때 드는 비용, 또는 가중치가 할당된 그래프 4. 완전 그래프 -. 모든 노드가 간선으로 연결되어 있는..
재귀함수
본 내용은 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 기반으로 포스팅 하였습니다. 재귀함수란? 자기 자신을 다시 호출하는 함수를 말한다. 즉, 내 함수 안에서 내 함수를 호출하는 형태이다. func recursiveFunc() { print("재귀 함수를 호출합니다.") recursiveFunc() } recursiveFunc() 위 코드를 실행하면 "재귀 함수를 호출합니다." 라는 문자열이 무한히 출력된다. 재귀 함수를 사용할 때에는 재귀 함수가 언제 끝날지 종료 조건을 꼭 명시해 주어야 한다. ※ 종료 조건을 명시해주지 않는다면 함수가 무한히 호출되므로 주의! func recursiveFunc(i: Int) { if i == 100 { return } print("\(i) 번째 재귀 함..
스택/큐
본 내용은 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 기반으로 포스팅 하였습니다. 스택이란? 후입선출(LIFO) 구조로 쌓아 올린다는 것을 의미하며, 박스를 쌓아 올리는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말한다. 가장 마지막으로 들어온 자료를 TOP이라고 부르며, 삭제 연산을 수행하게 되면 가장 마지막으로 들어온 자료(TOP)가 삭제된다. 스택에서 삽입은 PUSH, 삭제는 POP이라는 용어로 사용한다. 이때 비어있는 스택에 삭제(POP) 연산을 수행하게되면 스택 언터플로우가 발생하고, 꽉 차있는 스택에 삽입(PUSH) 연산을 수행하게되면 스택 오버플로우가 발생한다. 소스코드 var stack = [Int]() stack.append(5) stack.append(2) stack.a..
탐색/자료구조
본 내용은 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 기반으로 포스팅 하였습니다. 탐색이란? 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이다. 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘 2가지 DFS - 깊이 우선 탐색 (그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘) BFS - 너비 우선 탐색 (가까운 노드부터 탐색하는 알고리즘) 위 두가지 알고리즘을 이해하려면 기본 자료구조인 스택과 큐에 대한 이해가 전제되어야 한다. 자료구조란? 데이터를 표현하고 관리하고 처리하기 위한 구조를 의미한다. 그중 스택과 큐는 자료구조의 기초 개념으로 다음 두 핵심적인 함수로 구성된다. 삽입 - 데이터를 삽입한다. 삭제 - 데이터..
구현 - 게임 개발(Swift)
본 내용은 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 기반으로 포스팅 하였습니다. 문제 저작권 문제가 될 수 있어 문제는 삭제합니다. 풀이 코드 입력 출력 4 4 1 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 3 // 초기 입력값 let n = 4 let m = 4 let input = "1 1 0" let inputMap = [[1,1,1,1],[1,0,0,1],[1,1,0,1],[1,1,1,1]] var map = Array(repeating: Array(repeating: [Int](), count: n), count: m) var start = input.components(separatedBy: " ").dropLast().map{Int($0)!} var di..