알고리즘,PS

https://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 문제 풀이 (1,1) 집에서 (m,n)학교 까지 가는데 최단거리로 가는 경우의 수를 구하는 문제이다. 우선 , 문제의 조건으로 오른쪽or아래 만 진행한다고 하였으니 어디로 가든 최단거리는 기본으로 잡고 들어간다. 만약 현지위치를 (x,y) 라고 하면 이 위치에 오기 까지의 경우의수는 (x-1,y) 또는 (x,y-1)의 합이다. 즉 , 현재위치의 경우의..

https://www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 문제 풀이 이전에 풀었던 컵라면 문제와 동일하다. https://katastrophe.tistory.com/73 1. 기간순으로 오름차순 정렬된 우선순위 큐(q1)에 삽입 2. 페이 순으로 오름차순 정렬된 우선순위 큐(q2)에 삽입 2_1. 삽입한 원소의 기간보다 q2의 사이즈가 더 크면 큐의 맨 앞의 원소를 poll. ( 더 적은 페이를 제거 ) 3. q2를 ..

https://www.acmicpc.net/problem/3977 3977번: 축구 전술 World Soccer Championship이 다가오고 있다! 천재적인 전술을 창조하는 플랜 아티스트 감독 도현이는 자신의 팀이 승리하도록 만반의 준비를 가하고 있다. 도현이의 전략은 경기장을 여러 개의 구역 www.acmicpc.net 문제 풀이 이동 구간 경로가 주어 졌을 때 , 어느쪽을 스타트로 잡아야 하는지 정하는 문제다. 첫 번째 입력을 그래프로 나타내면 다음과 같은데 만약 3번에서 시작한다고 하면 주어진 경로를 모두 탐색할 수 없기 때문에 불가능. 그럼 나머지 0,1,2 번 지점에서는 저 중 아무곳에서 출발을 해도 모든 구간을 탐색이 가능하기 때문에 0,1,2 가 답. 즉 , { 0, 1, 2 } 를 하..

https://www.acmicpc.net/problem/4013 4013번: ATM 첫째 줄에 교차로의 수와 도로의 수를 나타내는 2개의 정수 N과 M(N, M ≤ 500,000)이 차례로 주어진다. 교차로는 1부터 N까지 번호로 표시된다. 그 다음 M개의 줄에는 각 줄마다 각 도로의 시작 교차 www.acmicpc.net [문제] [풀이] 어우 .. 어질어질하다.. SCC 활용 DP 문제이긴 한데 , 처음에 SCC 집단들을 구해서 indegree가 0인거부터 진행했는데 왜 안되지..? 했다가 나중에 알고보니 start 지점이 정해져있다는 걸 뒤늦게 알았고 한참을 헤맸다 .. 접근방법 1. SCC집단을 구할 것. 2. SCC집단마다 번호를 매기고 , 이 자체를 하나의 Node로 취급하여 또 다른 tot..

https://www.acmicpc.net/problem/4196 4196번: 도미노 도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러 www.acmicpc.net [문제] [풀이] x => y => ... 로 가는 간선이 있을 때 , x 를 넘어뜨리면 이와 연결된 모든 도미노가 넘어간다. 즉 , inDegree 가 0인 부분을 선택해서 카운팅 해줘야 하는 문제이다. 그런데 만약 사이클이 있는 경우는 inDegree를 정의하기가 어렵기 때문에 사이클이 있는부분은 어느 하나만 건드리면 나머지도 다 넘어지기 때문에 이 사이클을 하나의 노드로 봐야 한다. 그래서 SCC (강한 결..

https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net [문제] [풀이] 다익스트라 응용해서 풀었다. 1. 최단거리 알고리즘인 다익스트라의 조건을 최장거리로 변형시켜서 distance 설정 2. 도착지에서 distance[cur]-cost = distance[next] 의 조건을 만족하는 노드를 찾아가며 역추적 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2..

https://programmers.co.kr/learn/courses/30/lessons/81302#fnref1 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr [풀이] 2차원 map을 만들어서 P 와 P 사이의 거리가 2이하인 것을 발견..

https://programmers.co.kr/learn/courses/30/lessons/72412