Baekjakka

387.First Unique Character in a String

문제

• 문자열이 주어지면, 처음으로 반복되지 않은 문자의 인덱스를 찾아라. 반복되지않는 문자가 없다면 -1을 리턴하기

Examples:

    s = "leetcode"

    return 0.

    s = "loveleetcode"

    return 2

Note

• 문자열은 모두 소문자라고 가정합니다.

Solution 1. 앞에서부터 비교하기
1번 문자가 다음번째랑 같은지 안같으면 다음과 같은지 비교하다 같으면 2번 문자부터 순차적으로 비교하기
     1......n
      2.....n
       3...n

Solution 2. Map활용하기
문자를 Key, 갯수를 Value로 만들기 ( 1...n )

문자열의 앞의 문자부터 순서대로 Map의 키로 전달해 Value를 확인하여 1인 문자가 나오면 해당 인덱스를 반환한다.

( 1...n )

1번의 방법은 너무 많은 반복이 일어날 수 있다. 맨 마지막의 문자가 1번 쓰였을 경우 n번, n-1번, n-2번, ...., 2번, 1번의 경우까지 확인하는 경우도 있어 좋은 방법이라고 생각되지는 않는다.

2번의 경우는 문자열을 처음부터 끝까지 2번만 움직여보면 확인할 수 있는 방법이다.

처음에는 Map에 해당 문자별 갯수가 몇개인지 넣어두고

두번째는 문자열의 순서에 맞게 해당 문자의 갯수가 몇개인지 확인하여 해당 문자의 인덱스를 찾으면 된다.

Tip

Code

• Github : 387.First Unique Character in a String

Reference

• 387.First Unique Character in a String

알고리즘 문제를 보면 해결할 방법이 여러가지인게 재밌는 부분인것 같다. 물론 방법이 여러가지라고 모두 좋은 방법만 있지는 않지만 생각하지 못했던 방법을 보고 공부가 되기도하고 생각하는 방법이 늘어나 재밌는 것 같다.

이번에 풀어볼 문제는 Leetcode라는 사이트에 있는 문제입니다.

344. ReverseString이란 문제이며 난이도는 easy 입니다.

코드는 아래의 링크를 통해 확인해볼 수 있습니다.

문제 : 문자열을 Reverse(뒤집는)하는 함수를 만들어라.

    조건 1. 입력 문자열을 char[] 형태로 제공된다.
    조건 2. 다른 Array에 추가 공간을 할당하지 않는다.
    조건 3. 모든 문자는 출력가능한 아스키 문자로 구성된다고 가정한다.

Example 1
    Input: ["h","e","l","l","o"]
    Output: ["o","l","l","e","h"]

Example 2
    Input: ["H","a","n","n","a","h"]
    Output: ["h","a","n","n","a","H"]

Solution 1. 반복문 활용하기
    Input 문자열의 크기만큼 반복문을 사용해 역순으로 출력하기

Solution 2. 반복문 활용하기
    Reverse는 뒤집는 것이므로 1 2 3 4 5 가 있을 때 5 4 3 2 1 이 되야 하는 것.
    1 2 3 4 5
    5 4 3 2 1
    이 형태를 보면
    1과 5를 바꾸고
    2와 4를 바꾸는 형태임을 확인할 수 있다.

    즉, Swap하면 n번의 반복문이 절반으로 줄어들 수 있게 된다.

Solution 3. 제공되는 함수 활용하기

주의사항
    main에 있는 원본 Input에 변화가 생길 수 있다.

    1번은 역순으로 출력을 하여 원본에 변화가 생기지 않지만,
    2번과, 3번은 원본에 변화가 생기게 되므로 주의해야한다.

    만약 원본이 변하지 않길 바란다면 s를 그대로 넘겨주지 말고
    s.copyOf(), s.clone() 를 이용하면 된다.

    위의 이미지는 디버깅을 했을 때 나타나는 값들이다.

    s는 원본 데이터

    copyOfs는 s.copyOf()의 결과

    cloneS는 s.clone()의 결과

    이미지를 보면 알 수 있듯이 각각 다른 객체임을 확인할 수 있다.

    그럼 정말로 객체를 함수에 넘겨주었을 때 같은 객체가 넘어가는지 아래의 이미지를 통해 확인해보겠습니다.

    먼저 main의 s객체를 보면 @818임을 확인할 수 있다.

   main에서 reverseString1() 함수의 파라미터로 넘겨주고 함수에서 s객체를 확인해보면 아래와 같다.

    main의 객체와 같은 객체임을 확인할 수 있다. 따라서 함수에서 객체의 변화를 주면 함수안에서만 변화가

    일어나는 것이 아니라 밖에서도 변화가 유지될 수 있으므로 주의하는게 좋다.

