알고리즘과 입출력

시간 복잡도

---

Big - O 표기법

주어진 Input의 개수를 의미하는 n을 기반으로 명령어들의 연산이 몇 번이나 실행됐는지를 숫자로 표시하는 것이다.

Big - O : function ranking

 

Better

• O(1) - 상수 시간 : 문제를 해결하는데 오직 한 단계만 처리함.
• O(log(n)) - 로그 시간 : 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 따라 줄어듬.
• O(n) - 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력 값 n이 1 : 1 관계를 가짐.
• O(nlog(n)) - 로그 직선적 시간 : 문제를 해결하기 위한 단계의 수가 n*log(n)번 만큼의 수행시간을 가짐
• O(n^2) - 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력 값 n의 제곱.
• O(n^3) - 3차 시간 : 문제를 해결하기 위한 단계의 수는 입력 값 n의 세제곱.
• O(2^n) - 지수 시간 : 문제를 해결하기 위한 단계의 수는 상수 값의 n 제곱.

Worse

 

 

시간 복잡도를 구하는 요령

---

본래의 Big - O 표기법의 정의는 아래 써있는 것 보다 조금 복잡하지만, 대체로 아래와 같이 생각해도 일치한다.

(대략적으로 구하는 방식이므로 맹신하지 않는 것을 추천. 간단하게 구하면 이렇구나 정도로만 생각하자.)

• 하나의 루프를 사용하여 단일 요소 집합을 반복하는 경우: O(n)
• 컬렉션 절반 이상을 반복하는 경우: O(n / 2) ⇒ O(n)
• 두 개의 다른 루프를 사용하여 개별 컬렉션을 반복하는 경우: O(n + m) ⇒ O(n)
• 두 개의 중첩 루프를 사용하여 단일 컬렉션을 반복하는 경우: O(n ^ 2)
• 두 개의 중첩 루프를 사용하여 두 개의 다른 컬렉션을 반복하는 경우: O(n * m) ⇒ O(n ^ 2)
• 컬렉션 정렬을 사용하는 경우: O(n * log(n))

 

입력

---

Swift에서의 입력

readLine()

Swift의 표준 입력 함수로는 readLine()이 있다.

표준 입력으로부터 EOF에 도달할 때 까지 문자열 한 줄을 읽어서 반환하는 함수이다.

시작부터 EOF에 도달하는 경우에는 nil을 반환한다.

따라서 readLine()은 nil을 반환할 수도 있기 때문에 읽어온 문자열을 Optional 값으로 반환한다.

 

readLine()으로 입력 받는 예시

/* 단일 값 입력 받기 */
let str = readLine()! // 문자열
let N = Int(readLine()!)! // 정수

/* 여러 값 입력 받기 */
//공백으로 띄워짐
let strArr = readLine()!.split(separator: " ").map { String($0) } // 문자열(문자)
let NArr = readLine()!.split(separator: " ").map { Int(String($0))! } // 정수//공백으로 안띄워짐
let strArr = readLine()!.map { String($0) }// 문자
let NArr = readLine()!.map{ Int(String($0))! }// 정수

 

여러 값으로 입력 받아진 strArr상수와 NArr상수는 자동으로 배열 타입이 된다.

 

FileHandle class

또 다른 입력 방법으로는 FileHandle class를 이용하는 방법이 있다.

FileHandle은 파일 디스크립터를 객체 지향 API로 감싼 얇은 wrapper이다.

특정 경로 및 URL을 기준으로 쓰기/읽기 및 변경용으로 생성할 수 있으며, 동기 및 비동기식 파일 액세스를 지원한다.

이 클래스는 파일을 읽어오는 클래스인데, 알고리즘 문제를 풀 때 왜 귀찮게 이걸 사용하는 걸까?

사실 대부분 readLine()을 사용하고, readLine()으로도 문제를 풀기엔 충분하다.

하지만 readLine()의 경우 한번에 많은 양의 데이터를 읽어오는데는 시간이 얼마 안 걸리지만, 값이 쪼개져서 여러번 들어오게 되면 시간이 상당히 소모된다.

그래서 이를 이용해 readLine()보다 좀 더 빠르게 여러 개의 데이터를 받아오기 위해서 사용하는 것이다.

이는 라이노님이 만든 빠른 입출력 클래스를 사용하면 쉽게 사용할 수 있다.

