보통 원하는 원소를 찾고자 할 때 처음부터 끝까지 탐색하는 선형 탐색을 주로 사용한다.

선형 탐색은 데이터의 크기가 너무 크지 않다면 딱히 고려할 조건이 없기 때문에 구현이 쉽기 때문이다.

하지만 데이터의 크기가 너무 커진다면 얘기가 달라진다.

그래서 나온 탐색 방법이 이진 탐색이다.(이분 탐색도 같은 말)

먼저 기본적인 개념은 순차적으로 정렬이 된 상태에서 특정 원소를 찾을 때까지 범위를 절반씩 줄이고 더 이상 찾을 범위가 없으면 해당 원소는 없다고 판단하는 알고리즘이다.

N개의 Data가 있을 때 범위를 절반씩 줄여나가므로 O(logn)의 아주 효율적인 시간 복잡도를 가지는데 여기서 중요한 점은 정렬된 상태여야 한다는 것이다.

왜냐하면 범위를 줄여나갈 때 찾고자 하는 원소와 현재 범위의 중간값을 비교해서 일치하면 중단, 일치하지 않으면 절반에 해당하는 범위엔 찾고자 하는 원소가 없다는 전제하에 범위를 줄여나가는 방식인데 정렬된 상태가 아니라면 이처럼 범위를 줄여나갈 수가 없다.

따라서 정렬된 Data를 탐색하거나 정렬하여 탐색할 수 있는 범위가 주어진다.

참고로 Python의 sort함수를 쓰면 O(nlogn)의 시간 복잡도를 가지므로 100만의 Input정도는 충분히 정렬 후 탐색할 수 있다.

그림의 예시를 따라가다 보면 쉽게 이해할 수 있을 것이다. (예시는 오름차순 리스트를 하며 내림차순은 반대로 하면 된다)

먼저 리스트의 전체 범위에서 시작해야 하므로 Left와 Right 두 개의 변수가 필요하다.

Left는 시작을 뜻하는 0(0번째 인덱스), Right는 끝을 뜻하는 len(data)-1로 선언하면 된다.

이제 아주 간단한 사전 준비는 끝났다.

Left와 Right의 위치가 역전된다면 더 이상 탐색할 범위가 없다는 뜻이므로 Left <= Right인 동안 반복을 계속 돌려주면 된다.

예시로 2와 7을 찾도록 해보겠다.

빨간색 화살표는 중앙값(변수명은 mid)을 뜻하고 찾고자 하는 원소가 mid에 있는 원소보다 작으므로 왼쪽 범위를 찾아야 한다는 뜻이 된다.

이때 이미 mid에 위치한 원소는 탐색했으므로 Right는 mid-1로 변경해서 조금이라도 탐색 횟수를 줄여준다.

Right=mid-1로 범위를 바꾼 뒤 다시 중앙값(mid)을 비교해보면 2를 찾을 수 있다.

해당 위치의 인덱스를 저장한 뒤 반복문을 빠져나오면 된다.

다음은 리스트에 없는 7을 찾아보겠다.

찾고자 하는 원소가 중앙값보다 크므로 오른쪽 범위에 있단 의미고 마찬가지로 중앙값은 탐색했으므로 탐색 횟수를 줄이기 위해 Left는 mid+1로 변경한다.

오른쪽 범위로 이동해서 다시 중앙값을 비교해보니 찾고자 하는 원소보다 중앙값이 더 크다.

이 말은 왼쪽 범위에 있단 뜻이므로 Right를 mid-1로 변경한다.

다시 왼쪽 범위로 이동해서 중앙값을 비교해보니 찾고자 하는 원소가 중앙값보다 더 크다.

이 말은 중앙값보다 오른쪽 범위에 있단 뜻이므로 Left는 mid+1로 변경한다.

이때 Left는 Right보다 커져서 역전되므로 결국 원소를 찾지 못한 채 반복문을 빠져나오게 된다.

이 알고리즘이 이진 탐색이며 7개의 Data에서 2를 찾는데 2번 연산, 7이 있는지 확인하는데 3번 연산밖에 하지 않았다.

만약 선형 탐색이었다면 최악의 경우 7번(Data의 크기만큼)의 연산을 할 것이고 확실히 이진 탐색을 통해 연산 횟수가 줄어든 것을 알 수 있다.

