Ikjo's Technology blog

버블 정렬이란? 버블 정렬은 정렬 알고리즘 중에서 가장 원시적인 방법으로서 주어진 데이터들을 순회하면서 서로 붙어있는 2개의 데이터씩 비교해, 하나씩 맨 뒤에 차곡차곡 옮겨놓는 방식으로 정렬한다. 그림으로 버블 정렬의 원리 이해하기 아래와 같이 최초 정렬되지 않은 크기 10의 정수형 배열이 있다고 가정했을 때, 버블 정렬을 통해 오름차순으로 정렬해보자. 우선 맨 앞에서부터 서로 붙어있는 2개의 데이터씩 비교를 하는데, 작은 값을 왼쪽에 큰 값을 오른쪽에 옮겨나가면서 배열을 순회한다. 이때 순회의 마지막 지점에서 이루어지는 비교는 주어진 배열에서 가장 큰 값을 배열 맨 뒤에 옮겨놓는 것이 된다. 즉, 맨 마지막 요소는 정렬이 되었다고 볼 수 있으므로 맨 마지막 인덱스 직전까지 앞선 작업들을 반복해나간다. ..

문제 설명 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 접근 방법 해당 문제에서는 N개의 물병을 재분배하면서 최종적으로 남은 '비어있지 않은' 물병이 K개 이하일 경우 (나머지는 모두 빈 물병) 상점에서 최소한으로 산 물병의 개수를 요구하고 있습니다. 그렇다면 N개의 물병을 재분배하는 과정을 먼저 살펴보겠습니다. 우선 N = 1일 때는 K가 1이든 1000이든 (K의 값은 최소 1, 최대 1000) 항상 K 이하이므로, 상점에서 추가로 상점에서 물병을 사올 필요가 없습니다. N = 2일 때는 최초 물병의 용량은..

문제 설명 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 접근 방법 해당 문제는 규칙성을 세워서 해결할 수 있었습니다. 우선 주어지는 x 좌표와 y 좌표 사이의 거리(y - x) 일부(1 ~ 16)에 대해 공간 이동 장치 작동 횟수(이하 '이동 횟수')의 최솟값을 일일이 구해 나타내보면 다음과 같습니다. 이때 이동 경로를 통해 하나 유추해볼 수 있는 것은 만일 거리(distance)의 값이 제곱수(1, 4, 9, ...)에 해당된다면, 이동 횟수는 '해당 제곱수의..

문제 설명 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 방법 해당 문제는 이분 탐색을 이용하여 해결할 수 있었습니다. n명의 입국자에 대해 최대한 빨리 심사를 마치려면, 심사관 중 심사하는데 걸리는 시간이 가장 적은 사람에 가장 많은 입국자를 배정해야합니다. 이를 위해(이후 이분 탐색을 위함이기도) 우선적으로 심사 시간 배열(times)를 오름차순으로 정렬해줍니다. class Solution { int[] times; public long solution(int n, int[] times) { this.times = times; Arrays.sor..

문제 설명 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 방법 해당 문제는 우선순위 큐를 활용하여 해결할 수 있었습니다. 문제 조건 분석 문제에서는 각 작업별로 최초 요청 시간과 작업 시간이 주어졌을 때, 각 작업별로 요청되는 시간부터 작업이 종료되는 시간(이하 '처리 시간' = 대기 시간 + 실행 시간)의 '최소' 평균을 요구하고있습니다. 이때 각 작업별 처리 시간 동안 작업의 상태를 다음과 같이 나타내볼 수 있겠습니다. 여기서 실행 시간은 고정되어있는 값으로, 각 작업별 처리 시간의 최소 평균을 구하기 위해서는 대기 상태를 최대한 줄이는 노력이 ..