Henzee's Archive

백준 2667번 - 단지번호붙이기 (실버 1)     문제 분석N * N 크기의 지도를 입력받아 대각선을 제외하고 상,하,좌,우로 연결된 집의 모임의 개수와 해당 모임의 집의 개수를 출력하는 문제이다.2차원 벡터에 입력을 저장하고 (0, 0)부터 DFS로 사방 탐색을 하며 단지의 개수와 단지에 속한 집의 개수를 카운트해야겠다고 생각했다.델타 배열을 사용해서 상,하,좌,우에 집이 있는지 확인하고 해당 인덱스가 유효 범위인지 확인 후 DFS 탐색을 해야겠다고 생각했다. 처음 시도2차원 벡터에 지도의 정보를 저장하고 방문하지 않은 집의 위치에서 DFS 탐색을 시작해 단지의 개수를 출력하려고 했으나, 입력 오류와 단지에 속한 집의 개수를 세지 못했다. 원인 분석입력을 받는 과정에서 숫자를 바로 입력받는다고 생각..

백준 1697번 - 숨바꼭질 (실버 1)     문제 분석시작점(N)과 끝점(K)을 알려주고 끝점까지 가는 최단 시간을 구하는 문제이다.위치를 이동하는 3가지 방법이 있다. 현재 위치 + 1현재 위치 - 1현재 위치 × 2최단 시간을 구하는 문제라서 BFS 알고리즘을 적용해야겠다고 생각했다. 처음 시도Queue를 사용해서 3가지 경우의 위치를 넣고 깊이를 출력하는 방법으로 시도했으나, 메모리 초과가 났다.#include #include #include using namespace std;int main(){ int N, K; cin >> N >> K; queue> q; q.push({ N, 0 }); while (!q.empty()) { vector node = q.front(); q.pop(); ..

