본문 바로가기

728x90

Algorithm36

[Algorithm] 합병 정렬(Merge Sort)란? (feat. Swift) 안녕하세요 Foma 💻 입니다! 오늘은 분할 정복 알고리즘 중 하나인 합병 정렬에 대해서 알아보려고 합니다. 바로 시작할게요~ 분할 정복(Divide and Conquer Algorithm) 알고리즘이란? 🏡 위에서 합병 정렬은 분할 정복 알고리즘 중 하나라고 말씀드렸는데요. 그렇다면 분할 정복 알고리즘은 무엇일까요? 말 그대로 지금 해결할 수 없는 문제를 작게 쪼개서(분할) 풀어나가는(정복) 것입니다. 작은 문제를 해결하여 큰 문제를 해결해나가는 알고리즘으로 재귀 함수를 통해 자연스럽게 구현할 수 있습니다. 합병 정렬이란? 🤼‍♀️ 합병 정렬 또는 병합 정렬은 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. 존 폰 노이만이 1.. 2021. 10. 14.

[Algorithm] 시간복잡도(Time-Complexity)란? (feat. Big O) 안녕하세요 Foma 💻 입니다! 요즘 들어 알고리즘 공부를 하는데 알고리즘의 핵심인 시간복잡도에 대해서 정리하지 않은 것 같아서.. 이번 기회에 구체적으로 시간복잡도에 대해서 정리해보겠습니다! 바로 시작할게요~ 시간복잡도란? ⏱ 컴퓨터공학 용어로, 컴퓨터 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도이다. 일반적으로 시간 복잡도는 점근 표기법을 이용하여 나타낸다. 즉, 계산되는 양에 따라서 시간이 얼마나 걸릴지를 나타내는 것입니다. 시간복잡도 표기법 🖊 시간복잡도 표기법은 빅오메가,빅세타,빅오 이렇게 3가지가 있습니다. 1. BigΩ (Best case) 빅오메가 표기법은 최선의 실행시간 즉, 가장 빠른 케이스를 나타내는 것입니다. 2. Big𝚯 (Average case) 빅세타 표기법은.. 2021. 9. 29.

[Algorithm] 삽입 정렬(Insertion Sort) 이란? (feat.Swift) 안녕하세요 Foma💻 입니다! 오늘은 학교 알고리즘 수업을 듣는 중에 삽입 정렬을 구현해보는 과제가 있었는데... 딱 이 방식이 어떤 것이고 어떻게 구현해야 한다! 라고 구체적으로 떠오르지가 않더라구요... 그래서 삽입 정렬이 무엇이고 어떻게 구현해야 하는지에 대해 정리해보려고 합니다! 바로 시작할게요~ 삽입 정렬이란? 삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. -위키 백과 - 정렬하는 과정을 살펴보면 아래와 같습니다. 삽입 정렬 과정 82,10,9,72,31,45,60를 삽입 정렬을 하는 과정은 아래와 같습니다. 1. 먼저 맨 첫 번째인 82와 그 다음 숫자인 10을 비교해줍니다. 10이 더.. 2021. 9. 28.

[Algorithm] 백트래킹(Backtracking)이란? (feat. 예제포함) 안녕하세요 Foma 💻 입니다! 오늘은 프로그래머스 N-Queen 문제를 풀면서 해당 문제가 백트래킹 문제라는 것을 알게 되었는데요. 그래서 백트래킹이 무엇이고 어떻게 구현해서 사용해야 하는지에 대해 정리해보려고 합니다. 바로 시작할게요~ 백트래킹이란? 모든 경우의 수를 전부 고려하는 알고리즘 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다. 방식에 따라서 깊이우선탐색(Depth First Search, DFS)과 너비우선탐색(Breadth First Search, BFS), 최선 우선 탐색(Best First Search/HeuristicSearch)이 있다. 모든 경우의 수를 고려해야 하는 문제라면, DFS가 낫다. BFS로도 구현이 물론 가능하지만,.. 2021. 8. 28.

[Swift] 프로그래머스 N-Queen Problem 코딩테스트 연습 - N-Queen 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 programmers.co.kr Solution 해당 문제는 백트래킹(DFS)으로 풀어야 하는 문제입니다. 1. 각 행마다 퀸을 놓을 수 있는 위치를 체크한다. 각 행마다 퀸은 하나씩밖에 못놓으므로 현재 행의 열들에 공격할 수 있는 퀸이 있는지 체크합니다. 만약 공격할 수 있는 퀸이 없다면 현재 위치를 history(퀸의 위치를 저장하는 2차원 배열)에 저장해놓고 다음 행으로 진행합니다. 이렇게 진행하면서 가장 마지막 행까지 도달한 경우는 배치할 수 있는 경우이므로.. 2021. 8. 28.

[Algorithm] 조합(Combination)이란? (feat.Swift) 안녕하세요 Foma 👟 입니다! 오늘은 알고리즘 문제에서 정말 빈번하게 사용되는 "조합" 에 대해서 알아보도록 하겠습니다. 바로 시작할게요~ 조합이란? n개의 원소에서 r 개의 원소를 순서에 상관없이 뽑는 경우의 수 - 나무 위키 - 순열과 다르게 순서는 중요하지 않아요. 쉽게 설명하면 물건을 사고 총 가격을 구하는 것과 비슷해요. 과일로 예를 들면 사과,포도,수박이 있다면 사과,포도,수박 포도,사과,수박 수박,사과,포도 ... 등 어떤 방식으로 사도 총 가격을 똑같겠죠? 즉, 이루어진 과일이 똑같다면 하나의 조합으로 생각하는 것입니다. 코드 구현 먼저 경우의 수를 담을 배열을 만들어줍니다. var cases:[[Int]] = [] combination의 파라미터를 설정해주는데 인덱스들을 담고있는 ind.. 2021. 6. 27.

