[TIL-11 / 230629] 이분 탐색 알고리즘, 깃허브

1. 오늘의 고민

오늘은 알고리즘 공부 방향에 대한 생각에 많은 시간을 투자하였다. 인터넷을 찾다가 본 누군가의 말로 알고리즘을 파이썬으로 시작하였고, 공부는 성향상 백엔드가 적성에 맞아 자바, 스프링을 배워 백엔드 개발자가 되고자 한다.

 

그래서 최근에는 알고리즘 공부를 파이썬과 자바 두가지 언어로 모두 시행하고 있었는데, 시간적 여유가 없는 현 상황에 선택을 해야한다는 판단을 내렸다. 그래서 여러번 서칭하고 고민하다가, 당장 파이썬으로 풀 때보다 번거롭고 힘들더라도 내가 주력언어로 삼고 싶고 공부하고 있는 자바로 해야겠다는 결론을 내릴 수 있었다.

 

많은 사람들이 말하길, 언어는 수단이라고 한다. 한가지 언어를 깊게 공부하고 습득하면 다른 언어는 배우기가 쉬운 구조라고 한다. 나는 아직 자바, 파이썬 무엇도 제대로 다루지 못한다. 그렇기에, 파이썬으로 알고리즘을 이제까지 많이 풀었지만, 지금부터라도 자바에 집중하려 한다.

 

현 시점에서 나의 목표는 올해 말에 오픈될 우아한 테크코스에 백엔드 분야로 지원하는 것이다. 그에 필요한 조건들을 찾아봤는데 우선 기본적인 코딩 능력 및 CS 지식, 그리고 코딩테스트를 통과할 수 있는 알고리즘 실력이 필요하다. 우테코 백엔드 파트는 2차 코딩 테스트 언어를 자바로 제한하기에, 지금부터 쭉 공부하여 도전해볼 계획이다.

---

2. 이분 탐색 알고리즘

설명

정의

• 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법.

조건

• 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있다.

방법

• 변수 3개(start, end, mid)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색의 과정이다.

정렬 등과 함께 가장 기초인 알고리즘. 검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘.

오름차순으로 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘. 리스트의 중간 부분에 찾는 원소가 있는지 확인하고, 없으면 위쪽에 있는지 아래쪽에 있는지 판단하여 맨 앞부터 검색하거나 중간부터 검색한다.

• 예시(그림)

이분 탐색 알고리즘

# 재귀 함수로 구현한 이진 탐색
def binary_search(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2

    # 원하는 값 찾은 경우 인덱스 반환
    if array[mid] == target:
        return mid
    # 원하는 값이 중간점의 값보다 작은 경우 왼쪽 부분(절반의 왼쪽 부분) 확인
    elif array[mid] > target:
        return binary_search(array, target, start, mid - 1)
    # 원하는 값이 중간점의 값보다 큰 경우 오른쪽 부분(절반의 오른쪽 부분) 확인
    else:
        return binary_search(array, target, mid + 1, end)

n, target = list(map(int, input().split()))
array = list(map(int, input().split()))

result = binary_search(array, target, 0, n - 1)
if result is None:
    print('원소가 존재하지 않습니다.')
else:
    print(result + 1)

>>> 4

# sample input
# 10 7
# 1 3 5 7 9 11 13 15 17 19

# 반복문으로 구현한 이진 탐색
def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2

        # 원하는 값 찾은 경우 인덱스 반환
        if array[mid] == target:
            return mid
        # 원하는 값이 중간점의 값보다 작은 경우 왼쪽 부분(절반의 왼쪽 부분) 확인
        elif array[mid] > target:
            end = mid - 1
        # 원하는 값이 중간점의 값보다 큰 경우 오른쪽 부분(절반의 오른쪽 부분) 확인
        else:
            start = mid + 1

    return None

n, target = list(map(int, input().split()))
array = list(map(int, input().split()))

result = binary_search(array, target, 0, n - 1)
if result is None:
    print('원소가 존재하지 않습니다.')
else:
    print(result + 1)
    
>>> 4

# sample input
# 10 7
# 1 3 5 7 9 11 13 15 17 19

• 시간 복잡도는 O(logN)이다. (여기서 log는 log₂이다.)예를 들어 처음 데이터의 개수가 32개라면, 이론적으로 1단계를 거치면 약 16개의 데이터가 남고, 2단계에서 약 8개, 3단계에서 약 4개의 데이터만 남게 된다.
• 즉, 이진 탐색(이분 탐색)은 탐색 범위를 절반씩 줄이고, O(logN)의 시간 복잡도를 보장한다.
• 단계마다 탐색 범위를 반으로(÷2) 나누는 것과 동일하므로 위 시간 복잡도를 가지게 된다.

---

3. Git

Git에 대한 공부를 몇 번 했었지만, 실질적인 협업 프로젝트를 하지 않으니 사용하지 않게 되고, 점차 기억 속에서 잊혀져 간다. 그래서 이제 JPA를 배우고 Spring도 공부하면서 협업 프로젝트를 진행하게 될 것을 대비해서 깃을 매일 20~30분이라도 투자하여 공부하고자 한다.

 

기본 명령어

깃(Git) 기본 명령어

Git Commit 컨벤션

1) Commit message 구조

