꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/2776 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net 간단한 이분 탐색 문제였습니다. 개발환경:Visual Studio 2022 지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/64062 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이분 탐색을 이용하는 문제였습니다. 알고리즘은 아래와 같습니다. 1. stones 배열의 각 원소의 값이 최소 1이므로 left를 1, right를 stones 배열 내 최고 원소로 선언합니다. 2. 1번에서 구한 left와 right를 기준으로 이분 탐색을 진행하여 mid를 기준으로 조건을 성립하는지 확인합니다. 2.1 조건을 성립하면 answer를 업데이트하고 mid를 높여야..

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/86053 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이분 탐색 알고리즘을 통해 풀면 되는 문제였습니다. 알고리즘은 아래와 같습니다. 1. 이분 탐색의 핵심은 탐색의 범위를 지정하는 것이며 저는 시간을 기준으로 범위를 지정했습니다. 1.1 이 문제의 핵심은 최대 시간을 구하는 것인데 극단적인 케이스로 w = 1, t = 1, g = 1e9, 그리고 s = 1e9라고 가정했을 때 최대 시간은 1e5 + (1e5 * 2) * (2 * ..

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/12984 코딩테스트 연습 - 지형 편집 XX 게임에서는 지형 편집 기능을 이용하여 플레이어가 직접 게임 속 지형을 수정할 수 있습니다. 이 게임에서는 1 x 1 x 1 크기의 정육면체 블록을 쌓아 게임 속 지형을 표현합니다. 이때, 블록이 programmers.co.kr 이분 탐색을 이용해서 푸는 문제였습니다. 이차원 벡터를 매개변수로 넘길 때 참조형으로 넘기는 경우가 훨씬 빠르니 참조형으로 전달해야 합니다. 알고리즘은 아래와 같습니다. 1. 주어진 벡터에서 최소 층과 최대 층을 구한 뒤 이를 기준으로 이분 탐색을 진행합니다. 2. mid와 mid + 1 층을 기준으로 비용을 구한 뒤 더 작은 ..

문제 링크입니다: https://www.acmicpc.net/problem/3045 3045번: 이중 연결 리스트 문제 창영이는 1학년 때 숙제로 했던 이중 연결 리스트 소스를 상근이에게 생일 선물로 보내주었다. 상근이는 드디어 자신이 원하던 기능이 있는 소스를 받게 되어서 매우 기뻤다. 상근이는 하�� www.acmicpc.net 블로그 방문하셨던 분이 질문주셨던 문제여서 풀어보기 시작했던 문제였습니다. 처음에는 제목만 보고 이중 연결 리스트만 구현하면 되는줄 알았는데 생각보다 많은 부분을 고려해야 풀 수 있었던 문제였습니다. 우선, 이중 연결 리스트가 어떤 식으로 삽입 삭제되는지 A 1 4 연산을 예시로 그림과 함께 설명드리겠습니다. 1. 1번 노드를 떼어내야하기 때문에 1번 노드의 다음 노드인 2번..

문제 링크입니다: https://www.acmicpc.net/problem/1300 N이 최대 100,000이므로 브루트 포스 방식으로 진행하면 당연히 TLE가 나는 문제였습니다.저는 욱제님(http://wookje.dance/2017/02/20/boj-1300-K%EB%B2%88%EC%A7%B8-%EC%88%98/) 포스팅을 참고하여 이분 탐색을 통해 풀 수 있었습니다. 알고리즘은 아래와 같습니다.1. 임의의 숫자 mid를 골라 mid보다 작은 숫자의 개수를 파악해서 K 번째 숫자를 구합니다.2. mid는 이분 탐색으로 통해 구하고 low=1, high=K로 시작합니다.3. mid보다 작은 숫자를 효과적으로 구하기 위해 1 ~ N까지 반복문을 돌리고 i * j 하지만, N이 1000보다 크면 mid /..

문제 링크입니다: https://www.acmicpc.net/problem/3090 이분 탐색을 이용해서 풀어야하는 문제였습니다. 알고리즘은 아래와 같습니다.1. 이분 탐색을 진행하며 T번의 변경 안에 모든 인접한 숫자의 차가 mid 이하이면 true 아니라면 false를 반환하는 possible 함수를 구현합니다.2. 기존에 풀었던 이분 탐색과 다르게 최소 차를 찾는 과정이므로 1번이 성립하면 high를 줄이고 성립하지 않으면 low를 늘립니다.3. possible 함수가 성립하고 mid가 기존 차보다 작아야 result 배열을 업데이트해줍니다. #include #include using namespace std; const int MAX = 100000 + 1; int N, T; int A[MAX];..

문제 링크입니다: https://www.acmicpc.net/problem/1764 정렬된 듣도 못한 사람의 리스트를 탐색할 때 시간 복잡도가 O(N)인 find 함수를 사용하면 TLE가 발생하는 문제였습니다.따라서 이진 탐색(binary search) 함수를 직접 구현하여 듣도 못하고 보도 못한 사람을 result 벡터에 추가했습니다,주의할 점은, 이진 탐색을 하기 때문에 v 벡터도 정렬해야하고 사전 순서대로 출력해야하기 때문에 result 벡터도 정렬해야한다는 점입니다! #include #include #include #include using namespace std; int N, M; vector v; //듣도 못한 사람의 리스트 //이진 탐색 bool binarySearch(int low, in..

문제 링크입니다: https://www.acmicpc.net/problem/1920 자료구조 시간에 많이 다루던 이분 탐색, 혹은 이진 탐색 문제였습니다.네이버 사전에서는 이진 탐색이 올바른 표현인데 백준에서는 이분 탐색으로 표현을 하므로 논란이 생기지 않도록 BinarySearch라고 하겠습니다.BinarySearch는 배열 내 숫자가 정렬되어야 올바르게 탐색을 할 수 있습니다.처음부터 끝까지 모두 확인하며 탐색하는 방법은 시간복잡도가 O(N)이지만 BinarySearch는 시간복잡도가 O(logN)이기 때문에 웬만하면 BinarySearch를 통해 탐색하는 것이 효율적입니다.C++에서는 algorithm 헤더파일에 sort 함수를 제공하기 때문에 쉽게 정렬을 할 수 있습니다. 그리고 주의할 점은, c..

문제 링크입니다: https://www.acmicpc.net/problem/2869 굳이 이분탐색법으로 안 풀어도 되지만 이분탐색법 분류에 들어가 있는 문제였기 때문에 BinarySearch를 이용하여 풀었습니다.달팽이는 하루에 (A-B)만큼 움직이고 마지막날에는 A만큼 올라가서 목표지점에 도달하거나 초과합니다.따라서 결과는 totalDay(mid)가 아닌 totalDay+1이여야 합니다.그리고 한가지 주의할 점은 INF를 1,000,000,000 이상으로 설정해야한다는 점입니다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) #include #include using namespace std; const int INF = 1000000000 + 1; int A, B, V; long long ..