29792번: 규칙적인 보스돌이 보스의 체력 $P$의 제한 $2.66 \times 10^{11}$와 드랍하는 메소 $Q$의 제한 $1\,596\,506$은 2023년 8월 10일 업데이트 이전의 가장 많은 체력(카오스 혼테일)과 결정의 가격(노멀 파풀라투스)을 가진 일간 보 www.acmicpc.net 접근한 방법 이 문제는 배낭 알고리즘을 N번 수행해야 하는 문제입니다. 문제가 복잡해보일 수 있지만 배낭 알고리즘을 이해하고 있다면 풀이할 수 있습니다. 배낭 알고리즘은 제약 조건 아래에서 주어진 무게와 가치를 가진 여러 아이템 중에서 어떤 아이템을 선택하여 배낭에 담을지 결정하는 최적화 알고리즘입니다. 일반적으로 최대 가치를 얻고자 할 때 사용합니다. 저는 이런 변형 문제를 풀 때 헷갈리지 않도록 무게와..

17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 접근한 방법 이 문제를 풀기 위해선 두 가지 과정이 필요합니다. 1. 선거구를 나눌 두 개의 조합 2. 각 조합을 탐색하여 서로 연결되어 있는 지 확인 먼저 두 개의 조합(A, B)으로 나누기 위해서는 1개 조합, 2개 조합, ... (N / 2)개 조합을 먼저 구한 후(A) 전체 조합에서 A 원소들을 빼준 것을 (B)로 정합니다. 예를 들면 A = [1, 2, 3, 4]의 조합은 1개 조합일 때 -> A = 1. B = [1, 2, 3, 4] - A = 2, 3, 4 -> A = 2..

2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 접근한 방법 플로이드 워셜로 최단 경로를 구해 갱신하는 방법으로 접근합니다. 플로이드 워셜은 n^3 복잡도까지 커버할 수 있어서 표본 수가 적다면 가장 쉽고 간단하게 풀이할 수 있습니다. 각 정점을 순회하면서 중간 지점을 통해 경로하는 거리와 원래 놓여있는 거리 중 더 짧은 것으로 결정합니다. 최대한 중간지점을 통해 가지 않는 것이 거리가 1로 가장 짧으므로 회장 후보로 등록될 가능성이 클 것입니다. 탐색 후 각 정점마다 입력되어 있는 거리중 가장 먼 거리를 최..

16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 접근한 방법 매 반복문을 돌며 BFS를 이용해 조건에 맞는 좌표를 후보지에 등록해두고 탐색이 끝나면 등록된 후보지들의 인구 수를 한꺼번에 변경해주는 방식으로 구현합니다. 1. while 문을 이용해 인구 이동 횟수를 카운트합니다. 2. 연합이 가능한 위치들을 넣을 후보 배열을 만들고 방문하지 않은 위치에 대하여 탐색을 시도합니다. 3. BFS탐색을 시도하여 방문하지 않았고 절댓값 차이가 L과 R 사이 값을 만족하는 위치가 있는 곳을 확인하여 후보지에..

18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net 접근한 방법 완전탐색, 백트래킹 문제입니다. 장애물 3개를 놓을 수 있는 모든 경우의 수를 탐색합니다. 각 경우에서 선생님(T)으로부터 4방향을 모두 검사하여 학생(S)이 한명이라도 발견되는 경우 즉시 탐색을 멈춥니다. 발견되지 않으면 횟수를 카운트합니다. 카운트한 횟수와 선생님의 수가 일치할 경우 모든 감시를 피한 것으로 처리하고 그렇지 않은 경우는 피하지 못한것이 됩니다. Python import sys input = sys.stdin.readline..