copyOf()로 얻은 객체와, clone()으로 얻은 객체가 다른 객체임을 확인해봤는데 이들을 비교하면 어떤 결과가 나오게될지 궁금해져 비교를 해보게 되었다.

s == s.copyOf()
s == s.clone()

s.equals(s.copyOf())
s.equals(s.clone())

위의 결과가 어떻게 나오게 될까?

결과

더보기

s == s.copyOf() // false
s == s.clone() // false

s.equals(s.copyOf()) // false
s.equals(s.clone()) // false

 생각했던대로 결과가 나왔나요? 위의 코드는 같은 코드이기에 같은 결과를 얻게됩니다.

만약 객체의 내용물을 비교하고 싶다면 어떻게 해야 했을까요? contentEquals()라는 메서드를 사용하면 됩니다.

 

아래의 이미지를 통해 결과를 확인해볼 수 있습니다.

 

Code

• Github : 344.ReverseString.kt

Reference

• 344.ReverseString

문제

수많은 마라톤 선수들이 마라톤에 참여하였습니다.

단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때,

완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

해결 방법 : 배열의 정렬을 활용

public static String solution(String[] participant, String[] completion) {
	Arrays.sort(participant);
	Arrays.sort(completion);
	int index = 0;
	for(String c : completion) {
		if(!c.equals(participant[index]))
			return participant[index];
		index++;
	}
	return participant[participant.length-1];
}

참여한 사람들과 완주한 사람들을 담아둔 배열을 정렬시키고,

배열의 처음부터 순차적으로 비교해나가며 완주하지 못한 선수를 찾아내도록 만들었다. 

위의 코드는 완주한 사람을 배열에서 값을 순차적으로 가져와 같은 인덱스의 참여한 사람 배열의 값을 비교해 같은 값인지 확인한다.

equals() vs ==

String은 참조변수라서, ==으로 비교할 경우 객체가 같은가를 비교하게 되므로, equals를 사용하여 내용이 같은지 비교하도록 했다.

Arrays.sort() 시간 복잡도 : O(nlogn) or O(n^2) // O(nlogn)

primitive type배열은 Dual Pivot Quick Sort를 하고 nlogn을 기대할 수 있지만, 최악의 경우 n^2있고, primitive type은 comparator를 지정할 수 없다.

객체, 제너릭 타입들은 comparator를 지정하거나, null인 경우

Merge sort 또는 TimSort를 이용한다. 이는 최악의 경우에도 nlogn을 기대할 수 있다.

해쉬맵을 활용

public static String solution(String[] participant, String[] completion) {
	String answer = "";
    
	HashMap<String, Integer> prtcpt_map = new HashMap<>();
	for(String name : participant) {
		prtcpt_map.put(name, prtcpt_map.getOrDefault(name, 0)+1);
		// getOrDefault() : 값이 없으면 0으로 초기화하고 있으면 해당 값을 가져온다
	}
	
	for(String name: completion) {
		prtcpt_map.put(name,  prtcpt_map.get(name)-1);
	}
	
	for(String name: prtcpt_map.keySet()) {
		if(prtcpt_map.get(name) != 0) {
			answer = name;
			break;
		}
	}
	
	return answer;
}

동명이인이 있을 수 있어 참여한 사람의 이름과 명수를 K-V의 형태로 Map에 저장하고,

완주한 사람의 이름이 나올때 마다 명수를 줄여준다. 완주하지 못한 사람은 1명이기 때문에,

keySet을 받아와 key의 value가 0이 아닌 이름을 찾아준다.

위의 코드는 key의 value가 0인지 아닌지만 확인하면 된다. 

HashMap의 시간복잡도

HashMap은 Dictionary와 같은 역할을 하는 자료구조이다. 

