Octoping의 블로그
비트마스킹
개발 일반/알고리즘 2022. 6. 18. 15:51

비트마스킹은 이진법을 이용하여 적은 메모리로 데이터를 저장하는 기법이다 ​ int arr[20]에 0 또는 1의 데이터를 저장하느니, 20자리의 이진수 숫자 하나에 비트 하나당 0, 1의 값으로 데이터를 저장하는 것이 훨씬 이득일 것이다. int bitmask = 0; // 초기화 // [ n번째 값 1로 만들기 ] bitmask |= (1

숫자 배열에서 두 번째로 큰 값 찾기
개발 일반/알고리즘 2022. 6. 18. 15:37

숫자배열에서 두 번째로 큰 값을 찾는 몇 가지 방법을 소개한다. 방법 1 배열을 내림차순으로 정렬한 후, 두 번째의 값을 반환한다. 이 방법은 무척 코드로 쓰기 간단하지만, O(nlogn) 정도의 시간복잡도가 소모된다는 단점이 있다. Arrays.sort(arr); int second = arr[1]; 방법 2 for문을 사용하여 순회하며 두 번째로 큰 값을 찾는 방법도 있다. int max = -Integer.MAX_VALUE; int second = -Integer.MAX_VALUE; for(int i : arr) { if(i > max) { second = max; max = i; } else if(i > second) { second = i; } } 응용으로 세 번째로 큰 값도 쉽게 구할 수 있다..