링크https://www.acmicpc.net/problem/1010 문제 요약각 테스트 케이스에 대해 다리를 지을 수 있는 경우의 수 출력하기 강의 서쪽에는 N개, 동쪽에는 M개의 사이트가 있다.다리끼리 서로 겹칠 수 없다.서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 제한입력의 첫 줄에는 테스트 케이스의 개수 T가 주어짐그다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M 이 주어짐0  풀이보시면 시간제한이 0.5초로 매우 짧습니다. 그렇기 때문에 모든 경우를 탐색하며 문제를 풀면 안 됩니다. N개의 사이트를 기준으로 다리를 짓기 때문에 N 값이 동일할 때 예제를 살펴보겠습니다.`[N=2일 때]`M=2: 1M=3: 3M=4: 6M=5: 10M=6: 1..

링크https://www.acmicpc.net/problem/13023 문제 요약0번~N-1번 사람 중 아래와 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구하기A는 B와 친구다.B는 C와 친구다.C는 D와 친구다.D는 E와 친구다. 제한첫째 줄에 사람의 수 N, 친구 관계의 수 M5 ≤ N ≤ 20001 ≤ M ≤ 2000둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다.0 ≤ a, b ≤ N-1, a ≠ b같은 친구 관계가 두 번 이상 주어지는 경우는 X문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. 풀이경로의 특징을 저장해야하는 문제로, DFS로 문제를 풀어야 합니다.모든 정점에 대해 dfs를 수행한다.시작점은 ..

링크https://www.acmicpc.net/problem/2178 문제 요약미로 배열이 주어졌을 때, (1,1)에서 출발하여 (N, M)으로 이동할 때 지나야 하는 최소의 칸 수 구하기1은 이동할 수 있는 칸, 0은 이동할 수 없는 칸을 의미한다. 제한첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다.다음 N개의 줄에는 M개의 정수로 미로가 주어진다.각각의 수들은 붙어서 입력으로 주어진다. 풀이문제에서 (1,1)이라고 주어졌는데, 이는 배열에서 (0,0)값을 의미합니다.따라서 왼쪽 맨 위에서 오른쪽 맨 아래로 이동하는 것이 목표입니다. [입력]평소와 다르게 각각의 수들이 붙어서 주어집니다. 그래서 StringTokenizer를 사용할 수 없습니다.가장 쉽게 떠올릴 수 있는 입력 방법..

링크https://www.acmicpc.net/problem/1931 문제 요약회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수 구하기 제한첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다.둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다.시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다. 풀이회의의 수가 최대 10^6이므로 시간 복잡도가 `O(N log N)`을 넘으면 안 됩니다. 회의를 최대한 많이 선택하려면 어떤 기준으로 풀어야 할까요?핵심은 회의 종료 시간이 빠를수록 선택할 수 있는 회의가 많아진다입니다.끝나는 시간을 기준으로 오름차순으로 정렬한다.끝나는 시간이 같다..

링크https://www.acmicpc.net/problem/2573 문제 요약N*M 크기 배열의 각 칸에는 빙산 또는 바다(0)가 있다.각 빙산 칸에는 빙산의 높이 정보가 주어진다.동서남북으로 붙어있는 칸들은 서로 연결되어 있는 한 덩어리로 취급한다.빙산의 높이는 일 년마다 동서남북 네 방향으로 바다가 접해있는 개수만큼 줄어든다. 처음에 한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년) 구하기 제한첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다.N과 M은 3 이상 300 이하이다.그다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈칸을 사이에 두고 주어진다.각 칸에 ..

링크https://www.acmicpc.net/problem/4963 문제 요약h*w 사각형 지도에 섬 또는 바다가 표시되어 있을 때 섬의 개수를 반환하기이때 가로, 세로, 대각선으로 연결되어 있는 섬은 같은 섬이다. 제한입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다.w와 h는 50보다 작거나 같은 양의 정수이다.둘째 줄부터 h개 줄에는 지도가 주어진다.1은 땅, 0은 바다이다.입력의 마지막 줄에는 0이 두 개 주어진다.w와 h는 50보다 작거나 같은 양의 정수이다. 풀이가로, 세로, 대각선으로 연결되어 있지 않은 1의 개수를 세는 문제입니다. 즉, 영역의 개수를 구하는 문제이므로 DFS 또는 BFS로 풀 수 있습니다.저는 DFS로..

링크https://school.programmers.co.kr/learn/courses/30/lessons/64061 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 요약N*N `board`에 여러 모양의 인형(1*1)이 쌓여있는 상태이고, 크레인은 각 줄의 가장 위에 있는 인형을 집어 올린다.그리고 집어 올린 인형을 한 줄 바구니에 쌓아 올릴 때, 같은 모양의 인형이 연속해서 쌓이면 이 두 인형은 없어진다. 2차원 배열 `board`와 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열 `moves`가 매개변수로 주어질 때, 크레인을 모두 작동시킨 후 사라진 인형의 개수를 반환하기제한`board..

링크https://school.programmers.co.kr/learn/courses/30/lessons/42584 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 요약초 단위 주식가격 배열 prices에 대해 가격이 떨어지지 않은 기간은 몇 초인지 반환하기예: [1,2,3,2,3] → [4,3,1,1,0] 제한prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.prices의 길이는 2 이상 100,000 이하입니다. 풀이prices의 길이가 최대 10^6이므로 시간 복잡도는 `O(N)` 이어야 합니다.따라서 i초 시점 주식 가격이 언제 떨어지는지 그 뒤를 매번 확인한다면, `O(N..