import Foundation

// 라이노님의 FileIOfinal class FileIO {
    private var buffer:[UInt8]
    private var index: Int

    init(fileHandle: FileHandle = FileHandle.standardInput) {
        buffer = Array(fileHandle.readDataToEndOfFile())+[UInt8(0)]// 인덱스 범위 넘어가는 것 방지
        index = 0
    }

    @inline(__always) private func read() -> UInt8 {
        defer { index += 1 }

        return buffer.withUnsafeBufferPointer { $0[index] }
    }

    @inline(__always) func readInt() -> Int {
        var sum = 0
        var now = read()
        var isPositive = true

        while now == 10
                || now == 32 { now = read() }// 공백과 줄바꿈 무시if now == 45{ isPositive.toggle(); now = read() }// 음수 처리while now >= 48, now <= 57 {
            sum = sum * 10 + Int(now-48)
            now = read()
        }

        return sum * (isPositive ? 1:-1)
    }

    @inline(__always) func readString() -> String {
        var str = ""
        var now = read()

        while now == 10
                || now == 32 { now = read() }// 공백과 줄바꿈 무시

        while now != 10
                && now != 32 && now != 0 {
            str += String(bytes: [now], encoding: .ascii)!
            now = read()
        }

        return str
    }
}

let file = FileIO()

let testCase = file.readInt()

 

만약 유닉스 환경에서 사용한다면, EOF를 직접 넣어줘야한다.

EOF는 ctrl + d 로 넣을 수 있다.

 

C에서의 입력

scanf()

scanf()함수는 C의 표준 입력 함수로 괄호 안에 여러가지 format(서식 지정자)를 지정하여 입력을 받을 수 있다.

int val = 0;

scanf("%d", &val);

 

가장 기초적이자 기본적인 입력함수라 사람들이 많이 사용한다.

하지만 scanf에는 공백을 읽을 수 없다는 문제와 %c와 버퍼에 관련한 문제가 존재한다.

 

scanf가 공백을 읽을 수 있게 하는 법
플래그로 %[^\n]을 사용하면 된다.
이는 엔터를 제외한 모든 문자열을 받는다는 말이다.

 

버퍼와 scanf()의 고질적인 문제

컴퓨터가 만약 abcde를 입력받는다고 해보자.

컴퓨터가 각 문자를 입력받을 때마다 처리를 한다면 굉장히 비효율적일 것이다.

하지만 우리가 입력한 것을 다른 곳에 모아놨다가, 한 번에 처리한다면 훨씬 효율적일 것이다.

여기서 다른 곳, 즉 보관하는 곳이 버퍼(buffer)라는 것이다.

또한, 수 많은 버퍼 중에서도 키보드의 입력을 처리하는 버퍼는 입력 버퍼, 혹은 stdin(입력 스트림)이라 부르는 것이다.

다시 말해 우리가 키보드로 입력하는 모든 정보는 일시적으로 stdin에 저장됐다가 나중에 입력이 종료되면 한꺼번에 처리하는 것이다.

 

입력 종료 조건은 개행문자, 즉 엔터이다.

그런데 컴퓨터는 엔터를 받으면 엔터 이전 값만을 갖고 입력을 끝내는 것이 아니라, 엔터에 해당하는 개행문자를 버퍼에 저장하고 입력을 끝낸다.

숫자 1을 입력하면 stdin에는 "1\n"이 들어가있게 된다.

입력이 끝나면 컴퓨터는 scanf()함수를 이용해 stdin으로부터 숫자데이터를 얻어온다.

scanf()함수는 stdin에서 공백문자를 만날때 까지 데이터를 얻어온다.

'\n', '\t', ' '이 세 개의 문자를 만나면 scanf()는 입력을 종료한다.

scanf는 공백문자를 만나기 전까지 stdin에서 데이터를 가져간 후 버퍼에서 삭제해 버린다.

문제는 공백문자는 삭제하지 않는다는 것이다.

만약 1이 입력됐다면 버퍼에는 1\n이 들어가 있을 것인데, scanf는 1만 가져가서 버퍼에는 \n이 남게 되는 것이다.

사실 다른 플래그들은 버퍼에 '\n'이 남아도 아무 문제가 없다.

다른 값들은 '\n'값을 데이터로 가질 수 없기 때문이다.

