전체 233
중복된 원소 값이 있는 경우의 이진 탐색 (Binary Search)

#1 알고리즘#1-1 이진 탐색 (Binary search)#1 알고리즘 이렇게 해서 x의 인덱스 i를 찾으면 좋겠지만, 이 x가 배열 values 어디에도 존재하지 않는 경우도 있을 것이다. 이 경우엔 어떻게 처리해야 할까? 업 앤 다운 게임은 우리나라에선 소주kenel.tistory.com해당 글에서 이어진다. #1-2 #1-3중복된 값이 없는 경우의 이진 탐색에선 min 있는 경우의 이진 탐색에선 min = max가 되는 시점이 while의 탈출 시점이다. min = max는 검색 범위가 i에 최대로 접근 즉, 아예 같은 값이 되었다는 의미다. #1-4binarySearch() 대비 binarySearchFirstIndex() 또는 binarySearchLastIndex()에서 다른 부분을 빨갛게 ..
깨알 개념/알고리즘 2023.11.07

이진 탐색 (Binary search)

#1 알고리즘 #1-1 #1-2 이렇게 해서 x의 인덱스 i를 찾으면 좋겠지만, 이 x가 배열 values 어디에도 존재하지 않는 경우도 있을 것이다. 이 경우엔 어떻게 처리해야 할까? #1-3 업 앤 다운 게임은 우리나라에선 소주병 뚜껑에 적혀 있는 0 ~ 50 사이의 정수를 가지고 맞추는 술 게임의 이미지가 강하다. 어떤 상황을 가정해보겠다. 어느 병뚜껑엔 알 수 없는 이유로 34.5라는 정수가 아닌 수가 적혀 있었다. 사회자는 병뚜껑에 쓰인 숫자를 보고 당황했지만, 장난기가 발동해 그냥 게임을 진행해 보기로 했다. 참여자들은 병뚜껑에 쓰인 숫자가 정수가 아닐 거라고는 생각지 못하고 업 앤 다운 게임에 임할 것이다. 이 업 앤 다운 게임은 실패할 운명이다. 하지만, 이 사례를 상상해 보면서 이진 탐색..
깨알 개념/알고리즘 2023.11.06

[백준] 1654 (랜선 자르기)

#1 알고리즘#1-1 #1-2 중복된 원소 값이 있는 경우의 이진 탐색 (Binary Search)#1 알고리즘 이진 탐색 (Binary search) #1 알고리즘 이렇게 해서 x의 인덱스 i를 찾으면 좋겠지만, 이 x가 배열 values 어디에도 존재하지 않는 경우도 있을 것이다. 이 경우엔 어떻게 처리해야 할까? 업kenel.tistory.com해당 글을 읽어야 이 다음 부분을 이해할 수 있다 #1-3 #1-4여기에서 정리했던 binarySearchLastIndex()와 다른 부분을 강조 표시했다.
min과 max을 각각 2로 나눈 뒤 더하는 이유는 int형의 오버플로우 방지를 위해서다. 또, values는 내림차순이기 때문에, Up 및 Down을 판단하는 코드에서의 부등호를 반대 방향으로 돌렸다...
문제 풀이/탐색ㆍ그래프 2023.11.04

[백준] 1436 (영화감독 숌)

#1 알고리즘1번 if문과 2번 if문을 병렬로 두는 코드보다, 2번 if문을 1번 if문 안에 넣는 코드가 더 빠르다. 왜냐하면, contains666Count가 갱신되지 않았다면, targetCount와 비교한 결과 또한 갱신되지 않을 것이기 때문이다. contains666Count가 변해야, 2번 if문에 의미가 생긴다. #2 코드#2-1 자바import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int targetCount = sc.nextInt(); sc.close(); ..
문제 풀이/기타 2023.11.03

정렬 - 선택 정렬 (Selection Sort)

#1 알고리즘#1-1 #1-2 #2 코드#2-1 자바public static void selectionSort(int[] array, int startIndex, int endIndex) { for(int maxIndex = endIndex; startIndex  #2-2 코틀린fun selectionSort(array: Array, startIndex : Int, endIndex : Int) { for(maxIndex : Int in endIndex downTo (startIndex + 1)) { // 배열을 순회하며 가장 값이 큰 원소의 index를 구한다 var indexOfLargest = startIndex; for(i : Int in (s..
깨알 개념/알고리즘 2023.11.02

배열의 길이(length)와 원소의 순번(index)

#1 알고리즘 #1-1 #1-2 자바에서, 배열을 선언할 때는 '갯수'를 이용한다. 다음 자바 코드를 보자. 자바는 0-based indexing을 사용한다. int[] array = new int[5]; // 5는 0-based index의 최댓값 혹은 1-based index의 최댓값도 아닌 그저 '갯수'다 array[2] = 789; // 2는 '순번'이다. 배열을 선언할 때 [ ] 자리에 들어가는 숫자는 '갯수'를 의미한다. 배열에 접근할 때 쓰는 [ ] 속에 들어가는 숫자가 '순번'인 것과 달리 말이다. 이를 구분하지 못하면, "0-based indexing을 쓰는 언어일지라도 선언할 때만큼은 1-based indexing을 쓰나?" 와 같은 오해가 생긴다. #1-3 '순번' 과 '갯수'는 서로..
깨알 개념/알고리즘 2023.11.01

[Java] Map<Key, Value>의 Key 자리에 원시 타입(Primitive types) 데이터 형식이 올 수 없는 이유

#1 알고리즘 #1-1 자바의 Map 인터페이스에서, Map의 Key는 제네릭으로 작성되어 있다. 따라서, "제네릭(Generic) 자리에 원시 타입(Primitive types) 데이터 형식이 올 수 없는 이유"를 생각해야 한다. #1-2 먼저, 제네릭 탄생의 배경을 알아야 한다. 제네릭은, 자바에서 제네릭 도입 이전에 발생한 여러가지 문제(타입 안전성이 없고, 프로그래머가 일일이 명시적으로 형변환을 해야 하며, 코드 재사용성이 낮음)를 해결하기 위해 도입되었다. 제네릭은 많은 종류의 객체들을 다뤄야 하는 프로그래머가 객체를 더 쉽고 직관적으로 다룰 수 있도록 도와준다. #1-3 제네릭을 한 마디로 표현하면 객체 구별의 직관화이다. 따라서, 객체와 연관이 없는, 독립적인 개념인 원시 타입 변수의 데이터..
깨알 개념/기타 2023.10.30

[백준] 1181 (단어 정렬)

#1 알고리즘#1-1 선택 정렬 (Selection Sort)#1 알고리즘 #2 요약 선택 정렬은 가장 큰 원소 하나를 '선택'해서, 뒤쪽에 차곡차곡 쌓는 정렬이다. #3 이 개념이 사용된 글 https://kenel.tistory.com/7 1181 #1 알고리즘 정렬 알고리즘은 여러 가지가 있kenel.tistory.com정렬 알고리즘은 여러 가지가 있다. 상황에 맞추어 가장 적절한 알고리즘을 골라야 하지만, 나는 알고리즘을 공부 중이므로 사용해 보지 않은 정렬 알고리즘 중에 아무거나 골라서 사용한다. 이 문제에 사용할 알고리즘은 선택 정렬(Selection Sort)이다.  #1-2 #2 코드#2-1 자바import java.util.Scanner;public class Main { priva..
문제 풀이/정렬 2023.10.28
1 ··· 20 21 22 23 24
더보기

티스토리툴바