지금은 Data의 크기가 작기 때문에 몇 번 차이가 없지만 Data의 크기가 막대하게 커지면 상당히 효율적인 알고리즘이란 사실을 체감할 수 있을 것이다.

다음은 위의 설명대로 구현한 전체 코드이다.

data=[1,2,4,5,6,8,9]

def binary(n):
    index=-1
    left=0
    right=len(data)-1
    
    print("이진 탐색 과정 :",end=" ")

    while left<=right:
        mid=(left+right)//2
        print(data[mid],end=" ")
        if data[mid]==n:
            index=mid
            break
        elif n<data[mid]:
            right=mid-1
        else:
            left=mid+1
    print()
    return index

first=binary(2)

if first==-1:
    print("없는 원소입니다.")
else:
    print(first,"번째 인덱스에 있습니다.")

second=binary(7)

if second==-1:
    print("없는 원소입니다.")
else:
    print(second,"번째 인덱스에 있습니다.")

초기 Index는 -1로 지정하고 찾는 원소가 있다면 해당 원소의 인덱스로 갱신한다.

즉 여전히 Index가 -1이라면 찾는 원소가 없단 뜻이다.

그림을 참고하여 코드를 한 줄씩 따라가다 보면 쉽게 이해할 수 있을 것이다.

혹시나 해서 알고리즘 구현 자체를 접한 지 얼마 안 된 사람들께 덧붙이자면 이번 코드에서는 예시를 위해 인덱스를 반환하도록 구현했지만 당연하게도 각자 접하는 문제에 맞게끔 변형하여 구현해야 된다.

끝으로 이진탐색을 연습할 수 있는 문제를 몇가지 추천한다.

https://www.acmicpc.net/problem/1920

https://www.acmicpc.net/problem/1654

https://www.acmicpc.net/problem/23740

문제 풀이

눈여겨봐야 할 점은 3가지다.

1. 버스 노선의 개수인 N은 20만 이하이다.
2. 한 점 이상에서 겹쳐지면 연장 가능한 노선이다.
3. 개편된 노선의 요금은 개편할 때 사용된 노선의 최소 요금을 적용한다.

문제와 그림을 보고 바로 떠오른 생각은 노선의 정보를 오름차순으로 정렬한 뒤 개편된 노선과 겹친다면 포함하는 노선, 겹치는 부분이 없다면 새로운 개편된 노선으로 판단하는 방식이다.

이 방식대로 연산하면 Sort를 이용하여 정렬할 때 O(nlogn), 오름차순 된 노선 정보를 처음부터 훑을 때 O(n)으로 총 O(nlogn)의 시간 복잡도가 걸린다고 생각했다.

따라서 소스 코드는 다음과 같다.

n=int(input())
bus=[]
res=[]
for i in range(n):
    bus.append(list(map(int,input().split())))
bus.sort(key=lambda x:(x[0],x[1]))
check=True
for i in bus:
    if check:
        res.append(i)
        check=False
    else:
        if i[0]<=res[len(res)-1][1]:
            if i[1]>res[len(res)-1][1]:
                res[len(res)-1][1]=i[1]
            if res[len(res)-1][2]>i[2]:
                res[len(res)-1][2]=i[2]
        else:
            res.append(i)
print(len(res))
for i in res:
    print(i[0],i[1],i[2])

bus는 기존 노선 정보를 저장하고 res는 개편된 노선 정보를 저장할 리스트이다.

6번째 줄에서 lambda를 키로 이용하여 0번째 원소, 1번째 원소를 기준으로 오름차순 정렬한다는 뜻이다.

check 변수를 통해 첫 노선을 개편된 노선으로 잡았고 겹치는 부분이 있을 경우로 나눠 14번째 if문은 현재 노선 정보가 개편된 노선보다 길어서 연장해야 될 때, 16번째 if문은 최소 요금으로 갱신하는 문장이다.

또한 겹치는 부분이 없으면 기존 노선을 개편된 노선으로 추가한다.

한 줄씩 원리를 따라가 보면 쉽게 이해할 수 있을 것이다.

Python으로 제출하면 시간 초과가 뜨길래 PyPy로 제출했더니 통과했다.

PyPy는 한 줄씩 해석하는 인터프리터 방식인 Python의 느린 동작에서 컴파일 방식을 개선하여 나온 언어로 상당히 빠른 수행 속도가 특징이다.

