분류 전체보기
final 키워드 헷갈리는 부분 정리
private final Map store = new HashMap();위와 같은 코드가 있다고 했을 때, store가 가리키는 실제 데이터들이 바뀌면 안된다고 잘못 생각하고 있었다. 원시 타입 변수의 경우 값이 스택에 저장되고, 객체 타입은 주소는 스택에 값은 힙에 저장된다. store가 무엇을 가리키는지 즉, 가리키는 주소가 바뀌면 안된다는 것이지 힙 안의 값이 바뀌는 것은 상관이 없다. 힙 안의 값도 불변이길 원한다면 Collections.unmodifiableMap() 를 이용해보자. final을 값이 변하지 않는다고 이해하지 말고, 한번만 할당할 수 있다고 이해하자.
이분 탐색 알고리즘 헷갈리는 내용 정리(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..
BOJ 11653 소인수분해 [Java]
BOJ 11653 소인수분해 1. 문제 링크 https://www.acmicpc.net/problem/11653 2. 문제 해설 입력 받은 정수를 n, n을 나누는 수를 a라고 하자. a를 최초의 소수인 2로 초기화 한다. 아래의 과정을 n이 1이 될 때까지 반복한다. n이 a로 나눠지면 n을 a로 나누고 이 때의 a값을 담는다. n이 a로 나눠지지않으면 a를 1 늘린다. 3. 코드 보기 import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Buffere..
BOJ 6588 골드바흐의 추측 [Java]
BOJ 6588 골드바흐의 추측 1. 문제 링크 https://www.acmicpc.net/problem/6588 2. 문제 해설 true이면 소수이고, false면 소수가 아닌 isPrime 배열을 만든다. 테스트 케이스의 범위가 6이상 1000000이하이므로 크기는 1000001로 지정해준다. 일단 isPrime 배열의 원소를 전부 true로 초기화해주고, 그 후 에라토스테네스의 체를 이용하여 소수가 아닌 수들은 false로 바꿔준다. 이제 골드바흐의 추측이 가능한지 아닌지를 판단해주는 impossible 함수에 대해 설명해보겠다. impossible 함수는 n을 매개변수로 받고, n 이하의 짝수들을 전부 탐색하면서 두 짝수 소수의 합으로 나타낼 수 있으면 앞 쪽 소수를 반환한다. 두 짝수 소수의 합..
BOJ 1929 소수 구하기 [Java]
BOJ 1929 소수 구하기 1. 문제 링크 https://www.acmicpc.net/problem/1929 2. 문제 해설 주어지는 두 수의 범위가 1부터 1,000,000 사이이다. 1부터 1,000,000까지 모두 나눠보는 방식은 시간 제한에 걸리기도 하고 굉장히 비효율적이다. 주어진 범위 내에서 소수 판별을 하는 가장 좋은 방법으로 '에라토스테네스의 체' 라는 방식이 있다. 예를 들어 1부터 100까지의 수 중에서 소수를 판별한다고 할 때, 에라토스테네스의 체가 어떻게 동작하는지 살펴보자. 일단 소수도 합성수도 아닌 1을 제외한다. 2를 제외한 범위 내의 2의 배수를 전부 제외한다. 3을 제외한 범위 내의 3의 배수를 전부 제외한다. 4의 배수는 이미 2의 배수를 제외하는 과정에서..