중요한 점은 Hash의 성능을 통해 저장된 Key에 해당하는 Value를 O(1)의 시간복잡도로 검색이 가능하다.

HashMap.put(K, V) : O(1)

HashMap.replace(K,V) : 상수기간

자바의 HashMap의 요소에 대한 수정은 생각보다 복잡하다.

replace()와 get()을 통해 접근, 수정해주도록 하자. 말할 필요도 없이 시간복잡도는 상수기간이다.

HashMap.containsKey(K), HAshMap.containsValue(V) : O(1), O(n)

Key와 Value를 포함하고 있는지 확인하는 함수이다.

주로 containsKey()를 통해 Key가 있는지 확인하고 없을시 put()해주는 식으로 사용한다.

HashMap.keySet() : O(1)

Key를 모아놓은 자료구조를 반환하는 메서드이다. keySet()은 Set<K>를 반환한다.

주로 keySet()을 통해 반환된 Set으로 Map의 요소를 순환하고 싶을 때 사용한다.

References

• https://www.acmicpc.net/board/view/29052
• http://kwseo.github.io/2015/09/24/time-complexity-about-collections/
• http://infotechgems.blogspot.com/2011/11/java-collections-performance-time.html
• https://codeday.me/ko/qa/20190728/1160125.html
• https://velog.io/@wan088/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EA%B3%A0%EB%93%9D%EC%A0%90Kit-1-%ED%95%B4%EC%8B%9C

Hash란?

해쉬는 임의의 크기를 가진 데이터를 고정된 데이터의 크기로 변환시키는 것을 말한다. 

이를 이용하면 입력하고자 하는 데이터의 값을 특정한 배열의 위치나 인덱스로 이용해 저장하거나 찾을 수 있다.

해쉬를 이용하면 즉시 저장하거나 찾고자 하는 위치를 참조할 수 있으므로 더욱 빠른 속도로 처리할 수 있다.

1. Direct Addressing Table

Direct Addressing Table은 key-value쌍의 데이터를 배열에 저장할 때, key값을 직접적으로 배열의 인덱스로 사용하는 방법이다.

예를 들어 키 값이 400인 데이터가 있다면, 이는 배열의 인덱스가 400인 위치에 키 값을 저장하고 포인터로 데이터를 연결한다.

똑같은 키 값이 존재하지 않는다고 가정하면

삽입 시에는 각 키마다 자신의 공간이 존재하므로 그 위치에 저장을 하면 되고, 

삭제 시에는 해당 키의 위치에 NULL값을 넣어주면 되고,

탐색 시에는 해당 키의 위치를 찾아가서 참조하면 된다.

찾고자 하는 데이터의 key만 알고 있으면 즉시 위치를 찾는 것이 가능하므로 탐색, 저장, 삭제, 갱신은 모두 선형시간 O(1)로 매우 빠른 속도로 처리가 가능하다.

다만 key값의 최대 크기만큼 배열이 할당되기 때문에, 크기는 매우 큰데 저장하고자 하는 데이터가 적다면 공간을 많이 낭비할 수 있다는 단점이 있다.

2. Hash Table

Hash Table은 key-value쌍의 데이터에서 key값을 테이블에 저장할 때, key값을 함수를 이용해 계산을 수행 한 후, 그 ㅇ결과값을 배열의 인덱스로 사용하여 저장하는 방식이다. key값을 계산하는 함수는 해쉬함수(Hash Function)라고 부르며, 해쉬함수는 입력으로 key를 받아, 0부터 배열의 크기-1 사이의 값을 출력한다. 해쉬에 대한 첫 정의대로 임의의 숫자를 배열의 크기만큼으로 변환 시킨것이다. 이 경우 k값이 h(k)로 해쉬되었다고 하며, h(k)는 k의 해쉬값이라고 한다.

Hash Table은 Direct Addressing Table에 비해 공간 낭비가 매우 적은데, 이는 테이블의 크기가 key값에 좌우되는 것이 아니고, h(k)만큼의 공간에 저장되기 때문이다.

2.1 충돌(Collusion)

Hash Table은 충돌이 일어날 수 있다는 큰 문제점이 있다.

충돌이란 서로 다른 key값이 동일한 h(k)값을 가져 동일한 slot에 저장되는 경우를 말한다.

