유미의 기록들

📌 문제  📝풀이과정인구이동이 없을 때까지 모든 좌표를 DFS로 탐색하면서  while문으로 반복하였고, 인구인동이 없으면 break문으로 종료하도록 코드를 구현하였다 - 두 나라의 인구 차이 L이상 R이하 일 때 탐색한다- ArrayList를 사용하여 방문한 좌표값을 저장한다- DFS 탐색이 끝난 후, (ArrayList의 합)/ (ArrayList의 사이즈) 를 각 칸의 인구수로 만든다- 인구 이동이 없으면 break문으로 종료함while(){ for(int i=0;i 💻코드import java.util.Scanner;import java.io.*;import java.util.*;public class Main{ static int n,l,r; static int map[][]; static..

완전탐색 (Brute Force) 모든 경우의 수를 탐색하는 알고리즘 '노가다'라고 흔히 비유되는 이 방법은, 주어진 문제의 모든 가능성을 탐색하여 정답을 찾아내는 알고리즘 접근방식이다 흔히 사용하는 DFS, BFS도 완전탐색에 해당한다 ⚠️ 고려사항 완전탐색을 사용할 때 주의할 점은, 처리해야 할 데이터의 양이 너무 많지 않아야 한다. 보통 시간 복잡도 1억 미만으로 볼 수 있다. 📌 구현 방법 1) for / while를 이용 2) 재귀함수 이용 재귀함수를 활용하면 복잡하고 비용이 들기 때문에 반복문으로 해결이 가능하다면 가능한, 반복문으로 구현하는 것이 좋다 단, 매개변수의 수정만 필요한 반복적인 행위가 요구된다면, 재귀함수를 이용하는 것이 더 적합하다 - 조합이나 순열 - DFS, BFS 알고리즘..

📌 문제  📝문제 풀이 1) 전체가 0과 1 중 하나의 값으로만 이루어져 있는 지 확인2) 하나의 값으로 일치 하지 않는다면 4등분하기 (왼쪽 위 / 오른쪽 위 / 왼쪽 아래 / 오른쪽 아래)3) 모두 0이거나 모두 1일 때 값으로 표현하기 위 과정을 계속 반복하기 때문에 재귀함수를 활용하여 표현할 수 있다 여기서는 파라미터로 전체 사이즈, 시작 좌표 (y,x)를 넘겨야 한다 사이즈의 영역이 계속해서 4등분이 되기 때문에 분할정복 알고리즘을 사용하는 문제이다 재귀함수함수에서 자신의 로직을 다시 호출해 작업을 수행하는 방식 분할정복(Divide and Conquer)문제를 나눌 수 없을 때 까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘   💻코드import java.util.*..

그래프를 탐색하는 방법에는 깊이우선탐색(DFS)과 너비우선탐색(BFS)가 있다 그래프를 탐색하는 것은 하나의 정점으로 시작해서 모든 정점을 한 번씩 방문하는 것, 즉 방문한 정점은 다시 방문하지 않는다 깊이 우선 탐색 (DFS, Depth First Serch) DFS는 어떤 정점부터 시작해서 다음 분기(branch)로 넘어가기 전에 각 분기마다 가능한 가장 멀리 있는 정점까지 탐색하는 알고리즘 - 모든 정점을 방문하고자 하는 경우에 많이 사용한다 - 스택 또는 재귀함수로 구현한다 너비 우선 탐색 (BFS, Breadth First Search) BFS는 어떤 정점부터 시작해서 다음 깊이의 정점로 이동하기 전에 현재 깊이의 모든 정점을 탐색하는 알고리즘 즉, 레벨 별로 탐색한다는 의미이다 - 최단 거리를..

📌문제   📝풀이과정 1, 11 ,111, 1111....계속 증가 하도록 하고 입력받은 n의 수와 나누어 떨어지면 자리수를 출력하도록 했다import java.util.*;import java.io.*;public class Main{ public static void main(String[]args)throws IOException{ BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); String input; int n; long oneNumber,cnt; while((input=br.readLine())!=null){ n=Integer.parseInt(input); oneNumber=1;cnt=1; ..

📌문제  📝 풀이과정단순히 for문을 이용해서 A를 B번 곱한 다음, 나머지를 출력하면 될까?문제를 볼 때 가장 먼저 입력의 최대, 최소 범위를 봐야 한다여기서 최대 범위는 20억인데, for문으로 A를 B번 곱하게 되면 즉 시간 복잡도는 20억이 된다 그렇다면 어떻게 접근해야 할까?'모듈러 연산'과 '지수법칙'으로 접근하면 된다 모듈러 연산 모듈러 식을 연산자를 이용하여 표현해보면  → 문제에서 최대범위로 계산 했을 때 A(20억)을 B(20억) 번 계산해야 한다 그렇게 되면 long long의 범위를 벗어나고 오버플로가 발생하게 된다 따라서 A를 C로 나누면서 곱하는 식으로 계산해야 한다    지수법칙 2를 8번 곱하면 연산 횟수가 많다따라서 지수법칙에 따라 2^4를 하나의 변수 K에 넣고  K ..

📌 문제   💻 나의 코드import java.util.*;import java.io.*;public class Main{ public static void main(String[]args){ Scanner scanner=new Scanner(System.in); int n,m,cnt=0; int materials[]; n=scanner.nextInt(); m=scanner.nextInt(); materials=new int[n]; for(int i=0;i   💡시간 단축 방법자바로 코드를 작성하다 보면 Scanner와 System.out.println()을 사용하여 입출력 처리를 한다. 하지만 코딩테스트에서는 시간초과로 안되는 경우도 있는 것처럼 시간 소모가 심하다는 단점이..

📌 문제  📝 풀이 과정위 문제는 의상의 이름과 종류를 입력하면 의상을 입을 수 있는 경우의 수를 구하는 문제이다[예제 입력 1] 에서 의상의 종류는 2가지 이다. 같은 종류의 의상은 하나만 입을 수 있으므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses) 총 5가지의 경우의 수가 나온다 → HashMap을 이용하여 의상의 종류와 개수를 세어 나타내도록 한다 (key 값은 의상의 종류이고 value값은 개수이다)  여기서 경우의 수 5가지를 어떻게 도출할 수 있을까?  입지 않는 경우를 추가하고 곱하면 모든 경우의 수가 나온다  ( 3 × 2 = 6가지)그리고 x끼리의 경우 (즉, 아무것도 입지 않은 경우)를 빼면 된다  ( ..

알고리즘 문제를 풀 때 예제 입출력이 맞게 나와도 실제 코드를 제출했을 때 시간초과로 통과하지 못하는 경우가 종종 있다. 우리가 작성한 코드의 실행 시간을 어떻게 알 수 있을까? 이러한 시간은 사용된 언어 종류, 컴퓨터 사양, 컴파일러 속도 등 여러가지 영향을 받게 된다. 따라서 시간복잡도를 설명할 때는 입력값과 연산 수행 시간의 상관관계를 중점으로 설명한다 시간복잡도 (time complexity) 입력크기에 대해 어떠한 알고리즘이 실행되는 데 걸리는 시간, 주요로직의 반복 횟수를 중점으로 측정됨 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘 시간복잡도 표현방법은 3가지가 있다 1) 오메가 표기법 (Big-Ω) : 최상의 경우 2) 세타 표기법 (Big-θ) : 평균의 경우 3) 빅오 ..