민규의 흔적

2025년 5월 30일문제 링크 : 백준 2467번 - 용액 문제 접근 오름차순으로 각 용액의 특성값이 주어지는데, 두 용액을 선택해 특성값을 더했을 때 0에 가장 근접하는 두 용액의 특성값을 출력하면 되는 문제이다. 만약 그러한 두 용액 쌍이 2개 이상 존재할 경우 아무 용액 쌍이나 출력해도 된다. 모든 용액 쌍을 구해 각 합에 절댓값을 씌워 0에 가장 가까운 용액 쌍을 출력하는 단순한 방식은, N 이 용액의 개수일 때 시간복잡도 O(N^2)을 가지게 된다. 용액의 개수가 최대 100,000이므로 시간 초과를 범할 것이기에 적절하지 않은 방식이다. 이에 나는 투 포인터를 활용해 포인터를 적절하게 움직여 O(N) 시간복잡도를 가지는 알고리즘 설계를 고안했다. 시도 1 (예외가 발생하는 틀린 풀이)(올바른..

2025년 5월 16일문제 링크 : 백준 1300번 - K번째 수 문제 접근 문제는 정말 간단한다. (이런 간단한 문제가 정말 무서운 문제다.) N 이 3이라면 3X3 사이즈의 A 행렬은 다음과 같이 나타낼 수 있다. i 행 j 열의 값은 i * j 로 채워져 있다. 이를 1 X N ^2 사이즈의, A 행렬의 각 요소를 오름차순으로 정렬한 B 벡터는 다음과 같이 나타낼 수 있다. 문제에서 원하는 바는 어떤 정수 k가 주어졌을 때 B[k] 의 값을 구하는 것, 즉 A행렬의 값들 중 k 번째로 작은 값을 구하는 것이다.( k는 min(10^9, N ^2)보다 작거나 같은 자연수 ) Naive method (시간 초과) 단순하게 생각할 수 있는 방법으로 문제를 다음과 같이 접근해 볼 것이다. 1. A 행..

2025년 5월 16일문제 링크 : 백준 28119번 - Traveling SCCC President 문제 접근 문제를 요약하면 다음과 같다. 요약1. 대학 캠퍼스에는 1부터 N 까지 번호가 붙어 있는 N 개의 건물이 있다. 건물 번호는 중복 없이 1부터 N 까지 정수가 정확히 하나씩 존재한다.2. 서로 다른 두 건물을 연결하고 1부터 M 까지 번호가 붙어 있는 M 개의 도로가 있다. 각 도로는 통행하는 데 일정 시간이 소요된다. 두 건물을 직접 잇는 도로가 존재하지 않더라도, 다른 이어진 건물로 우회하여 이동할 수 있다면 두 건물은 연결되어 있다고 표현한다. 모든 건물은 도로를 통해 이어져 있으며, M 은 최소 N - 1개 존재한다. 3. 건물 N 개 모두를 주어진 차례대로 방문해야 한다.4. 한 번 ..

2024년 10월 2일문제 링크 : 백준 2583번 - 영역 구하기 문제 눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.예를 들어 M=5, N=7 인 모눈종이 위에 과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 와 같이 3개의 분리된 영역으로 나누어지게 된다.와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램..

2024년 10월 2일문제 링크 : 백준 1926번 - 그림 문제어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.입력첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다)출력첫째 줄에는 그림의 개수, 둘째 줄에는 그..

2024년 9월 26일문제 링크 : 백준 5972번 - 택배 배송 문제 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 구두쇠라서 최소한의 소들을 만나면서 지나가고 싶습니다.농부 현서에게는 지도가 있습니다. N (1 다음 지도를 참고하세요. [2]--- / | \ /1 | \ 6 / | \ [1] 0| --[3] \ | / \2 4\ | /4 [6] \ | / /1 [4]-..

2024년 9월 5일문제 링크 : 백준 1283번 - 단축키 지정문제한글 프로그램의 메뉴에는 총 N개의 옵션이 있다. 각 옵션들은 한 개 또는 여러 개의 단어로 옵션의 기능을 설명하여 놓았다. 그리고 우리는 위에서부터 차례대로 각 옵션에 단축키를 의미하는 대표 알파벳을 지정하기로 하였다. 단축키를 지정하는 법은 아래의 순서를 따른다.먼저 하나의 옵션에 대해 왼쪽에서부터 오른쪽 순서로 단어의 첫 글자가 이미 단축키로 지정되었는지 살펴본다. 만약 단축키로 아직 지정이 안 되어있다면 그 알파벳을 단축키로 지정한다.만약 모든 단어의 첫 글자가 이미 지정이 되어있다면 왼쪽에서부터 차례대로 알파벳을 보면서 단축키로 지정 안 된 것이 있다면 단축키로 지정한다.어떠한 것도 단축키로 지정할 수 없다면 그냥 놔두며 대소문..

2024년 8월 14일문제 링크 : 백준 9095번 - 1, 2, 3 더하기문제정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.1+1+1+11+1+21+2+12+1+12+21+33+1정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.출력각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 알고리즘 분류다이나믹 프로그래밍 문제 접근 테스트 케이스마다 11 미만의 양의 정수 n이 주어졌을 때, n을 1, 2, 3..