예를 들어, h(k1)=h(k2) 인 경우를 들 수 있다. Direct Addressing Table에서는 이를 방지하기 위해 모든 key값이 다르다고 전제하지만, 해쉬 테이블에서는 key값이 달라도 해쉬의 결과가 같을 수 있기 때문에 이를 방지하기 위한 방법이 필요하다. 하지만 해쉬 함수를 짜더라도 충돌을 '완전히' 방지한다는 것을 보장하기 힘드므로, 충돌을 방지하기 위한 방법으로 충돌을 어느정도 허용하되 이를 최소화 하는 방법을 사용하기도 한다.

2.1.1 Chaining 방법 - 충돌을 허용하되 최소화 하는 방법

충돌을 허용하지만 이를 최소화하기 위한 방법중 하나는 chaining 방식이다. 

chaining이란 데이터들을 포인터를 이용해 체인 형태로 엮어 나가는 것을 말한다.

Hash Table에서 동일한 해쉬값이 출력되 충돌이 일어나면, 그 위치에 있던 데이터에 key값을 포인터 뒤이어 연결한다.

따라서 최초로 h(k)위치에 저장된 데이터를 시작으로 그 이후의 h(k)값이 출력되면 연결 리스트의 형태를 취한다.

그렇기 때문에 최초의 위치를 탐색하는 해쉬 과정을 제외하고, 모든 탐색, 삽입, 삭제 과정은 연결리스트와 유사한 방식으로 진행한다.

chaining방법에서의 수행시간은 삽입 시에는 해쉬값을 이용해 slot에 저장하면 되므로 상수시간에 일어나고,

삭제는 연결리스트의 삭제와 동일하게 상수시간에 일어나고,

탐색은 연결리스트를 따라가기 때문에 리스트의 길이 만큼 발생하지만, 최악의 경우, 즉 모든 데이터의 해쉬값이 일치하여 한 인덱스에 저장됐을 경우엔 연결리스트의 탐색 시간과 동일한 선형시간을 가지게 된다.

2.1.2 적재율

최악의 경우는 극단적인 예로, 평균적인 경우엔 O(a+1)의 시간이 걸린다. a는 적재율을 뜻하며 적재율이란 현재 저장된 key 값 갯수 (K)를 전체 테이블의 갯수(N)로 나눈 값(K/N)이다. 즉 현재 저장된 데이터가 많으면 많아질수록 충돌 확률이 높아져 연결 리스트 탐색 확률도 증가하며, 적을수록 리스트 탐색 확률이 적어진다는 것이다.

2.1.3 Simple uniform hash

충돌을 최소화 하는 방법 중에 충돌이 적은 좋은 해쉬 함수를 만드는 방법도 있다.

좋은 해쉬 함수의 조건은 Simple uniform hash 함수를 만드는 것으로, 이 조건은 다음과 같다.

1. 계산된 해쉬 값의 범위는 0부터 배열의 크기-1 사이이며, '동일환 확률'로 골고루 나타나야 한다.
2. 각각의 해쉬값들은 서로 연관성을 가지지 않고 독립적으로 생성되야 한다.

첫번 째 조건을 충족하면 충돌이 일어날 확률이 적어질 것이며,

두번 째 조건은 해쉬값들이 서로 연관이 있을 경우 해쉬값이 등장하는 패턴이나 순서가 존재할 수 있고, 이는 반복적인 충돌을 일으킬 확률이 있기 때문이다.

2.1.4 division method

해쉬 함수는 정말 다양하지만 대표적인 해쉬 함수로는 division method가 있는데, modular 연산 방법을 이용하는 방법이다. 특정 key를 어떤 수로 나눈 나머지를 해쉬값으로 사용한다. 

예를 들어 m=100 이면 k mod m 은 0부터 99까지의 범위를 가진다. 이 범위의 m은 해쉬 테이블의 성능을 크게 좌우하는데, m의 크기는 보통 키의 수의 3배가 적당하다고 한다. (적재율이 30%쯤까지 충돌이 거의 일어나지 않는다고 한다.)

그리고 m으로 2^p 값을 사용하는 것엔 큰 주의를 요한다. m이 2^3이면, 2진수로 000010000이고, 4번째이하의 숫자만 해쉬 값에 영향을 끼치기 때문이다.

