Swift로 코딩테스트 시작하기, 시간복잡도, 공간복잡도, 입출력

 

 

 

 

 

"무엇"을 사용해서 코딩테스트를 준비해야 하나?

 macOS > Command Line Tool(명령어 라인 도구)로

새로운 프로젝트를 생성합니다.

 

 

🤷‍♂️: 왜 playground에서 실행 안 하고 Command Line Tool에서 실행하는 걸까요?

 

🐶: 대부분의 OJ 플랫폼에서는 직접 입출력 부분까지 구현해야 합니다.

playground에서는 readLine() 메서드를 사용할 수 없기 때문에 Command Line Tool을 사용해야 합니다.

또한 playground에서는 REPL(Read-Equal-Print Loop) 방식으로 동작하기에 디버깅이 어렵습니다.

 

이런 이유로 코딩테스트를 준비하기 위해서는 Command Line Tool을 사용합니다.

 

 

 

 

---

"어디서" 코딩테스트를 연습할 수 있는가? 

일반적으로 코딩테스트를 위해

1. 백준(https://www.acmicpc.net/)

2. 프로그래머스(https://programmers.co.kr/)

OJ 사이트들을 이용합니다

 

help.acmicpc.net/language/info

백준 채점 서버는 위와 같은 기준을 가지고 있습니다.

 

 

---

"어떠한" 배경지식이 필요한가?

어떤 시험에서도 그렇듯. 코딩테스트에는 유형이 존재합니다.

 

 

그래프(BFS&DFS), 백트랙킹, DP, Greedy
투포인터, 이진검색트리, 스택, 큐, 디큐, 우선순위큐,
해시, 위상정렬, 플로이드, 다익스트라 KMP, 완전탐색, 구현
등... 등..

 

이렇게 많은 유형들에 대처하기 위해서는 알고리즘과 자료구조에 대한 기초 지식이 필요합니다.

 

 

또한 문제풀이의 주춧돌은 문제를 분석하는 것입니다.

아무리 많은 유형을 알고 있다고 해도, 문제에 가장 적합한 풀이 방식을 찾아내는 것이 중요합니다.

 

더 구체적으로 말하자면,

 

일반적으로 코딩테스트에서는 시간과 공간에 대한 제한 사항이 존재합니다.

그리하여 여기서 주춧돌은 이의 복잡도에 대한 개념이 됩니다.

 

알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도라고 합니다.

 

 

 

 

 

 

---

시간복잡도

시간복잡도는 실행에 필요한 시간을 평가한 것입니다.

실행시간은 대체로 입력의 크기와 함께 성장합니다.
평균실행시간(Average case)은 결정하기 어렵습니다.

그래서 최악실행시간(Worst case)에 집중합니다.

최악 실행 시간은 시간 복잡도의 분석이 비교적 용이합니다.

 

그런데 매번 엄밀하게 시간을 Counting 할 수 있을까요?

그래서 점근 분석법 Big-O notation을 이용합니다.

 

 

 

 

Big-O 표기

시간복잡도를 표기하는 데는 Big-O 표기법을 사용합니다.

점근 분석법에 의하여 주어진 식의 값에서 가장 큰 대표항만 남겨 나타내는 방법입니다.

단순하게 상수항 무시하고, 계수 무시하고, 최고차항만!

관찰하면 끝입니다.

 

Big-O 표기 예시는 이와 같습니다.

O(N) = 6, 3

O(N) = 7N - 2, 3N + ㏒ N

O(N²) = N² + 2N

 

 

 

아래 코드를 예시로 시간 복잡도를 계산해봅시다!

이 함수에서는 sum에 0을 넣는데 1번,

반복문을 배열의 수만큼 수행하는데 N번,

값을 반환하는데 1번이라고 하면,

N + 2 = O(N)의 시간복잡도를 가집니다.

 

 

 

 

 

Swift에서는 간편하게 연산을 지원하는 함수가 많습니다.

이 함수들의 시간복잡도는 apple documentation에서 확인 할 수 있습니다.

 

Swift | Apple Developer Documentation

 

 

 

 

 

 

그럼 이 시간복잡도에 대한 배경지식을 통해서, 코딩테스트의 시간 제한을 어떻게 알 수 있을까요?

코딩테스트에서 채점서버는 일반적으로 1초에 약 1억(10^8) 개의 연산을 한다고 합니다.

 

우리는 Big - O로 도출한 시간복잡도를 기반으로 적합한 자료구조와 알고리즘 풀이 방식을 선택해

문제의 제한을 피하는 풀이를 고안해내야합니다.

 

 

 

 

 

---

공간복잡도

공간복잡도는 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것입니다.

프로그래머스에서 Swift에서 메모리 제한이 걸려있습니다.

메모리 512MB는 어느 정도의 공간을 얘기하는 걸까요?

 

 

 

 

데이터의 가장 최소단위는 비트(bit)입니다.

비트는 0과 1로 표현하는 데이터로 컴퓨터가 정보를 처리하고 저장하는 가장 기본적인 형태입니다.

전류가 흐르면 1, 전류가 흐르지 않으면 0으로 데이터를 처리합니다.

 

 

 

 

그다음의 가장 기본적인 단위는 바이트(Byte)입니다.

문자 하나를 나타내는 데 흔히 사용됩니다.

1 Byte는 8 Bit로 이루어져 있습니다.

 

다시 돌아와서 우리가 주목했던 512MB는 얼마인지 계산하겠습니다.

 

1 Byte = 8 Bit

4 Byte = 32 Bit

 

2¹⁰ = 1024 ≈ 10³

2³² = 2¹⁰ × 2¹⁰ × 2¹⁰ × 2² ≈ 4 × 10⁹

 

2³² ≈ 40억

 

1 GB = 10⁹ Byte
512MB = 5 ×10⁸ × 1Btye
512MB = 1.25 × 10⁸ ×4Btye

512MB ≈ 약 1.2 × 10⁸ 개의 Int 32 (= 4 Byte)

 

 

 

 

 

 

🤷‍♂️ : 그런데 왜 1Byte는 8개의 Bit를 하나의 단위로 사용했을까요?

 

 

프로그래밍은 영어권에서부터 발전해 왔음에 주목할 필요가 있습니다.

8비트는 256가지의 고유한 값을 나타낼 수 있어, 대소문자 알파벳, 숫자, 특수 문자 등 기본 문자들을 표현할 수 있습니다.

이는 초기 컴퓨터 사용에 있어서 효율적인 데이터 처리와 표현 범위를 제공했습니다.

 

 

 

 

---

입출력하기

Swift에서는 readLine 함수를 통해서 입력을 받습니다.

 

 

 

 

 

공백을 포함해서 배열을 받고 싶다면

split으로 공백을 처리하고

map 함수를 통해 Int 값으로 받을 수 있습니다.