Baekjoon

❓문제https://www.acmicpc.net/problem/18870성능 요약메모리: 149248 KB, 시간: 1824 ms분류값 / 좌표 압축, 정렬 문제 설명수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.✍🏻풀이문제를 읽어보면 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수가 Xi'과 같다고 한다. 정말 단순하게 생각하면 이중반복문으로 풀 수 있다. 그러나 이 경우 시간 복잡도가 최악의 경우 O(N²)으로 N이 최대 1,000,..

❓문제https://www.acmicpc.net/problem/1012성능 요약메모리: 114308 KB, 시간: 132 ms분류그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 문제 설명차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에..

❓문제https://www.acmicpc.net/problem/2667성능 요약메모리: 108548 KB, 시간: 92 ms분류너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색 문제 설명과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.✍🏻풀이각 단지에 속하는 집의 수..

❓문제https://www.acmicpc.net/problem/24480성능 요약메모리: 70312 KB, 시간: 540 ms분류깊이 우선 탐색, 그래프 이론, 그래프 탐색, 정렬문제 설명오늘도 서준이는 깊이 우선 탐색(DFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 깊이 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.깊이 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 내림차순으로 방문한다.dfs(V, E, R) { # V : 정점 집합, E : 간선 ..

❓문제성능 요약메모리: 136204 KB, 시간: 380 ms분류다익스트라, 그래프 이론, 최단 경로 문제 설명방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.✍🏻풀이최단 경로를 구하기 위해 인접행렬과 인접리스트를 사용할 수 있지만 인접 행렬을 사용하는 경우, 시간 복잡도가 O(V²)이 됩니다. 그러나 인접 리스트를 사용하는 경우 시간 복잡도가 O(E * logV)이 되므로 인접 리스트를 사용해서 풀겠습니다. 그리고 다익스트라는 Heap을 사용하는 것이 빠릅니다.heapq를 사용하기 위해 pq를 생성해 (가중치, 시작 정점) 쌍으로 힙큐에 넣어준다. 그리고 dist는 각 정점의 최단 거리 테이블을 ..

❓문제성능 요약메모리: 32412 KB, 시간: 40 ms분류그리디 알고리즘, 정렬문제 설명항승이는 품질이 심각하게 나쁜 수도 파이프 회사의 수리공이다. 항승이는 세준 지하철 공사에서 물이 샌다는 소식을 듣고 수리를 하러 갔다.파이프에서 물이 새는 곳은 신기하게도 가장 왼쪽에서 정수만큼 떨어진 거리만 물이 샌다.항승이는 길이가 L인 테이프를 무한개 가지고 있다.항승이는 테이프를 이용해서 물을 막으려고 한다. 항승이는 항상 물을 막을 때, 적어도 그 위치의 좌우 0.5만큼 간격을 줘야 물이 다시는 안 샌다고 생각한다.물이 새는 곳의 위치와, 항승이가 가지고 있는 테이프의 길이 L이 주어졌을 때, 항승이가 필요한 테이프의 최소 개수를 구하는 프로그램을 작성하시오. 테이프를 자를 수 없고, 테이프를 겹쳐서 붙..