예를 들어 k1과 k2가 각각 10110100, 10120100이면 둘다 같은 해쉬값을 출력한다. 이를 방지하기 위해서 보통 2^p에 근접한 소수를 선택한다고 한다.

즉 가장 최적의 m의 크기는 키의 갯수의 3배이며 2의 지수승에 근접한 소수이다.

3. Open Addressing

Open Addressing은 key값을 테이블에 저장하는 Direct Addressing Table과는 다르게, 모든 데이터(key+데이터)를 테이블에 저장하는 방법이다.

장점으로는 데이터를 직접 모두 읽어오기 때문에 포인터를 쓸 일이 없어 포인터를 사용함으로서 발생 할 수 있는 오버헤드를 방지할 수 있다는 점이다.

포인터가 필요 없어 구현이 훨씬 용이해졌으며, 포인터 접근에 필요한 시간이 없기 때문에 큰 성능 향상이 있다.

3.1 Liner probing

포인터를 사용하지 않기 때문에, 앞서 설명한 Chaining방법은 사용할 수 없다. 따라서 다른 방법으로 충돌시에 대처해야 하는데 그 중 하나가 Liner probing이다. 

Liner probing은 충돌이 발생하면 바로 다음 인덱스에 데이터를 저장하는 방식이다. 다음으로 이동한 이후에도 충돌이 발생했다면 다시 다음으로 이동하여 저장한다.

즉 충돌이 일어나지 않을 때 까지 다음으로 이동하며 빈 공간을 찾으면 그 위치에 저장한다.

매 충돌시마다 한칸씩 이동하므로 해쉬함수는 다음의 형태를 취하게 된다.

h(k,i) = (k+i) mod m

Liner probing은 정말 구현이 용이하지만, primary clustering이라는 문제점을 가지고 있다.

primary clustering은 충돌이 나면, 뒤 슬롯에 데이터를 넣어 하나의 데이터 덩어리를 이루기 때문에, 데이터들이 특정 위치에만 밀집하는 현상을 말한다. 이 현상으로 slot이 많아지면 많아질수록 탐색 시간이 엄청 늘어나게 된다.

3.2  Quadratic probing

primary clustering을 방지하기 위해 hash함수를 다음과 같이 2차식의 형태로 만드는 것이다.

