민규의 흔적

2025년 6월 13일문제 링크 : 백준 33926번 - 인덕이와 보드게임 문제 접근 문제 내용을 요약하면 다음과 같다. N * M 격자판 모양 보드의 각 칸에 정수값이 존재하고, 또한 각 칸은 흰색 또는 검은색으로 칠해져 있다.1행 1열에 공이 소환되며, 1행 1열의 정수값이 공에 기록된다.공이 다른 칸으로 이동하면 해당 칸에 적혀 있는 정수가 공에 더해지며, 만약 이동을 마친 칸이 검은색이라면 공에 적힌 수의 부호가 반전된다. (흰색은 반전되지 않는다.)단, 이동할 때 대각선 방향은 허용하지 않으며 한 번에 변으로 인접한 다른 한 칸으로만 이동할 수 있다.이 때, 1행 1열에서 N 행 M 열까지 공을 최단 경로로 이동시켰을 때 공에 기록된 수의 최댓값을 구한다. 최단 경로라는 문구만 보고 BFS 기반..

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

2024년 8월 6일문제 링크 : 백준 1325번 - 효율적인 해킹 문제 해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.입력첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 ..

2024년 7월 10일문제 링크 : 백준 14889번 - 스타트와 링크 문제  오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sj..

2024년 6월 30일문제 링크 : 백준 15649번 - N과 M (1) 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열입력첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)출력한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력해야 한다. 알고리즘 분류백트래킹문제 접근 자연수 N이 주어졌을 때, 1 ~ N 까지의 자연수 중, 중복 없이 길이 M만큼의 수열로 올 수 있는 모든 경우의 수를 사전 순으로 출력해야 하는 문제이다. 모든 경우의 수..

2024년 6월 26일문제 링크 : 백준 2798번 - 블랙잭 문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다.한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어..