공부공간

https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 가수의 수가 나오고, 그 뒤로는 그 가수들의 순서가 나온다. N은 1이상 1,000이하의 정수이고, M은 1이상 100이하의 정수이다. www.acmicpc.net 음악프로그램에 N명의 참가자가 일부 순서가 정해져있을때에 서로다른 M가지의 일부순서를 만족하는 하나의 전체순서를 구하는 전형적인 위상정렬문제이다. 만약 그래프에 사이클이 생겼을때에는 전체 N을 방문하지 않고 끝나므로, Indegree배열에 0이..

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다. 학생들의 번호는 1번부터 N번이다. www.acmicpc.net 위상 정렬 ( Topology Sort )는 그래프의 진입 차수를 기준으로 다음 올 그래프의 순서를 정하는 정렬알고리즘이다. 먼저 위상 정렬의 순서는 다음과 같다. 1. 그래프에서 진입차수가 0인 노드들을 큐에 넣는다. 2. 큐에서 하나씩 poll 하면서, 그 노드와 연결된 그래프들의 진입차수를 -1해준다 ( 큐에서 poll ..

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a www.acmicpc.net 합집합의 연산을 반복하면서, 특정 두 원소가 같은 집합에 속해있는지를 묻는 문제이다. 이 문제는 "너 서로소집합 메소드 구현할줄알아?..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동 www.acmicpc.net 예전에 못풀어서 끙끙앓던 문제였는데 다시 생각해보니 쉬웠다. 큐에 들어가는 노드에 벽을 부수었는지? 만 체크하면 된다고 생각했..

https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 문제 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서 www.acmicpc.net 3차원 BFS를 통해서 S에서 시작하여 E까지 도달하는 문제이다. 한 칸움직이는 사이에 1분이 소요되므로 일반적인 BFS를 돌려주면 된..

https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a, b, c가 주어지는데, a가 1인 경우 b번째 수를 c로 바꾸고 a가 2인 경우에는 b번째 수부터 c번째 수까지의 www.acmicpc.net 연속 합을 구하는 문제에서 Segment Tree 와 Fenwick Tree를 자주 사용하는데, Segment Tree로 위 문제..

코로나가 기승을 부리고있다.. 사실 무엇보다도 예방하는게 가장 중요하다.. 마스크를 확보하는것이 중요하지만, 사실상 어느약국에 얼만큼 마스크가 남아있는지 알수가 없다. 공공데이터 api를 이용해서 주소를 기반으로 내주변 약국에 마스크가 있는지? 없는지? 얼마나있는지? 알려주는 기능을 한번 개발해보았다. ( 마크스 5부제를 통해서 출발하기전에 확인하면 좋을것같다 ) 예전에 음성합성프로젝트를 같이한 https://somjang.tistory.com/ 솜씨좋은장씨 somjang.tistory.com 이 folium이라는 좋은 파이썬 라이브러리를 소개시켜줬고, 한번 써볼겸 + 요즘 알고리즘만 하다보니 이런 문제정의와 구현하는데 어색해지기때문에.. 구현시간은 30분정도 걸렸다. Code 개발환경 : google ..

악마의 손아귀 스킬을 피해 목적지까지 갈 수 있는지 여부를 체크해주는 문제이다. 덱을 사용하여 처음 입력에 악마의 손아귀를 먼저 처리해주고 이동하는 S는 항상 한개이기 때문에 큐 내에서 같은 시간에 처리된다. https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWsBQpPqMNMDFARG SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.u..