따라서 다른 플래그의 값들은 \n만 남아있는 버퍼를 마주하면 무시하고 새 값을 넣어 진행이 된다.

 

하지만 하나의 문자를 받아오는 %c 플래그는 얘기가 다르다.

'\n'도 사실은 하나의 문자에 해당한다.

다른 플래그와는 다르게 '\n'을 값으로 가질 수 있는 %c 플래그는 '\n'만 들어있는 버퍼를 마주하게 되면, 가질 수 있는 값이므로 '\n'을 받아옴과 동시에 '\n'이 scanf()의 종료에 해당하므로 scanf()를 종료시킨다.

따라서 아래의 순서로 scanf()를 동작시키면, 사용자는 두 번 입력하는 것이 아니라 사실상 한 번만 입력하게 된다.

int a = 0;

char c = 'a'

scanf("%d", &a);// 입력 가능scanf("%d", &c);// 입력 무시됨

 

 

그렇다면 이 현상을 어떻게 해결할 수 있을까?

간단하다.

stdin을 비워주면 된다.

 

1. fflush(stdin);

말 그대로 "stdin을 비워버려라" 라는 의미이다.

하지만 gcc에서는 이런 작업을 수행하지 않을 가능성이 있어 추천하는 방법은 아니다.

 

2. getchar();

"stdin에서 한 문자를 읽어와서 그 값을 리턴한다"라는 의미이다.

'\n'만 남아있으므로 stdin을 비울 수 있다.

 

gets()

scanf()에는 여러 문제가 있어서 gets()함수를 사용하곤 한다.

char str[100];

gets(str);

 

 

scanf()와는 다르게 공백문자를 읽을 수 있어서, 한 줄을 입력할 때 gets()함수를 사용하곤 한다.

하지만 문자열을 받는 함수이므로 정수를 받으려면 형변환을 해야한다.

또 다른 문제로는 gets()함수에는 크기 제한이 없어서 저장할 문자열보다 큰 문자가 제공되면 에러가 난다.

 

fgets()

gets의 큰 문제점이었던 크기 제한이 걸려있는 함수이다.

char str[100];

fgets(str, sizeof(str), stdin);

 

 

• 첫번째 매개변수: 버퍼에 대한 포인터
• 두번째 매개변수: 문자열의 최대크기(\0 포함)
• 세번째 매개변수: file

 

사실 보통은 파일을 읽을 때 fgets()를 사용하는데, file대신 stdin을 넣으면 키보드 입력으로 바뀌게 된다.

 

출력

---

Swift에서의 출력

print()

Swift의 표준 출력 함수로는 print()가 있다.

Swift의 자동 타입 감지 덕분에 간단하게 사용할 수 있다.

print()로 출력하는 예시

let N = 123
let str = "hello"
let arr = [1, 2, 3, 4]
let tuple = (1, 2, 3, 4)

/* 숫자 출력 */
print(N)// 출력: 123
print(123)// 출력: 123

/* 문자열 출력 */
print(str)// 출력: "hello"
print("hello")// 출력: "hello"

/* 콜렉션 타입 출력 */
print(arr)// 출력: [1, 2, 3, 4]
print(tuple)// 출력: (1, 2, 3, 4)

 

예시를 보면 알 수 있듯이 컬렉션 타입도 통째로 출력이 가능하다.

Swift의 print()에는 특이한 점이 하나 있는데, 바로 개행문자가 기본으로 들어가 있다는 것이다.

사용자가 넣지 않아도 기본으로 개행문자를 넣어서 출력해준다.

 

"그렇다면 어떻게 개행없이 출력할 수 있을까?"

 

print()함수의 다른 매개변수인 terminator: 값을 ""로 채워주면 된다.

print("hello")// 실제 출력: hello\n
print("hello", terminator: "")// 실제 출력: hello

 

이런 식으로 사용하면 hello가 개행 없이 출력이 된다.

 

C에서의 출력

printf()

printf()함수는 C의 표준 입력 함수로 괄호 안에 여러가지 format(서식 지정자)를 지정하여 출력할 수 있다.

int val = 123;

printf("%d", val);

 

가장 기초로 배우는 함수이고, printf()를 제외한 출력함수가 마땅히 없어서 대부분 printf()를 사용한다.

리눅스 C라면 write()함수도 있긴 하지만, 대부분 리눅스가 아닐 것이기에 printf()만 얘기했다.