본문 바로가기

전체 글

 (346)
[백준] 29792. 규칙적인 보스돌이 풀이 (Python, JavaScript) 29792번: 규칙적인 보스돌이 보스의 체력 $P$의 제한 $2.66 \times 10^{11}$와 드랍하는 메소 $Q$의 제한 $1\,596\,506$은 2023년 8월 10일 업데이트 이전의 가장 많은 체력(카오스 혼테일)과 결정의 가격(노멀 파풀라투스)을 가진 일간 보 www.acmicpc.net 접근한 방법 이 문제는 배낭 알고리즘을 N번 수행해야 하는 문제입니다. 문제가 복잡해보일 수 있지만 배낭 알고리즘을 이해하고 있다면 풀이할 수 있습니다. 배낭 알고리즘은 제약 조건 아래에서 주어진 무게와 가치를 가진 여러 아이템 중에서 어떤 아이템을 선택하여 배낭에 담을지 결정하는 최적화 알고리즘입니다. 일반적으로 최대 가치를 얻고자 할 때 사용합니다. 저는 이런 변형 문제를 풀 때 헷갈리지 않도록 무게와..
[백준] 17471. 게리맨더링 풀이 (Python) 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. 회장뽑기 풀이 (Python, JavaScript) 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 접근한 방법 플로이드 워셜로 최단 경로를 구해 갱신하는 방법으로 접근합니다. 플로이드 워셜은 n^3 복잡도까지 커버할 수 있어서 표본 수가 적다면 가장 쉽고 간단하게 풀이할 수 있습니다. 각 정점을 순회하면서 중간 지점을 통해 경로하는 거리와 원래 놓여있는 거리 중 더 짧은 것으로 결정합니다. 최대한 중간지점을 통해 가지 않는 것이 거리가 1로 가장 짧으므로 회장 후보로 등록될 가능성이 클 것입니다. 탐색 후 각 정점마다 입력되어 있는 거리중 가장 먼 거리를 최..
[백준] 16234. 인구이동 풀이 (Python, JavaScript) 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 접근한 방법 매 반복문을 돌며 BFS를 이용해 조건에 맞는 좌표를 후보지에 등록해두고 탐색이 끝나면 등록된 후보지들의 인구 수를 한꺼번에 변경해주는 방식으로 구현합니다. 1. while 문을 이용해 인구 이동 횟수를 카운트합니다. 2. 연합이 가능한 위치들을 넣을 후보 배열을 만들고 방문하지 않은 위치에 대하여 탐색을 시도합니다. 3. BFS탐색을 시도하여 방문하지 않았고 절댓값 차이가 L과 R 사이 값을 만족하는 위치가 있는 곳을 확인하여 후보지에..
[백준] 18428. 감시 피하기 풀이 (Python, JavaScript) 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net 접근한 방법 완전탐색, 백트래킹 문제입니다. 장애물 3개를 놓을 수 있는 모든 경우의 수를 탐색합니다. 각 경우에서 선생님(T)으로부터 4방향을 모두 검사하여 학생(S)이 한명이라도 발견되는 경우 즉시 탐색을 멈춥니다. 발견되지 않으면 횟수를 카운트합니다. 카운트한 횟수와 선생님의 수가 일치할 경우 모든 감시를 피한 것으로 처리하고 그렇지 않은 경우는 피하지 못한것이 됩니다. Python import sys input = sys.stdin.readline..
[백준] 14938. 서강 그라운드 풀이 (Python) 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 접근한 방법 다른 풀이방법이 많이 있지만 다익스트라 알고리즘으로 풀이합니다. 1번부터 마지막번 노드까지 각각 탐색 시작점을 설정하여 다른 노드까지의 최단 경로 차트를 만든 후 그 안에서 수색 범위(M)안에 해당하는 노드의 아이템 값(items[노드 번호])만 합산해서 최댓값을 구해주면 되는 문제입니다. 코드 풀이 (Python) import sys input = sys.stdin.readline n, m, r = map(int, input().split()) items..
[프로그래머스] lv3. 단어 변환 풀이 (TypeScript) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근한 방법 DFS로 현재 문자열에서 한 글자씩 지워가며 비교하는 방식으로 탐색합니다. 예를 들어 begin이 hit라면, 순차적으로 *it, h*t, hi* 과 같은 위치인 글자가 words배열에도 존재하는지 확인하여 존재하면 진입 횟수를 카운트하여 재탐색합니다. 이때 이미 방문했던 단어들은 제외하기 위해 방문 배열을 설정하여 관리합니다. target이 발견되면 현재까지 저장했던 result 카운트를 갱신한 후 DFS가 완전히 끝날 때 남아있는 result의 값이 최소 비교 횟수가 됩니다. 코드 설명 1. ..
[백준] 1374. 강의실 풀이 (Python) 1374번: 강의실 첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 www.acmicpc.net 접근한 방법 그리디를 이용해 최소 개수로 최대한 많은 강의(작업)를 실행하기 위한 작업 스케줄링 문제입니다. 기본 아이디어는 강의들을 시작 시간을 기준으로 오름차순 정렬한 후, 그리디하게 선택하는 것입니다. 1. 강의들을 시작 시간을 기준으로 정렬합니다. 2. 힙(우선순위 큐)을 사용하여 강의 시간을 스케줄링합니다. 힙은 강의의 종료 시간을 저장하는데 사용되고 항상 종료 시간을 기준으로 최소 힙(가장 작은 종료 시간을 루트에 두는 힙)으로 유지해야..

티스토리툴바