[Algorithm] 순열(Permutation)이란? (feat.Swift) 안녕하세요 Foma 👟 입니다! 오늘은 알고리즘 문제에서 정말 빈번하게 사용되는 "순열"에 대해서 알아보도록 하겠습니다. 바로 시작할게요! 순열이란? 서로 다른 n개의 원소에서 r개를 중복없이 골라 순서에 상관있게 나열하는 것을 이른다. - 나무 위키 - 쉽게 설명하면 줄 세우기와 똑같아요. A,B,C라는 학생을 줄 세우는 방법은 ABC,ACB,BAC,BCA,CAB,CBA 등이 있겠죠? 이 중에서 2명의 학생으로 줄 세우는 방법은 AB,AC,BA,BC,CA,CB 등이 있을거에요. 코드 구현 경우의 수들을 담을 이중 배열을 만들어줍니다. var cases:[[Int]] = [] 몇 개를 뽑을지 정해줍니다. let pickCount = 3 본격적으로 순열 함수를 만들어줍니다. 파라미터로는 전체 인덱스가 담긴.. 2021. 6. 27.

[Algorithm] 너비우선탐색(BFS,Breadth-First-Search)란?(feat.Swift) 안녕하세요 Foma 👟 입니다! 오늘은 트리를 탐색하는데 쓰이는 알고리즘인 너비우선탐색(BFS)에 대해서 알아보도록 하겠습니다. 바로 시작할게요~ BFS란? 너비 우선 탐색은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. 큐를 사용해야만 레벨 순서대로 접근이 가능하다. - 위키 백과 - 쉽게 예제를 통해서 설명드릴게요! 아래 사진과 같이 지구 안에 세 나라만 있고 모든 나라와 나라의 도시들을 탐색한다고 가정하겠습니다. 탐색하는 방법은 여러가지가 있겠지만 먼저 지구에 있는 나라를 왼쪽부터 어떤 도시들이 있는지 확인하고 넘어가는 방법은 DF.. 2021. 6. 27.

[Algorithm] 깊이 우선 탐색(DFS,Depth-First-Search)이란? (feat.Swift) 안녕하세요 Foma 👟 입니다! 오늘은 알고리즘 문제에서 엄청 빈번하게 출제되고 알아두면 정말 유용한 DFS에 대해서 알아보도록 하겠습니다. 바로 시작할게요! DFS란? "깊이 우선 탐색은 맹목적 탐색 방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다." - 위키 백과 - 이게 뭔말이야....;;; 쉽게 예제를 통해서 설명드리겠습니다. 아래 사진과 같이 지구 안에 세 나라만 있고 모든 나라와 나라의 도시들을 탐색한다고 가정하겠습니다. 어떤 사람은 "난 먼저 어떤 나라들이 있는지 부터 확인하고 그 나라 안에 있는.. 2021. 6. 5.

[Swift] 2018 KAKAO BLIND RECRUITMENT [1차] 추석 트래픽 Problem 2021. 5. 19.

[Swift] 프로그래머스 약수의 개수와 덧셈 Problem 코딩테스트 연습 - 약수의 개수와 덧셈 두 정수 left와 right가 매개변수로 주어집니다. left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하도록 solution 함수를 완성해주 programmers.co.kr Solution left부터 right까지 숫자를 1부터 n까지 나누면서 나머지가 0인 숫자의 갯수(약수)를 구한다. 만약 약수의 갯수가 짝이라면 n을 더해주고 홀이면 -n을 더해준다. Source Code 다른 사람 풀이 제곱근에 소수점이 없으면 약수의 갯수가 홀수고 있으면 짝수임. import Foundation func solution(_ left:Int, _ right:Int) -> Int.. 2021. 5. 18.

[Algorithm] 플로이드 와샬(Floyd Warshall) 알고리즘이란? (feat.Swift) 안녕하세요 Foma🍍 입니다! 오늘은 그래프 문제에서 아주 빈번하게 사용되는 플로이드 와샬이라는 알고리즘에 대해서 알아보겠습니다. 바로 시작할게요! 플로이드 와샬이란? 🤔 위키 백과에는 다음과 같이 정의되어있습니다. "플로이드 와샬 알고리즘은 변의 가중치가 음이거나 양인 (음수 사이클은 없는) 가중 그래프에서 최단 경로들을 찾는 알고리즘이다." 쉽게 말하면 모든 최단 경로를 찾는 알고리즘이에요. 그래프 설명 아래와 같은 그래프가 있다고 가정할게요. (파란색 동그라미는 정점, 사이에 숫자는 거리입니다.) 만약 1번 정점에서 3번 정점으로 가려면 어떤 정점을 이용해야 가장 짧을까요? 정답을 알기 위해선 중간에 모든 정점을 거쳐서 간 다음 가장 짧은 거리를 구해야 할 것 입니다. 1번 -> 2번 -> 3번 3.. 2021. 5. 17.

이전 1 2 3 다음

728x90

티스토리툴바