binary6 [프로그래머스] 징검다리 문제 링크: https://programmers.co.kr/learn/courses/30/lessons/43236 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 프로그래머스 기준 Level 4인, 약간 어려운 문제입니다. 문제 내에서 총 거리가 주어지고 (distance), 각 바위의 위치가 주어집니다. 이후 제거해야 하는 바위의 수 (n)이 주어집니다. n개의 바위를 제거한 후 시작점 - 각 바위 사이 - 도착점 사이의 거리를 구했을 때, 어떤 바위를 제거했느냐에 따라 각 바위 사이 거리가 달.. 2021. 10. 8. [백준 1300번] K번째 수 난이도: 골드 III 문제 링크: https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net N의 최대 크기가 10만이므로, 배열에 들어갈 모든 수를 계산하기에도 벅찹니다 (10만 x 10만 번의 연산). 따라서 이 문제는 모든 숫자를 계산하지 않고 풀 수 있어야 합니다. K번째 수를 구한다는 것은, 이보다 작은 수가 K-1개 존재한다는 뜻입니다. 이러한 상황에서 비교 연산을 훨씬 덜 하면서 원하는 수를 탐색하는 방법 중 하.. 2021. 9. 17. [프로그래머스] 가사 검색 출처: 2020 KAKAO Blind Recruitment 문제 링크: programmers.co.kr/learn/courses/30/lessons/60060 코딩테스트 연습 - 가사 검색 programmers.co.kr 문제에 대한 자세한 내용은 링크를 통해 직접 확인하시기 바랍니다. 이분 탐색 문제를 풀던 중 나온, 카카오 기출문제들이 으레 그렇듯 꽤 난이도 있는 문제입니다. 정확히는 정석대로 이분 탐색을 구현하는 것이 아닌, lower_bound와 upper_bound 함수를 이용하여 구현하는 방식입니다. 문제를 접근한 순서는 다음과 같습니다. 각 단어를 길이에 따라 나눈다. 각 단어 길이 배열을 알파벳 순서로 정렬한다. 이진 탐색을 통해 쿼리의 단어로 시작하는 마지막 단어와 첫 단어의 인덱스를 구.. 2021. 3. 8. [백준 2110번] 공유기 설치 난이도: 실버 1 문제 링크: www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 이분 탐색을 이용하는 문제 중 꽤 애를 먹은 문제입니다. 어느 부분에서 이분 탐색을 이용해야 하는지 고민을 많이 했는데, 다른 블로그 (링크)의 글을 참고하여 알고리즘을 이해했습니다. 문제의 접근 순서는 다음과 같습니다. 주어진 집들의 좌표를 오름차순으로 정렬한다 (이분 탐색의 기본 조건). 집들 사이의 거리를 초기화한다. 최솟값.. 2021. 3. 8. 이진 탐색 탐색이라 함은, 데이터의 집합 중에서 원하는 값을 찾는 것을 의미합니다. 오늘 다루어 볼 내용은 이진 탐색 (binary serach)인데, 이에 앞서 가장 기본적인 탐색 방법인 순차 탐색을 다루고자 합니다. 순차 탐색 순차 탐색 (sequential search)는 배열 내의 특정 데이터를 찾기 위해 앞에서부터 순차적으로 확인하는 방법입니다. 정렬되지 않은 배열에서 데이터를 찾을 때, 시간만 충분하다면 순차 탐색이 좋은 방법이 될 수 있습니다. 'Carrot' 이라는 문자열을 찾는 과정입니다. 파란색은 현재 'Carrot'와 비교하는 문자열, 빨간색은 이미 비교하였으며 일치하지 않은 문자열, 초록색은 목표로 하는 문자열입니다. 첫 번째 문자열 'Apple', 두 번째 문자열 'Banana'는 일치하지 .. 2021. 2. 4. [백준 2357번] 최솟값과 최댓값 난이도: 골드 1 문제 링크:www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 기말고사 전에 공부해서 풀었던 문제이지만... 블로그에 글로 정리하기에는 바빠서 지금에서야 정리해서 올립니다. 언뜻 보면 쉬워 보이는 최솟값, 최댓값 찾기 문제입니다. 처음엔 별 생각 없이 배열에 정렬해서 넣고 주어진 구간을 전부 탐색하여 최솟값, 최댓값을 찾아왔으나... 시간 초과가 걸렸습니다. 숫자의 크기가 크고, 갯수가 최대 10만 개가 되.. 2020. 12. 23. 이전 1 다음
