Language/Python

2176번: 합리적인 이동경로 첫째 줄에 정점의 개수 N(1 < N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 100,000이 주어진다. 다음 M개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 길이 www.acmicpc.net 풀이 과정 DP를 최단 경로를 탐색하기 위하여 사용된다. dp의 i번째 인덱스는 출발하는 합리적인 이동경로의 수를 의미하며, 도착점 2번 노드부터 탐색을 시작한다. 각 정점까지의 최단경로를 갱신하는 과정에서 현재 노드까지 최단 경로의 길이가 다음 노드까지 최단 경로의 길이보다 짧을 경우, 다음 노드와 현재 노드 사이에 합리적인 이동 경로가 존재한다는 뜻이다. 풀이 과정 import sys,heapq; input =..

10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 풀이 과정 해당 문제는 정말 대표적인 다익스트라 문제인 거 같다.. 문제를 해결하는데 몇 분도 안 걸린 기분 좋은 문제였다. 😊 1. 입력받은 T만큼 반복문을 돌린다. 2. 입력받은 컴퓨터 수(n), 의존성 관계(d), 감염된 컴퓨터 번호(c)를 입력받는다. 3. 필자는 의존성 관계를 표현하는 2차원 배열을 computers 이름으로 할당해주었다. 그리고 감염된 컴퓨터가 있을 경우 해당 컴퓨터가 몇 초 후에 감염되는지 확인하기 위하여 infection이라는 이름으로 ..

25239번: 가희와 카오스 파풀라투스 차원의 균열 패턴이 끝난 후, 파풀라투스가 회복하는 체력이 h%라고 할 때, h를 출력해 주세요. www.acmicpc.net 풀이 과정 1. 현재 시간을 hh, mm으로 받고 정수형으로 저장하였다. 2. 영역의 값을 num 배열에 받고, 영역에 접근하였는지 안 했는지 확인하기 위하여 크기가 6인 bool 형식의 배열을 "seal"로 초기화해주었다. 3. 이벤트 수(L) 만큼 반복문을 돌린다. 3-1. 만약 입력받은 s.T 가 1분이 지났다면 반복문을 종료시켰다. 3-2. 입력받은 명령어가 "^" 이면 현재 시간이 가리키는 영역을 False로 변경해준다. 3-3. 입력받은 명령어가 시간이 포함될 경우 3-3-1. 명령어에 "MIN" 이 포함될 경우 : 현재 분(mm..

6209번: 제자리 멀리뛰기 첫 번째 줄에는 갇힌 돌섬으로부터 탈출구까지의 거리 d(1 ≤ d ≤ 1,000,000,000), 작은 돌섬의 수 n(0 ≤ n ≤ 50,000), 제거할 수 있는 작은 돌섬의 수 m (0 ≤ m ≤ n)이 공백으로 구분되어 주어진다. 두 www.acmicpc.net 풀이 과정 해당 문제는 저어어어어엉말 어려웠다.. 👏👏 해당 문제의 알고리즘 분류는 이분 탐색으로 표기되어 있었고, 그것은 나에게 도움이 되지 않았다...😂😂 결국 이분 탐색의 target을 바위 간에 거리로 잡아야 하는데, 바위를 제거를 어떤 식으로 구현해야 할지 감이 잡히지 않아서 매우 고생했던 문제였다.. 1. 입력받은 돌섬(rocks)들의 거리를 오름차순 정렬을 하고, 주어진 거리도 rocks에 appen..

25240번: 가희와 파일 탐색기 2 Q개의 질문에 대해, 연산이 성공하면 1을 실패하면 0을 출력해 주세요. 각 질문에 대한 답은 한 줄에 하나씩 출력해 주세요. www.acmicpc.net 풀이 과정 이 문제는 정말 맞왜틀을 외치면서 풀었던 문제인 거 같다... 7번이나 틀렸던 문제😂😂 문제를 제대로 읽지 않아서 중요한 부분을 놓쳤다. " 유저가 속한 그룹들에 대한 정보에 USER_NAME이 주어지지 않더라도 그룹 이름이 USER_NAME인 그룹에 속함에 주의하세요." 유저에 대한 정보의 개수 U만큼 user_name과 user_group이 입력되는데, user_name이 동일한 이름을 가진 그룹에 속하다는 것을 놓쳐버렸다.. 🤦‍♂️🤦‍♂️ 1. 필자는 그룹에 어떤 유저가 포함되어 있는지, 그룹 이..

2539번: 모자이크 수찬이는 선생님을 도와서 교실 벽면을 장식할 모자이크 그림을 그리기로 하였다. 이를 위하여 직사각형 모양의 큰 도화지를 준비하여 교실 벽에 붙이고 1cm 간격으로 가로선과 세로선을 그려서 www.acmicpc.net 풀이 과정 이분 탐색의 팁은 주체를 찾고 해당 주체를 target으로 잡아서 이분 탐색을 해주면 된다. 하지만 해당 문제를 3번이나 틀렸다.😂 1. 첫째줄부터 셋째 줄까지 입력을 받고 잘못 칠해진 칸(y, x) 값을 입력받을 때 높이(y)의 max 값을 left에 저장해줘야 한다... 해당 작업을 하지 않고 정형적인 이분 탐색의 left 값을 0으로 해놓아서 9%에서 바로 틀려버렸다 ㅠ 색종이는 밑변에 맞춰서 붙이기 때문에 최소한 가장 높은 높이의 색종이 칸을 가지고 있..

6137번: 문자열 생성 첫 번째 줄에 문자열 S의 길이 N이 주어진다. (N

11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 풀이 과정 그래프 문제에서 노드간에 걸리는 시간이 음수가 포함했다? -> 벨만 포드 음수 간선에 관하여 최단 경로 문제는 다음과 같이 분류할 수 있다. 1. 모든 간선이 양수인 경우 2. 음수 간선이 있는 경우 2-1) 음수 간선 순환은 없는 경우 2-2) 음수 간선 순환이 있는 경우 벨만 포드 최단 경로 알고리즘은 음의 간선이 포함된 상황에서도 사용할 수 있다. 또한 음수 간선의 감지할 수 있으며, 벨..