CodeClover

https://www.acmicpc.net/problem/2828📌 문제 탐색하기N칸으로 구성된 스크린이 있고 바구니는 M칸을 차지하고 처음에는 스크린의 가장 왼쪽에 위치한다. 사과가 한번에 하나씩 J번 떨어진다면 모든 사과를 바구니에 담기위한 바구니를 움직인 거리의 최솟값을 구하는 문제이다. 이때 조건은 사과는 바닥에 도달할때 바구니가 해당 칸을 덮고 있어야 하고 바구니는 스크린의 범위를 벗어나면 안된다.📌 가능한 시간복잡도사과의 최대 개수는 20개, 사과마다 위치 비교하고 이동 거리를 계산하는데 필요한 시간 복잡도는 O(N)이다.따라서 가능한 시간복잡도는 O(N) 입니다.📌 코드 설계하기바구니의 지금 현재 범위를 유지하면서 떨어지는 사과가 바구니 안에 있으면 이동하지 않는다. 바구니 범위 바깥이..

https://www.acmicpc.net/problem/2810📌 문제 탐색하기혼자 앉는 일반좌석 S두 좌석이 하나의 팔걸이는 공유하는 LL 커플석커플석 LL의 경우 두 사람이 하나의 컵홀더를 공유하기 때문에 L 두개당 컵홀더 하나만 추가된다.좌석의 수, 정보의 입력값을 보고 해당 좌석들에서 이용 가능한 총 컵홀더의 개수를 출력하는 문제이다.📌 가능한 시간복잡도입력받은 좌석의 개수 N의 문자열 길이를 한번 순회하면서 일반좌석과 커플좌석을 구분하고 커프좌석이 나타나면 인덱스를 한번 더 넘기는 방식으로 진행한다. 각각 문자를 한번씩 확인하기 때문에 O(N) 이라고 생각함.따라서 가능한 시간복잡도는 O(N)입니다. 📌 코드 설계하기일반좌석은 좌우에 컵홀더가 하나씩 있고, 커플석은 두 좌석에 하나..

https://www.acmicpc.net/problem/14916📌 문제 탐색하기n원을 2원짜리와 5원짜리 동전으로 동전 개수를 최소로 거슬러주는 문제이다.거슬러 줄 수 없는 경우 -1을 출력해야한다. 📌 가능한 시간복잡도입력받은 n의 값이 홀수이거나 5이하로 나누어 떨어지는 수가 아니면 2원짜리 동전을 사용해서 n을 주여야함. 매번 반복문에서 n의 값이 2씩 감소하기때문에 최대 반복 횟수는 n/2이다. 큰 동전을 사용할 수 없는 경우 2원짜리 동전을 계속 사용해야함. 따라서 가능한 시간복잡도 O(N)이다. 📌 코드 설계하기그리디 알고리즘 적용큰 동전을 최대한 많이 사용하고 큰 동전 사용이 더 이상 불가능한 경우 2원 동전을 하나씩 추가하면서 가능한 조합을 찾는다.📌 정답 코드import jav..

https://www.acmicpc.net/problem/2606📌 문제 탐색하기 컴퓨터 번호 1번 부터 시작 -> 1번 컴퓨터부터 시작해서 몇대의 컴퓨터가 감염되는지 찾아서 출력하는 문제이다. 📌 가능한 시간복잡도입력받은 컴퓨터의 수 N대, 네트워크 상에 직접 연결되어 잇는 컴퓨터 쌍의 수 M이므로 BFS를 활용해서 가능한 시간복잡도는 O(N+M)입니다. 📌 코드 설계하기BFS 활용정점 : 컴퓨터(컴퓨터 번호는 1부터 시작) / 간선 : 네트워크 연결으로 설정해서 감염된 컴퓨터 수는 1번 컴퓨터를 제외하고 COUNT한다. 📌 정답 코드import java.io.*;import java.util.*;public class Main { public static int bfs(List> g..

https://www.acmicpc.net/problem/1260📌 문제 탐색하기DFS, BFS 문제로 ,,, 그래프 탐색 문제 입니다. 방문된 점을 출력하라고 했으니 순서가 중요한 문제입니다. 📌 가능한 시간복잡도가능한 시간복잡도는 입력받은 정점의 개수 N ,간선의 개수 M으로 ...정점과 간선을 한번씩 탐색해서 BFS , DFS 모두 동일하게 O(N+M) ,리스트에 간선 정보를 넣고 정렬해야하니까 O(M logM)따라서 가능한 시간복잡도는 모두 더한값 O(N+M) + O(M logM) 입니다. 📌 코드 설계하기그래프는 List> 으로 인접 리스트를 사용하고 DFS는 스택 ,BFS는 큐를 사용해서 구현하면 된다. 📌 정답 코드import java.io.*;import java.util.*;..

https://www.acmicpc.net/problem/10816📌 문제 탐색하기상근이가 가지고 있는 숫자카드의 개수 N , N개의 카드들 , 정수 M , M개의 카드들이 입력된 값에서 각각 입력된 M개의 정수들이 N개의 숫자카드에 있는 숫자만큼 출력하는 문제이다. https://www.acmicpc.net/problem/10815 이 문제의 응용버전...  ! 📌 가능한 시간복잡도N개의 숫자 저장 하고 조회하는 과정에서 O(N) , O(M) 만큼의 시간복잡도 .... 따라서 가능한 시간복잡도는 O(N) + O(M) 입니다. 📌 코드 설계하기시간복잡도를 잘 생각해서 풀어야하는 문제이다. 조건에 보면 50만개의 숫자에 대해서 체크해야하는 문제이므로 단순한 반복으로 해결 가능 . 우선, 상근이가 가지..