민규의 흔적

2024년 7월 12일문제 링크 :백준 3085번 - 사탕 게임문제 상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.입력첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, ..

2024년 7월 12일문제 링크 : 백준 1182번 - 부분수열의 합문제  N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.출력첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다. 알고리즘 분류백트래킹브루트포스 알고리즘 문제 접근 백트래킹을 활용해 완전탐색 해야하는 문제이다. 길이가 1일 때의 부분 수열부터 길이가 N일 때의 부분수열까지 모든 조합을 구해 합이 0이 되는 ..

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

2024년 7월 8일문제 링크 : 백준 2606번 - 바이러스문제  신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때,..

2024년 7월 8일문제 링크 : 백준 2644번 - 촌수계산문제  우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.입력사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n..

2024년 7월 8일문제 링크 : 프로그래머스 - 모의고사 문제 접근 문제가 요구하는 사항들이 명확해, 문제가 요구하는 사항들을 잘 읽기만 한다면 간단히 풀 수 있는 문제라고 생각한다. 수포자는 총 3명이다.1번 수포자는 1, 2, 3, 4, 5를 반복하며 찍는다.2번 수포자는 2, 1, 2, 3, 2, 4, 2, 5를 반복하며 찍는다.3번 수포자는 3, 3, 1, 1, 2, 2, 4, 4, 5, 5를 반복하며 찍는다.가장 많이 맞은 사람을 배열에 출력하면 되며, 가장 많이 맞은 사람이 여럿 존재할 경우 오름차순으로 배열에 담아 출력한다. 전체 코드 def solution(answers): answer = [] first_idx = 0 first_cnt = 0 first = [1, ..

2024년 7월 7일힙(Heap) 힙이란, 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리 기반의 자료구조이다. 부모 노드와 자식 노드의 일련된 대소 관계가 성립하는 구조를 보인다. 최대 힙(max heap) 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리를 의미한다. 위 그림과 같이, 자식 노드를 가지고 있는 모든 부모 노드는 무조건 자식 노드보다 크거나 같은 값을 지니는 양상을 보인다. 최소 힙(min heap) 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리를 의미한다. 위 그림과 같이, 자식 노드를 가지고 있는 모든 부모 노드는 무조건 자식 노드보다 크거나 같은 값을 지니는 양상을 보인다. 부모 노드와 자식 노드의 연결 관..

2024년 7월 5일문제 링크 : 프로그래머스 - 게임 맵 최단거리 문제 접근 한 칸을 이동하는 과정을 한 턴 이라고 이야기하겠다. 적진(지도의 맨 오른쪽 맨 아래 위치)으로 가는데 필요한 최소한의 턴을 구하는 문제이다. 이 문제는 1일차에 [0, 0]에서부터 바이러스가 하루에 주변 한 칸씩 퍼질 때 [n - 1, m - 1]은 며칠차에 감염되는가? 와 같은 문제이다. 문제를 풀기 위해선 다음과 같은 접근 방식이 필요하다. 한 턴에 갈 수 있는 칸은 여러 개 일 수 있다. 나는 이 문제를 BFS 방식으로 풀이할 것이다. 또한, 뒤에서 말할 변수들의 이름은 다음과 같은 뜻을 가지고 있다고 생각해두자. queue = 다음 방문 예정인 노드들 next_v = 지금 위치에서 한 턴 뒤에 갈 수 있는 모든 노드들..