분류 전체보기

https://www.acmicpc.net/problem/9095 난이도 : S3Tag : DP풀이 일자 : 2025-03-07문제 탐색하기T : 테스트 케이스 수n : 1,2,3의 합으로 나타낼 수 (1  이 문제는 정수 n을 1, 2, 3의 합으로 나타내는 모든 경우의 수를 구하는 문제입니다. 즉, 주어진 숫자 n을 만들 수 있는 서로 다른 합의 방법을 찾는 것이 핵심입니다. 예를 들어, n = 4일 때 가능한 조합은 다음과 같습니다.1+1+1+11+1+21+2+12+1+12+21+33+1가능한 시간복잡도이 문제는 n 이를 일반화하여 n이 커질 때의 시간복잡도를 고려하면 완전 탐색O(3^n)은 비효율적입니다.예를 들어, n=20이면 경우의 수가 121415개이고,  O(3^20) ≈ 35억 번의 연산..

https://www.acmicpc.net/problem/10026 난이도 : G5Tag : BFS/DFS풀이 일자 : 2025-03-06문제 탐색하기RRRBBGGBBBBBBRRBBRRRRRRRR N: 그리드의 한 변의 길이 (1 그리드의 각 칸은 R(빨강),G(초록),B(파랑)중 하나로 색칠되어 있다.적록색약인 사람은 빨간색과 초록색을 구분하지 못한다.위 그림을 예시로 들면 정상인은 4개의 구역을, 적록색약은 3개의 구역을 보게 된다.즉 이 문제는 탐색 알고리즘(DFS/BFS)을 사용하여 각 격자를 탐색 후 색깔별로 정상인이 보는 구역의 개수와 적록색약이 보는 구역의 개수를 계산하는 게 핵심입니다. 가능한 시간복잡도먼저 각 구역을 하나하나 탐색해야 하므로 최대 O(100*100) = O(10,000)의..

https://www.acmicpc.net/problem/27737 난이도 : S1Tag : BFS/DFS풀이 일자 : 2025-03-05문제 탐색하기N: 정사각형 버섯농장 한 변의 나무판 길이 (1 M: 버섯 포자 개수 (0 K: 하나의 버섯포자가 자라게 할 수 있는 최대 버섯 수 (상, 하, 좌, 우) (1  0 : 버섯이 자랄 수 있는 칸1 : 버섯이 자랄 수 없는 칸 조건 :한 칸에 여러 개의 버섯 포자를 겹쳐 심을 수 있다.이때 자랄 수 있는 최대 버섯 수는 x * K농사가 가능한 조건 : 버섯 포자를 하나라도 사용해야 합니다.버섯이 자랄 수 있는 모든 칸에 버섯이 전부 자라야 합니다.즉, 버섯이 자랄 수 있는 땅을 모두 덮을 수 있는 최소 포자 개수를 구하고, 남은 포자의 개수를 출력하는 것이..

https://www.acmicpc.net/problem/4963 난이도 : S2Tag : BFS/DFS풀이 일자 : 2025-03-04문제 탐색하기w: 지도의 너비 (1 h: 지도의 높이 (1 00: 종료  땅은 "1"바다는 "0" 이때 같은 섬의 기준은 "가로", "세로", "대각선"으로 연결되어 있어야 합니다.즉, 지도가 주어졌을 때 위 조건을 만족하는 서로 다른 모든 섬의 개수를 세는것이 문제의 핵심입니다.가능한 시간복잡도지도의 가로 세로 최대 높이가 50이므로 각 위치를 한 번씩은 무조건 탐색해야 합니다. 그 위치에 존재하는게 섬인지 바다인지 알아야 하니까요. 즉, 모든 위치를 방문해야 하므로 기본적으로 O(w × h)의 시간이 걸립니다.그리고 섬을 찾으면 DFS를 통해 연결된 모든 칸을 방문해..

https://www.acmicpc.net/problem/1326난이도 : S2Tag : BFS/DFS풀이 일자 : 2025-03-03문제 탐색하기N : 징검다리의 개수N개의 수: 각 징검다리에 쓰여있는 값 (배수의 위치로만 점프)a : 출발하는 a번째 징검다리b : 도착하는 b번째 징검다리  각 징검다리에 쓰여 있는 수의 배수만큼 떨어져 있는 곳으로만 이동하여,a번 징검다리에서 출발하여 최소한의 점프 횟수로 b번 징검다리까지 가는 게 핵심입니다.N은 최대 10,000개고 a,b는 N보다 작거나 같습니다.또한, 징검다리에 쓰여있는 정수는 10,000보다 작거나 같은 자연수입니다.이때, a에서 b로 갈 수 없다면 -1을 출력합니다.가능한 시간복잡도개구리가 현재위치에서 징검다리마다 점프할 수 있는 모든 경우..

https://school.programmers.co.kr/learn/courses/30/lessons/42626# 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 이를 위해 아래와 같은 규칙으로 두 음식을 섞습니다:새로운 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 × 2)모든 음식의 스코빌 지수가 K 이상이 될 때까지 섞어야 하며, 최소 몇 번 섞어야 하는지를 구해야 합니다.풀이 방법우선순위 큐를 사용하면 쉽게 풀 수 있습니다.우선순위 큐의 값은 내림차순으로 정렬되기에 입력받..

https://school.programmers.co.kr/learn/courses/30/lessons/12915 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다.예를 들어 strings가 ["sun", "bed", "car"]이고 n이 1이면 각 단어의 인덱스 1의 문자 "u", "e", "a"로 strings를 정렬해주세요. 풀이 방법sort() 함수에 사용자 정의 정렬 기준을 적용하면 문제를 쉽게 해결할 수 있습니다.n번째 위치의 알파벳을 기준으로 문자열을 오름차순 ..

https://school.programmers.co.kr/learn/courses/30/lessons/43163# 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 주어진 단어 begin에서 target으로 변환하는 가장 짧은 과정을 찾는 문제입니다. 변환 과정에서는 다음 규칙을 따라야 합니다:한 번에 한 개의 알파벳만 변경할 수 있습니다.변경된 단어는 반드시 주어진 단어 목록(words)에 포함되어 있어야 합니다.문제 조건모든 단어는 소문자 알파벳으로 이루어져 있으며, 길이는 동일합니다.변환 과정에서 target 단어로 변환할 수 없으면 0을 반환합니다. 풀이 방법이 문제는 BFS로 풀 수 있습니다.B..