🛵꾸준한 꿈틀꿈틀

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 이해 풀이에 앞서 문제를 이해해보자 토마토의 익은 상태가 1초마다 1칸씩 전이되는 상황이고 전체 토마토에 전이되는데 걸리는 최소 시간을 출력해야한다 결국 탐색을 진행해야하고, 각 좌표에 최소 시간을 기록해야하므로 BFS를 이용해야한다 BFS를 진행하며 cost를 기록하고 탐색 종료 후에 cost 중 가장 큰 값을 출력하면 된다 풀이 여기서 방문처리는 익은 토마토 여부로 한다 = 1..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 이해 해당 문제는 2차원 배열로 주어지는 map을 탐색하여 연결된 지역을 찾는 문제이다. 즉 map을 순회하며 방문처리되지 않은 좌표가 있다면 해당 좌표를 기준으로 인접한 좌표를 모두 방문처리한다. 이렇게하면 연결된 지역은 모두 방문처리될 것이고 map을 순회 중에 방문되지 않은 좌표를 찾는다면 새로운 지역의 발견을 의미한다. 따라서 map을 순회하며 방문되지 않은 좌표를 찾을 시 해당 좌표를 시작..

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 이해 문제 풀이에 앞서 문제를 이해해보자. 연결 요소(Connected Component)는 연결된 정점의 집합을 의미한다. 다음 이미지에서의 연결 요소는 4개이다. 따라서 해당 문제는 그래프 탐색을 통해 연결된 정점을 모두 방문처리하고 방문처리 되지 않은 정점이 발견되면 새로운 연결 요소임을 의미한다. 풀이 전체 노드(1~N)를 순회..

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 풀이 "연결 정보가 주어진 N명의 학생 줄 세우기"는 다음과 같이 해석할 수 있다. => 연결 정보가 주어진 순환하지 않는 방향성 그래프(DAG=방향성 비순환 그래프)에서 각 노드를 줄 세우시오. 이를 구하는 방법은 위상정렬 알고리즘과 일치하므로 위상정렬 알고리즘을 이용해 풀이한다. 여기서는 각 노드의 연결 당한 정보를 linked 배열에 미리 입력 후 ..

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 이 글은 이분탐색을 이미 알고있는 사람을 대상으로 작성한다. 이분탐색을 이용해 최적의 값을 찾아낸다. 이분탐색 문제에서는 구해야하는 값을 찾고 해당 값을 기준으로 풀이한다. 보통 정답을 요구하는 값과 일치한다. 해당 문제에서는 K(절단기에 설정할 높이의 최댓값)이 기준 값이다. 따라서 변화하는 K를 기준으로 totalSlicedHeight(잘려진 나무 길이의..

#2 에서는 유용한 키워드들을 정리하면서 문제도 몇 개 정리할 생각입니다. - 집계함수(SUM, MAX, MIN, COUNT, AVG) 집계함수는 최댓값 혹은 최솟값 구하기, 개수 세기 그리고 평균 구하기 등에 이용될 수 있습니다. ❗#1에서 정리한 GROUP BY는 집계함수와 사용하면 유용하니 꼭 알아둡시다. 이에 관련된 예제는 뒤에 GROUP BY 문제와 함께 알아봅니다. - 중복 제거 하기(DISTINCT) DISINCT 키워드를 사용해서 중복을 제거할 수 있습니다. ❗추가로 집계함수와 조합하여 COUNT(DISTINCT NAME) 이런 방식도 가능합니다. NAME의 중복값을 미리 제거하고 COUNT하는 것이죠. -- NAME SELECT 중복 제거 SELECT DISTINCT NAME FROM M..

#1에서는 핵심적인 키워드를 정리하고 #2에서는 프로그래머스 SQL 고득점 kit Level 3~4 문제 몇개를 다루면서 자주 사용하는 함수들을 정리해보려고 한다. 간단하게 키워드들을 정리하고 마지막에 이들을 적합하게 사용하는 법을 정리할 것이다. ORDER BY SELECT * FROM 테이블명 ORDER BY 컬럼명 (ASC) 특정 컬럼을 기준으로 정렬. 기본값은 오름차순(ASC) 정렬 SELECT * FROM 테이블명 ORDER BY 칼럼1, 칼럼2 DESC 위 방식처럼 여러 칼럼에 적용할 수도 있다. GROUP BY, HAVING SELECT id, COUNT(*) FROM member GROUP BY id HAVING id > 3 특정 칼럼을 기준으로 그룹화한다. 주로 집계함수(COUNT(), ..