이진 탐색 - 자료구조와 알고리즘 탐색 알고리즘 중 하나인 이진 탐색(Binary Search)이란 '정렬된 배열'에서 '특정 값'을 찾는 알고리즘을 의미한다. 이진 검색은 정렬된 배열에서 검색 간격을 반으로 반복적으로 나누어 사용하는 검색 알고리즘으로 정의된다. 이진 검색의 아이디어는 배열이 정렬된 정보를 사용하여 시간 복잡도를 O(로그 N)으로 줄이는 것이다. 이진 탐색 알고리즘의 예시로 아래의 그림을 참고하자. 정렬된 배열에서 23을 찾는 과정이다. 배열의 중앙 인덱스를 찾는다. M = (0 + 9) / 2 = 4 인덱스 4에 위치한 16과 23을 비교한다. 16 < 23 23이 더 크므로 L(5) ~ H(9) 사이에서 다시 탐색을 실시한다. M = (5 + 9) / 2 = 7 인덱스 7에 위치한 ..

오전에는 운동, 오후에는 집안일과 각종 잡무들을 처리하느라 많은 공부를 하지 못하였다. 백준에서 문제를 풀다가 코드가 너무 복잡해지고, 속도 또한 느리게 나오는 문제를 발견했다. 그래서 어떻게 해야할지를 고민하다가 평소에 많은 배움을 얻고 있는 Stranger-Lab님의 블로그에서 카운팅 정렬을 학습했다. 링크는 페이지 하단 참고자료란에 첨부하겠다. 카운팅 정렬(Counting Sort) 카운팅 정렬 사용 이유 시간복잡도가 O(n)으로서 엄청난 성능. 대표적인 정렬 알고리즘(퀵 정렬, 힙 정렬, 합병 정렬 등)의 평균 시간복잡도는 O(nlogn)이다. 정렬 방법 카운팅 정렬은 데이터의 값이 몇 번 나왔는지를 세는 메커니즘 array 배열 counting 배열 array를 순회하면서 해당 값을 index..

9월 30일은 세미나를 보고 정리한 내용만 올리고 오랜만에 한국으로 돌아온 친구, 타지에서 일하는 친구들이 모두 부산에 모여서 친구들을 만났고, 10월 1일은 부모님과 함께 보냈다. 번아웃으로 조금 힘든 날들을 보내고 있었는데 오랜만에 공부를 잠깐 쉬어가면서 사람들을 만나니 다시 에너지를 얻은 기분이다. 역시 공부와 휴식이 조화를 이룰 때 공부도, 휴식도 잘할 수 있는 게 맞다. 오늘은 본가에 다녀와서 짧게나마 알고리즘 문제풀이와 객체지향의 사실과 오해를 읽고 정리했다. TIL-37 시작하겠다. 백준 4949 자바(Java) 균형잡힌 세상 https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"..

[백준 2839/자바(Java)] 설탕 배달 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 시간 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 302839 112158 84392 36.699% 문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에..

[백준 18111 자바(Java)] 마인크래프트 https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 (추가 시간 없음) 1024 MB 54089 14225 10578 23.922% 문제 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 땅을 파거..

오늘은 평소와 같이 오전에 운동을 하고 알고리즘을 풀면서 하루를 시작했다. 오늘 계획한 목표는 알고리즘 1문제 / 객체지향의 사실과 오해 1장 정리 / 자기소개서 보완 / 우아한테크세미나 TDD 리팩토링 듣고 정리였고, 공부한 내용을 차례대로 정리해보겠다. 백준 7568 덩치(Java) https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 시간 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 93178 51602 4360..