따라서 동일한 문법이기에 애초에 시간 복잡도를 비효율적으로 작성한 경우가 아니라면 Python으론 시간 초과 뜨는 코드가 PyPy로 통과하는 경우가 많다.

즉 올바르게 작성한 것 같은데 시간 초과가 뜬다면 PyPy로 제출하길 추천한다.

https://www.acmicpc.net/contest/problem/725/1

문제 풀이

눈여겨봐야 할 조건은 3가지다.

1. 보이는 대로 읽어야 할 알파벳과 다르게 읽어야 할 알파벳이 구분되어있다.
2. 최대 100글자의 단어가 주어진다.
3. 영어 소문자로 나타내 출력해야 한다.

다르게 읽어야 할 알파벳은 다음과 같다.

B->v, E->ye, H->n, P->r, C->s, Y->u, X->h

해당 부분은 파이썬의 딕셔너리(Dictionary)를 사용하면 쉽게 치환 가능하다.

최대 100글자이므로 시간 복잡도는 고려할 필요가 없을 정도로 Input Size가 작다.

입력이 대문자로 들어오고 출력은 소문자로 해야 하므로 보이는 대로 읽어야 할 알파벳은 소문자로 치환시켜야 된다.

다음은 전체 코드이다.

word=input()
russ={"B":"v","E":"ye","H":"n","P":"r","C":"s","Y":"u","X":"h"}
res=""
for i in word:
    if i in russ:
        res+=russ[i]
    else:
        res+=i.lower()
print(res)

먼저 russ란 딕셔너리에 치환해야 될 알파벳들을 넣어 놓고 Input 문자열을 하나씩 반복한다.

만약 딕셔너리에 있는 문자라면 해당 값을 res에 이어 붙이고 없는 문자라면 lower() 함수를 이용하여 대문자를 소문자로 치환한 다음 이어 붙인다.

완성된 문자열을 출력하면 정답이다.

파이썬의 딕셔너리를 사용해야겠다는 생각만 떠올리면 복잡한 인덱싱 과정도 필요 없기에 쉽게 풀 수 있는 문제였다.

개발자로 취업하기 위해선 중요한 요소들이 몇 가지 있습니다.

보통 IT 직무의 채용 절차는 다음과 같습니다.

코딩 테스트 -> 필기 테스트 -> 역량 면접 -> 인성 면접 -> 건강검진 -> 입사

각각

1. 알고리즘 구현 능력
2. CS(Computer Science) 지식 (전공 이론 지식)
3. 실무 적응 가능성
4. 회사 및 직무 적합도
5. 건강 이상

위의 요소가 중요합니다.

이 중 가장 처음으로 접하는 테스트인 알고리즘 구현 능력은 주어진 문제를 해결하는 과정을 평가하므로 적절한 상황에 적합한 알고리즘을 적용하기 위해 자료구조와 알고리즘 학습이 필수입니다.

따라서 이 책은 취업 준비를 위해 자료구조와 알고리즘을 복습, 독학하는 과정에서 프로그래밍 언어에 대한 자료는 많이 있지만 자료구조와 알고리즘을 같이 묶은 집약된 자료를 찾기 어려웠고 국비지원 강의를 들을 때 비전공자 분들과 협업한 경험을 통해 프로그래밍 자체에 어려움을 겪는다는 것을 알게 되어 도움이 되고자 작성하게 되었습니다.

이 부분에 착안하여 고등학교 수리 과외 경험을 살려 언어만 알고 있다면 비전공자도 최대한 쉽게 이해할 수 있도록 작성한 PDF 형태의 전자책입니다.

언어는 가장 기본으로 여겨지는 C와 이해가 쉬운 Python을 기반으로 작성하였으며 목차에서 목록을 클릭하면 해당 본문 페이지로, 본문 페이지의 제목을 클릭하면 다시 목차로 넘어올 수 있도록 만들었기에 전자책의 편의성을 극대화하였습니다.

공부가 주목적이라 마케팅이 전혀 없었기에 몇 권 팔리진 않았지만 지인을 포함한 구매하신 분들 전부 좋은 자료라는 호평이 이어졌습니다.

관심 있으신 분들은 한 번 구경하셔도 좋을 것 같습니다!!

https://kmong.com/gig/290286