h(k,i) = (h'(k)+c1*i+c2*i^2) mod m

Liner probing과는 달리 i가 2차식의 형태를 취해, 한칸씩 이동하는 것이 아닌 c1*i+c2*i^2만큼 이동한다.

간단한 예로 해쉬 함수는 h(k,i)=(k+i^2) mod m의 형태일 때를 살펴보자.

m은 7이며, insert값이 76, 40, 48일때 76%7=6, 40%7=5, 48%7=6이 된다. 

3번째 insert값인 48은 충돌이 일어난다. 그래서 i를 하나 증가시켜 h(48,1) = (48+1^2) mod 7 = 0의 위치에 저장하였다. 여기선 충돌이 한번 일어난 경우지만, 만약 0에서도 충돌이 일어났다면 h(48,2) = h(48+2^2) mod 7 = 3의 위치에 저장되었을 것이다. 

하지만 Quadratic probing에도 secondary clustering이라는 단점이 있다. 이는 처음 시작 해쉬값이 같을 경우, 그 이후의 해쉬값들도 모두 동일한 값으로 계산되어 충돌이 반복적으로 일어나는 것을 말한다.

3.1.3 Double hashing

Quadratic probing의 secondary clustering을 해결하기 위해서 사용하는 방법이다.

원리는 간단한데 해쉬 함수를 2개로 구성하는 것이다. 해쉬 함수는 다음과 같은 형태를 가진다.

h1(k) = k mod m

h2(k) = k mod m2

h(k,i) = (h1(k) + i*h2(k)) mod m

시간복잡도란 무엇일까요?

점근적 실행시간, 또는 big-O 시간에 대한 개념 이라고 말을 합니다. 예를 들어 데이터 전송 '알고리즘'의 실행시간을 예를 들어 보겠습니다.

온라인 전송 : O(s). 여기서 s는 파일의 크기가 된다. 즉, 파일의 크기가 증대함에 따라 전송 시간 또한 선형적으로 증가합니다.

비행기를 통한 전송 : O(1). 파일 크기에 관계없이 파일을 전송하는데 걸리는 시간이 늘어나지 않는다. 즉, 상수 시간만큼 소요된다.

간단하게 그래프로 그려 보겠습니다.

시간복잡도를 구할 때 기억할 것

• 상수항은 무시하라
• 지배적이지 않은 항은 무시하라

상수항은 무시하라

만든 알고리즘의 시간 복잡도가 4N+100000라는 시간이 걸린다고 생각해보자. N값의 따라 걸리는 시간이 달라진다. N의 값이 점점 커지고 여러분이 상상하는 가장 큰 숫자가 된다고 생각해보자. 뒤에 상수항은 그 숫자에 얼마나 큰 영향을 주게 되나요?

지배적이지 않은 항은 무시하라

이번에 만든 알고리즘의 시간복잡도는 N² + N + 1000000 의 시간이 걸린다고 생각해보자. 이번에도 N의 값을 계속해서 키워나갈 때, N²의 값, N의 값, 1000000 들의 변화를 살펴보자. N²값에 비하면 N은 상수항과 비슷한 느낌을 받는다. 즉, N²값에 따라 이 알고리즘이 걸리는 시간이 결정된다. 그러므로 이 알고리즘을 big-O표기법을 사용해 표현하면 O(n²)의 시간복잡도를 가진다고 말할 수 있다.

덧셈 vs 곱셈

덧셈 수행시간 : O(A + B)

곰셈 수행시간 (A * B)

알고리즘이 두 단계로 이루어져 있다고 가정하자. 어떤 경우에 수행 시간을 곱하고 어떤 경우에 더해야 할까?

• 만약 알고리즘이 "A 일을 모두 끝마친 후에 B일을 수행"하는 형태라면 A와 B의 수행시간을 더해야한다.
• 만약 알고리즘이 "A 일을 할 때마다 B일을 수행"하는 형태라면 A와 B의 수행시간을 곱해야 한다.

log N 수행시간

O(logN) 수행 시간을 자주 접할텐데 이 수행 시간은 어떻게 구해진걸까?

binary search(이진 탐색)을 생각해보자. 이진 탐색은 N개의 정렬된 원소가 들어있는 배열에서 원소 x를 찾을 때 사용된다. 먼저 원소 x와 배열의 중간값을 비교한다. 'x==중간값'을 만족하면 반환한다. 'x < 중간값'일 때는 배열의 왼쪽 부분을 재탐색하고 'x > 중간값'일 경우에는 배열의 오른쪽 부분을 재탐색한다.

처음에는 N개가 들어있는 배열에서 시작한다. 한 단계가 지나면 탐색해야할 원소의 개수가 N/2로 줄어들고, 다음 단계에서는 N/4로 줄어든다. 그러다 원소를 찾거나 탐색할 원소 1개가 남으면 탐색을 중지한다.

시작 N이 16이라고 가정하고 정리하면,

N = 16

N = 8

N = 4

N = 2

N = 1 의 결과로 원하는 x를 찾을 수 있다.

반대로 16에서 1로 증가하는 순서로 생각해보면 1에 2를 몇번이나 곱해야 할까?

N = 1

N = 2

N = 4

N = 8

N = 16 약, 4번 2를 곱하고 결과 값을 얻을 수 있다.

즉 2^k = N을 만족하는 k는 무엇인가? 이때 사용되는 것이 바로 로그(log)이다.

2^k = N  ▶  log₂16 = 4  ▶  4

log₂N = k  ▶ 2^k = N

어떤 문제에서 원소의 개수가 절반씩 줄어든다면 그 문제의 수행 시간은 O(logN)이 될 가능성이 크다. 로그의 밑은 고려하지 않아도 된다. 밑이 다른 로그는 오직 상수항만큼만 차이가 나는데 위에서 언급했듯이 상수항은 영향이 크지 않다. 표현할 때도 logN으로 표현되며, 로그의 밑은 무시해도 된다.

재귀적으로 수행시간 구하기

오메가 : 최선의 시간을 고려
세타 : 평균의 시간을 고려
오 : 최악의 시간을 고려 (세타를 O(오)로 통합해 표현하기도 합니다)