solved.ac class 163

[백준 2096] 내려가기 [Python]

풀이 문제에서 주어진 규칙에 따라 N줄을 내려가면서 최댓값과 최솟값을 구하면 되는 문제다. 주어진 규칙을 살펴보자. 별의 위치에 따라 더하거나 뺄수 있는 칸의 범위가 달라진다. 이번에는 아래 그림을 살벼보자 별이 기준이 아닌, 동그라미를 기준으로 각각 빨,초,파의 선을 그었다. 첫 번째 칸에 위치한 동그라미는 첫 번째와 두 번째의 별에 대해 더하거나 뺄 수 있다는 의미이다. 앞으로 계산해야되는 칸을 각각 max_dp, min_dp에 담아주자. 1번 줄은 그대로 담으면 된다. 2번 줄 부터 N번 줄까지는 위에서 말했듯 동그라미를 기준으로 계산하듯이 계산해주면 된다. 각각 max_dp와 min_dp를 구하는 코드이다. 코드가 너무 길다고 생각된다면 아래처럼 쌍으로 묶어주어 관리해도 된다. dp[0] = [ ..

[백준 1865] 웜홀 [Python]

풀이 가중치가 양수인 간선은 양방향, 음수인 간선은 단방향인 그래프에서 출발 정점에서 도착 정점까지 돌아오는 음수사이클이 존재하는지 확인하면 되는 문제다. 특이한 점이라 하면 출발점이 주어지지 않았고, 그래프 내에 어디든 상관없이 조건에 부합하는 음수 사이클이 존재하는지 여부만 알면 되는 문제다. 때문에 모든 정점을 출발점으로 간주하고 bellman ford를 여러 번 진행해야 한다. 만약 탐색 후 dist가 inf가 아니라면, 이미 탐색을 한 번 완료한 그래프이기에, 탐색이 되지 않은 또 다른 그래프에 대해서만 탐색을 진행해주었다. 좀 더 빠르게 탐색해보자. 어떤 정점을 기준으로 조건에 부합하는 음수 사이클이 존재하는지 모르기 때문에, 어차피 모든 정점에 대한 탐색이 이루어져야 하며 매 탐색마다 시작 ..

[백준 11375] 열혈강호 [Python]

풀이 두 그룹이 있을 때, 모든 간선이 가중치가 1이고 다른 그룹으로만 향하는 그래프를 Bipartite Graph 라고 한다. 이 때, 간선을 통해 다른 정점을 점유한 상태를 matching한다고 하며 Bipartite Graph에 대한 matching을 Bipartite Matching이라고 한다. 즉, 간선의 가중치가 전부 1인 Bipartitle Graph에서 maximun flow을 구해주는 문제는 maximun matching을 구해주는 문제와 동일하다. 때문에 간단하게 DFS를 이용해 O(VE), O((N+M)E) 안에 구현하는 방법을 사용할 수 있다. 최종적으로 연결된 정점을 기록할 match 배열과, 바로 매칭이 되지 않은 경우(다른 정점과 이미 매칭된 경우) 현재 정점을 최종적으로 매칭..

[백준 21736] 헌내기는 친구가 필요해 [Python]

풀이 단순한 graph 문제이다. 입력을 받으면서 탐색 위치를(I)를 찾아주자. BFS로 풀이했다. 벽(X)이 아닌 경우와, 이미 방문하지 않은 공간을 탐색해주어야 한다. 위의 조건이 성립하고, 도연이가 사람(P)을 만났다면 만난 사람 수를 업데이트 해주자. 만약 만난 사람이 0명이라면 "TT"를 출력해주어야 한다는 점도 유의하자. 소스코드 소스코드 보기 출처 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net

[백준 20529] 가장 가까운 세 사람의 심리적 거리 [Java]

풀이 N개의 중 3개의 MBTI에 대해서 가장 작은 심리적 거리를 구해야 한다. 모든 경우의 수를 전부 탐색하면 N^3 이기에 당연히 시간초과가 발생할 것이다. 때문에 구한 거리가 0인지 확인을 하고, 중간에 loop를 빠져나와야 한다. 비둘기집 원리를 통해 더 줄여보자. MBTI에 대한 심리적 거리의 최선의 경우는 뭘까? bruteforce이지만, 심리적 거리가 0인 경우 더 이상의 탐색이 무의미하기에 중단 해주어 시간초과가 발생하지 않는다. 심리적 거리가 0이라는 조건 이후의 탐색이 무의미하다면, 심리적 거리가 0이 되는 최악의 경우는 무엇일까? 바로 비둘기집 원리에 따른 33명이다. 서로 다른 MBTI를 가진 16명이 2명씩 총 32명 있을 경우 심리적 거리는 0이 될 수 없다. 33명부터 동일한 ..

[백준 14940] 쉬운 최단거리 [Java]

풀이 각 지점에서 목표지점(2) 까지의 거리를 출력하는 문제로 반대로 생각해서 목표지점에서 출발해 갈 수 있는 모든 거리에 대한 거리를 계산하는 문제로 풀이할 수 있다. 입력을 받으면서 목표지점(=출발지점)을 찾으면 0으로 대신 넣어주고, 1이면 -1로 넣어주자. 그 외의 숫자는 그대로 넣어주면 된다. 1일 때 -1을 넣어주는 이유는 출발지점으로부터 출발했을 때 갈수없는 땅(0)으로 둘러싸인 영역은 도달할 수 없는 위치(-1)임을 미리 표시하기 위함이다. 출발지점에서 도달할 수 있는 영역의 1들이 전부 -1 로 바뀌면 문제가 없을까? 그렇다, 어차피 도달할 수 있는 영역의 거리들은 이전에 도달한 거리의 값(출발지점 = 0 이므로 0 이상의 수)에 1을 더한 값이기에 결국은 덮어쓰일 것이다. 그 이후로는 ..

[백준 18110] solved.ac [Python]

풀이 정렬된 점수들의 절사평균을 구하는 문제이다. 가장 작은 15%의 인원과, 가장 큰 15%의 인원을 제외한 후 나머지 인원에 대해 평균을 구한 후 반올림을 해서 출력해주면 된다. 문제는 단순하지만 Python을 사용하다보니 예상치 못한 복병들이 많았다. 우선 첫 번째로 주어지는 점수들의 개수가 최대 3 x 10^5 이다. 실버 난이도의 문제답지 않게 많은 입력이 주어진다. 빠른 입출력을 해주자. 그 다음으로는 전체 인원에 대한 절사평균이 성립하지 않는 경우다. 즉, 인원이 너무 적어 절사평균을 구하기 위해 제외해야할 인원이 적은 경우이다. 15%에 해당하는 인원의 반올림한 값이 0보다 큰 경우에만 인원을 제외시켜 주자. 다른 하나는 Python의 round()의 작동 방식에 대한 문제다. 일반적으로 ..

[백준 9465] 스티커 [Python]

풀이 스티커를 사용할 때 변을 공유하는 스티커는 사용할 수 없다는 조건이 있다. 따라서, 스티커를 최대한 많이 사용하고자 한다면 대각선으로 진행하며 사용할 때 가장 많은 스티커를 사용할 수 있다. 총 5개의 스티커를 고를 수 있다. 하지만, 이러한 방식이 항상 스티커 점수들의 최댓값임을 보장하지 않는다. 문제에서 주어진 경우를 살펴보자. 50 - 50 - 100 - 60 으로 총 4개의 스티커를 사용했지만, 스티커 점수들의 합은 260으로 이전에 선택한 경우보다 큰 점수를 가진다. 따라서, 각 스티커 영역마다 가질 수 있는 최댓값을 기록할 때 아래 그림과 같은 선택지를 고려해야 한다. 먼저, 단순하게 대각선으로 선택한 경우다. 주황색은 선택하지 못하는 영역, 초록색은 지금 선택한 영역, 파란색은 선택할 ..

[백준 11054] 가장 긴 바이토닉 부분 수열 [Python]

풀이 LIS문제의 원리를 잘 다룬 문제이다. 기존에 O(N^2) 방식으로 LIS를 구할 때, 비연속 LIS 길이를 찾을 수 있었다. [백준 11053] 가장 긴 증가하는 부분 수열 [Python] 풀이 LIS (Longest Increasing Subsequence)는 최장 증가 부분 수열로, N개의 원소에 대해 요소를 골라 만든 부분 수열을 만들 때 각 원소가 이전 요소보다 큰 원소로 이루어진 부분 수열을 의미한다. 즉, 가 kyr-db.tistory.com LDS를 찾을 때도 마찬가지로 같은 방식을 사용했다. [백준 11722] 가장 긴 감소하는 부분 수열 [Python] 풀이 일전에 풀었던 LIS문제에서 사용한 방법을 응용해 풀이할 수 있다. [백준 11053] 가장 긴 증가하는 부분 수열 [Pyt..

[백준 11053] 가장 긴 증가하는 부분 수열 [Python]

풀이 LIS (Longest Increasing Subsequence)는 최장 증가 부분 수열로, N개의 원소에 대해 요소를 골라 만든 부분 수열을 만들 때 각 원소가 이전 요소보다 큰 원소로 이루어진 부분 수열을 의미한다. 즉, 가장 긴 비연속 부분 수열의 길이를 알아내면 된다. 그렇다면, LIS는 어떻게 만들어 지는가? 기본적으로 위에서 언급했 듯 이전 요소보다 큰 요소가 나오면 된다. 문제의 입력에서 알 수 있듯 항상 증가만 하는 요소로 주어지지 않는다. 아래 그림을 보자. 입력받은 배열 A와, 배열에 대한 LIS 길이를 기록할 dp배열이 있다. 그 아래에는 단순히 이전 요소보다 큰 요소가 나오는 경우만 기록한 Increasing Subsequence이다. 첫 번째 경우 10 - 20 - 30 - ..