이분 탐색 알고리즘 헷갈리는 내용 정리(while 조건, lo/hi 갱신 처리, 반환 값, lo/hi 범위)

이분 탐색을 이용한 백준 문제들을 풀다가 헷갈리는 부분들이 생겨 그에 관해 정리해본다. 일단 이분 탐색 알고리즘의 대표적인 코드를 한번 보자. int BinarySearch(int lo, int hi, int target) { while(lo + 1 < hi) { int mid = (lo + hi) / 2; if(arr[mid] target) hi = mid; } return lo; } 여기서 헷갈리는 부분들이 4가지가 있었다. while문 안의 조건 다른 사람들의 이분 탐색 코드를 살펴보면, 대표적으로 많이 쓰이는 3가지가 있다. (lo + 1 < hi), (lo < hi), (lo = target 라면, hi = mid로 갱신을 해줘야한다. while문을 탈출하는 lo + 1 == hi의 경우에, h..

→2021.09.16

시간 복잡도 / 공간 복잡도

1. 시간 복잡도, 공간 복잡도란? 좋은 알고리즘이란 무엇일까? 얻고자 하는 결과를 짧은 시간과 적은 메모리 공간을 이용하여 구해내는 알고리즘을 좋은 알고리즘이라 할 수 있다. 이 때 알고리즘 수행에 드는 시간 효율과 공간 효율을 알아내는 방법이 필요한데, 그것이 시간 복잡도와 공간 복잡도이다. 2. 시간 복잡도 알고리즘의 시간 복잡도를 계산할 때는 알고리즘의 연산의 횟수를 계산하여 정한다. 알고리즘은 경우에 따라 연산 횟수가 최선의 경우, 평균적인 경우, 최악의 경우로 달라질 수 있다. 대체로 최악의 경우를 산정하고 시간 복잡도를 파악한다. 그렇다면 이 때 연산이라고 할 수 있는 것에 무엇이 있을지 알아보자. 대입 연산 사칙 연산(덧셈, 뺄셈, 곱셈, 나눗셈) 비교 연산 함수의 호출 public int..

→2021.08.12

위상 정렬(Topological sorting) [Java]

목차 1. 위상정렬이란? 2. 위상정렬의 과정 3. 위상정렬 구현 1. 위상정렬이란? 위상정렬은 사이클이 존재하지 않는 방향 그래프에서 정점들을 정렬하는 알고리즘이다. 대표적인 실생활의 예로 대학교의 선후수 교과과정이 있다. 위와 같은 상황에서 과목을 듣는 순서를 짜는 것이 위상정렬의 한 예이다. 만약 사이클이 있다면 선후 관계가 모호해지기 때문에 사이클은 올 수 없다. 2. 위상정렬의 과정 위 그래프를 한번 위상정렬해보자. 먼저 들어오는 간선이 없는 A가 제일 앞에 올 것이다. A에서 나가는 간선을 보면 B, C, D를 향해 있다. 이것의 의미는 B, C, D를 거치기 전에 반드시 A가 등장해야한다는 의미이다. 지금 상태에서는 A가 제일 앞에 등장했으니 A에서 나가는 간선은 의미가 없다. 그러므로 A와..

→2021.08.07

java.lang 패키지 / 오토 박싱/ 오토 언박싱

java.lang 패키지에 대한 간단한 내용 1. java.lang 패키지는 import 하지 않아도 사용할 수 있다. 2. java.lang 패키지에는 기본형타입을 객체로 변환시킬때 사용하는 Wrapper클래스가 있다. ex)Boolean, Byte, Short, Integer, Long, Float, Double 클래스 3. java.lang 패키지에 속한 클래스 - 모든 클래스의 최상위 클래스인 Object - 문자열과 관련된 String, StringBuffer, StringBuilder - 화면에 값을 출력할때 사용했던 System클래스 - 수학과 관련된 Math클래스 - Thread와 관련된 중요 클래스들 - 외에도 다양한 클래스와 인터페이스가 속해있다. 오토 박싱 / 오토 언박싱 public..

→2021.07.28

Java Object 클래스

Object 클래스는 모든 클래스의 최상위 클래스이다. 아무것도 상속 받지 않으면 자동으로 Object 클래스를 상속 받기 때문에, Object가 갖고 있는 메소드는 모든 클래스에서 이용할 수 있다. Object가 가지고 있는 메소드 중에서 가장 많이 사용되는 메소드는 equals, toString, hashCode가 있으며 이는 반드시 오버라이딩해서 사용해야 한다

→2021.07.27