백준 1260번 - DFS와 BFS (실버 2)       이 문제를 풀기 위해서는 그래프 탐색에 대해 알아야 한다. 그래프 탐색이란?하나의 정점에서 시작해 차례대로 모든 노드를 방문하는 것그래프 탐색의 방법깊이 우선 탐색 (Depth First Search, DFS)너비 우선 탐색 (Breadth First Search, BFS)그래프 탐색의 두 가지 방법인깊이 우선 탐색 (Depth First Search, DFS)과 너비 우선 탐색 (Breadth First Search, BFS)에 대해 알아보자.  DFS(Depth First Search)란?깊이 우선 탐색시작 지점에서 출발하여 한 방향으로 탐색탐색을 더이상 할 수 없으면 마지막 만난 지점으로 돌아와 다른 방향으로 다시 탐색후입 선출(LIFO :..

백준 2512번 - 예산 (실버 2)     이 문제는 배정할 예산의 최소값과 최대값을 가지고중간값을 구하고 중간값이 될 수 있는 범위를 줄여나가며배정 예산의 최대값을 구해줄 수 있다.   예를 들어, 예제 입력 1과 같이 주어졌을 때4120 110 140 150485 배정할 예산의 최소값은 1이고, 최대값은 150이 된다. (예산 요청 범위가 1 이상 100,000 이하)그러면, 중간값은 (1 + 150) / 2 = 75 이다. (몫이 소수점이면 소수점 아래는 버림)중간값 75가 예산 요청 값인 120보다 작기 때문에 중간값인 75를 저장하고다음 요소를 탐색한다.  120부터 150까지 탐색을 마친 뒤 저장된 예산의 합은 75 X 4 = 300 이다.M과 비교했을 때 300 이 더 작기 때문에현재 중간..

백준 2470번 - 두 용액 (골드 5)       이분 탐색으로 풀어야겠다고 생각했는데 방향을 잘못 잡아서용액의 합의 최대, 최소를 구하고 탐색하려 했으나도저히 잘 동작하는 알고리즘이 생각나지 않아서포기하고 다른 블로그에서 아이디어를 보고 문제를 다시 풀어봤다.   이 문제는 포인터를 두 개(start, end)를 가지고 합을 구하며 범위를 조여나가는 방법으로 풀 수 있다. 먼저, 오름차순으로 배열(liquid)을 정렬한 뒤시작점(start)과 끝점(end)의 위치를 맨 앞(인덱스 0), 맨 뒤(인덱스 N-1)로 두고두 용액의 합이 음수일 경우 시작점의 위치를 오른쪽으로 옮기고(start += 1)두 용액의 합이 양수일 경우 끝점의 위치를 왼쪽으로 옮기며(end -= 1) 탐색하면 된다. 그 과정에서 ..

백준 2343번 - 기타 레슨 (실버 1)        문제를 읽고 이분 탐색으로 풀어야 하는 문제라는 것은 알았지만,강의 길이의 합을 어떻게 구해야 할지 전혀 감이 안와서챗지피티의 도움을 좀 빌렸다😅  블루레이의 최소 길이(min)와 최대 길이(max)를 구한 뒤두 수의 중간값(mid)을 가지고 정답을 도출해내는 것이 방법이었다..!  블루레이의 최소 길이는 입력으로 받은 강의 시간의 최대값이다. 블루레이의 최대 길이는 모든 강의 시간의 합이다.입력 받은 강의 시간을 배열에 넣어서 순서대로 더한 뒤 블루레이 길이의 중간값보다 커지면 배열의 다음 인덱스부터 다시 더하고 블루레이 개수를 하나 올려준 뒤블루레이 개수에 따라서 최대 길이와 최소 길이를 다시 정해준다.  글로만 읽어서는 도무지 이해가 안갈 수..

백준 11663번 - 선분 위의 점 (실버 3)        선분의 시작점과 끝점을 주고 선분 위의 점 개수를 출력하는 문제이다.  처음 접근 방식은 시작점부터 끝점까지 돌며 1,000,000,000 크기의 배열에 인덱스에 접근해서개수를 세는 방식이었다. 그러나 메모리 초과로 실패했고, 이분 탐색으로 시간 복잡도를 줄여서 풀어야겠다고 생각했다.  이분 탐색의 시간 복잡도는 O(logN) 이므로 M개의 쿼리를 처리할 때 전체 쿼리를 처리하는 시간 복잡도는 O(M⋅logN) 이다. 따라서, 효율적으로 주어진 조건 안에서 문제를 풀 수 있다.      알고리즘※ 조건 ※ 1 ≤ N, M ≤ 100,000두 점의 좌표는 항상 다르다.1 ≤ 좌표 ≤ 1,000,000,000 1. 점의 좌료를 저장한 배열을 오름차..

백준 1654번 - 랜선 자르기 (실버 2)        이 문제는 랜선 길이를 알려주고 주어진 개수만큼 자를 때랜선 길이의 최대값을 구하는 문제이다.  처음 문제에 접근한 방식은 주어진 랜선 길이의 최소값을 가지고 랜선을 자르며 랜선 개수를 구한 뒤랜선 개수가 주어진 개수보다 큰지 작은지 여부를 판단해서작다면 최소값에서 1을 빼주어 다시 탐색하는 방법을 사용해서 문제를 풀었다.  하지만, 위 방법은 최소값에서 1을 빼주며 일일이 탐색을 다시 해야하기 때문에시간 복잡도가 매우 높아지는 문제가 발생한다.  따라서 위 방법이 아닌 이분 탐색을 이용하여 시간 복잡도를 O(K⋅log⁡(최대 길이))로 줄여서 해결하는 방법을 채택했다.   먼저, 이분 탐색이란?자료의 가운데에 있는 항목의 키 값과 비교해 다음 탐..

문제 링크 : https://www.acmicpc.net/problem/2920 문제 설명다장조는 c d e f g a b C, 총 8개 음으로 이루어져있다. 이 문제에서 8개 음은 다음과 같이 숫자로 바꾸어 표현한다. c는 1로, d는 2로, ..., C를 8로 바꾼다.1부터 8까지 차례대로 연주한다면 ascending, 8부터 1까지 차례대로 연주한다면 descending, 둘 다 아니라면 mixed 이다.연주한 순서가 주어졌을 때, 이것이 ascending인지, descending인지, 아니면 mixed인지 판별하는 프로그램을 작성하시오. 입력첫째 줄에 8개 숫자가 주어진다. 이 숫자는 문제 설명에서 설명한 음이며, 1부터 8까지 숫자가 한 번씩 등장한다. 출력첫째 줄에 ascending, desc..

문제 링크 : https://www.acmicpc.net/problem/10809 문제 설명알파벳 소문자로만 이루어진 단어 S가 주어진다. 각각의 알파벳에 대해서, 단어에 포함되어 있는 경우에는 처음 등장하는 위치를, 포함되어 있지 않은 경우에는 -1을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 단어 S가 주어진다. 단어의 길이는 100을 넘지 않으며, 알파벳 소문자로만 이루어져 있다.  출력각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다.만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출력한다. 단어의 첫 번째 글자는 0번째 위치이고, 두 번째 글자는 1번째 위치이다.  해결 과정 (핵심 아이디어)..