14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 접근한 방법 다른 풀이방법이 많이 있지만 다익스트라 알고리즘으로 풀이합니다. 1번부터 마지막번 노드까지 각각 탐색 시작점을 설정하여 다른 노드까지의 최단 경로 차트를 만든 후 그 안에서 수색 범위(M)안에 해당하는 노드의 아이템 값(items[노드 번호])만 합산해서 최댓값을 구해주면 되는 문제입니다. 코드 풀이 (Python) import sys input = sys.stdin.readline n, m, r = map(int, input().split()) items..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근한 방법 DFS로 현재 문자열에서 한 글자씩 지워가며 비교하는 방식으로 탐색합니다. 예를 들어 begin이 hit라면, 순차적으로 *it, h*t, hi* 과 같은 위치인 글자가 words배열에도 존재하는지 확인하여 존재하면 진입 횟수를 카운트하여 재탐색합니다. 이때 이미 방문했던 단어들은 제외하기 위해 방문 배열을 설정하여 관리합니다. target이 발견되면 현재까지 저장했던 result 카운트를 갱신한 후 DFS가 완전히 끝날 때 남아있는 result의 값이 최소 비교 횟수가 됩니다. 코드 설명 1. ..

1374번: 강의실 첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 www.acmicpc.net 접근한 방법 그리디를 이용해 최소 개수로 최대한 많은 강의(작업)를 실행하기 위한 작업 스케줄링 문제입니다. 기본 아이디어는 강의들을 시작 시간을 기준으로 오름차순 정렬한 후, 그리디하게 선택하는 것입니다. 1. 강의들을 시작 시간을 기준으로 정렬합니다. 2. 힙(우선순위 큐)을 사용하여 강의 시간을 스케줄링합니다. 힙은 강의의 종료 시간을 저장하는데 사용되고 항상 종료 시간을 기준으로 최소 힙(가장 작은 종료 시간을 루트에 두는 힙)으로 유지해야..

5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 접근한 방법 최장 공통 부분수열을 구하는 문제로써 DP를 활용하여 해결할 수 있습니다. 1. DP 테이블 d를 생성하여 문자열의 길이에 따른 최장 공통 부분 수열 길이를 저장합니다. d[i][j]는 s1의 첫 i개 문자와 s2의 첫 j개 문자 사이에서의 최대 공통 부분 수열의 길이를 나타냅니다. 2. 문자열을 비교해 최장 공통 부분 수열 길이를 갱신합니다. 이중 반복문을 사용하여 s1과 s2의 각 문자를 순회하면서 만약 s1[i - 1]과 s2[j -..

접근한 방법 미로에서 최단 경로를 찾는 BFS 알고리즘을 사용하여 해결할 수 있습니다. 최소 heap 자료구조를 이용하여 매 방문마다 가장 적게 벽을 바꾼 지점의 좌표를 꺼내서 해당 좌표에서만 탐색을 나아가면 최소 개수로 벽을 바꿀 수 있습니다. 1. 큐에서 원소를 하나씩 꺼내면서 해당 위치의 상하좌우를 체크합니다. 2. 벽이 있는 경우는 +1 카운트 하여 큐에넣고 그렇지 않은 경우는 그대로 큐에 넣어줍니다. 3. 마지막 지점에 닿으면 현재까지의 카운트를 출력하고 종료합니다. Python import sys input = sys.stdin.readline n = int(input()) arr = list(list(map(int, input().rstrip())) for _ in range(n)) from..

5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 접근한 방법 그래프의 간선 가중치를 고려한 최단 경로를 구하는 문제입니다. 힙 자료구조를 이용한 다익스트라 알고리즘으로 풀이할 수 있습니다. dist는 노드 간의 최단 거리를 저장할 리스트로 초기값은 무한대(inf)로 초기화하고 1번 노드부터의 최단 거리를 나타냅니다. graph는 각 노드에 연결된 엣지 정보를 저장하는 리스트입니다. 먼저 그래프 정보를 구성해야 합니다. m번 반복하여 입력으로 주어지는 간선 정보를 바탕으로 생성합니다. 양방향 그래프이므로 두 노드 간의 ..

2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 접근한 방법 답을 도출하기 위한 풀이 로직은 쉽지만 메모리, 시간 초과 문제로 인해 정답 비율이 낮은걸로 보입니다. 이 문제를 만약 2개의 배열을 만들어 중간 결과를 저장하는 방식으로 코드를 짰다면 입력 데이터가 클 때 메모리 제한(4mb)에 걸리게 될겁니다. 따라서 입력 데이터의 최댓값과 최솟값을 계산하면서 중간 결과를 저장하는 대신, 이전 단계의 계산 결과만 활용하여 계산해 나가는 방식을 사용하면 풀이할 수 있습니다. 첫 입력 데이터 한 줄을 초깃값으로 정해놓고 다음 입력..