Commit 메세지는 기본적으로 제목 / 본문 / 꼬리말로 나눠지며 각 부분은 빈 줄로 구분한다.

type: subject

body

footer

2) Commit Type

타입은 태그와 제목으로 구성되고, 태그는 영어로 쓰되, 첫 문자는 대문자로 한다.

태그: 제목  <--과 같은 형태

• feat: 새로운 기능 추가
• fix: 버그 수정
• docs: 문서 수정
• style: 코드 포맷팅, 세미콜론 누락, 코드 변경이 없는 경우
• refactor: 코드 리팩토링
• test: 테스트 코드, 리팩토링 테스트 코드 추가
• chore: 빌드 업무 수정, 패키지 매니저 수정

3) Subject

• 제목은 최대 50글자 넘지 않도록 하고, 마침표 및 특수기호는 사용하지 않는다.
• 영문 표기시 동사원형을 가장 앞에 두고 첫 글자는 대문자(과거 시제 X)
• 제목은 개조식 구문(간결 & 요점)

4) Body

• 본문은 한 줄 당 72자 이내
• 본문 내용은 양에 구애받지 않고 최대한 상세히!
• 본문 내용은 (어떻게 변경했는지 보다) 무엇을 변경했는지, 왜 변경했는지 기술

5) Footer

• 꼬리말은 optional이고 이슈 트래커 ID를 작성한다.
• 꼬리말은 "유형: #이슈 번호" 형식으로 사용
• 여러 개의 이슈 번호를 적을 때는 쉼표(,)로 구분
• 이슈 트래커 유형은 다음과 같다.
  • Fixes: 이슈 수정중(아직 해결 x)
  • Resolves: 이슈를 해결했을 때 사용
  • Ref: 참고할 이슈가 있을 때 사용
  • Related to: 해당 커밋에 관련된 이슈번호(아직 해결되지 않은 경우)
• ex) Fixes: #3 Related to: #4, #5

6) Commit 예시

Feat: "로그인 기능 구현"

SMS, 이메일 중복확인 API 개발

Resolves: #1
Ref: #2
Related to: #3, #4

7) Commit Message Emogji

아이콘	코드	설명	원문
🎨	:art:	코드의 구조/형태 개선	Improve structure / format of the code.
⚡️	:zap:	성능 개선	Improve performance.
🔥	:fire:	코드/파일 삭제	Remove code or files.
🐛	:bug:	버그 수정	Fix a bug.
🚑	:ambulance:	긴급 수정	Critical hotfix.
✨	:sparkles:	새 기능	Introduce new features.
📝	:memo:	문서 추가/수정	Add or update documentation.
💄	:lipstick:	UI/스타일 파일 추가/수정	Add or update the UI and style files.
🎉	:tada:	프로젝트 시작	Begin a project.
✅	:white_check_mark:	테스트 추가/수정	Add or update tests.
🔒	:lock:	보안 이슈 수정	Fix security issues.
🔖	:bookmark:	릴리즈/버전 태그	Release / Version tags.
💚	:green_heart:	CI 빌드 수정	Fix CI Build.
📌	:pushpin:	특정 버전 의존성 고정	Pin dependencies to specific versions.
👷	:construction_worker:	CI 빌드 시스템 추가/수정	Add or update CI build system.
📈	:chart_with_upwards_trend:	분석, 추적 코드 추가/수정	Add or update analytics or track code.
♻️	:recycle:	코드 리팩토링	Refactor code.
➕	:heavy_plus_sign:	의존성 추가	Add a dependency.
➖	:heavy_minus_sign:	의존성 제거	Remove a dependency.
🔧	:wrench:	구성 파일 추가/삭제	Add or update configuration files.
🔨	:hammer:	개발 스크립트 추가/수정	Add or update development scripts.
🌐	:globe_with_meridians:	국제화/현지화	Internationalization and localization.
💩	:poop:	똥싼 코드	Write bad code that needs to be improved.
⏪	:rewind:	변경 내용 되돌리기	Revert changes.
🔀	:twisted_rightwards_arrows:	브랜치 합병	Merge branches.
📦	:package:	컴파일된 파일 추가/수정	Add or update compiled files or packages.
👽	:alien:	외부 API 변화로 인한 수정	Update code due to external API changes.
🚚	:truck:	리소스 이동, 이름 변경	Move or rename resources (e.g.: files paths routes).
📄	:page_facing_up:	라이센스 추가/수정	Add or update license.
💡	:bulb:	주석 추가/수정	Add or update comments in source code.
🍻	:beers:	술 취해서 쓴 코드	Write code drunkenly.
🗃	:card_file_box:	데이버베이스 관련 수정	Perform database related changes.
🔊	:loud_sound:	로그 추가/수정	Add or update logs.
🙈	:see_no_evil:	.gitignore 추가/수정	Add or update a .gitignore file.

 

내용 출처

https://velog.io/@shin6403/Git-git-%EC%BB%A4%EB%B0%8B-%EC%BB%A8%EB%B2%A4%EC%85%98-%EC%84%A4%EC%A0%95%ED%95%98%EA%B8%B0

Git | git 커밋 컨벤션 설정하기

https://treasurebear.tistory.com/70