유미의 기록들

📌 문제   📝 풀이과정1. +, -, * 와 같은 연산자 ArrayList와 숫자의 ArrayList로 나눈다 => 인덱스를 기반으로 연산을 하기 쉬워진다for(int i=0;i 2. 인덱스를 기반으로 해서 재귀함수로 탐색한다 예를 들어 3 + 8 * 7 라면 두가지 경우의 수가 나온다1) (3 + 8) * 7 = 77  → nums[0]과 nums[1]을 opers[0]을 하고 난 후 나머지 계산2) 3 + (8 * 7) = 59  → nums[1]과 nums[2]를 opers[1]을 하고 난 후 나머지 계산       💻 코드import java.util.Scanner;import java.io.*;import java.util.*;public class Main{ static ArrayLis..

📌문제  📝 풀이과정처음에는 내림차순 정렬을 해서 9,3,1 차례로 빼면서 모두 0이하일 때까지 반복하면 최솟값을 구할 수 있다고 생각했다... 하지만 예외1에서도 그 방법은 맞지 않았다  너무 단순하게 생각한 것이다😓 단순하게 9,3,1 만 빼는 것이 아니라 6가지의 경우의 수가 있다  이렇게 그래프로 나타내보면 모든 경우의 수에서 (0,0,0)에 도달하는 최소의 횟수를 구할 수 있다. 즉, 레벨별로 탐색하여 최단거리를 구하는 개념으로 생각해보면 BFS로 풀 수 있는 것을 알 수 있다.   💻코드import java.util.Scanner;import java.io.*;import java.util.*;public class Main{ static int n; static int scv[]=ne..

📌문제     📝 풀이과정최단거리 문제이므로 BFS로 푸는 것이 좋다 1. 시작 좌표값인 (0,0)을 BFS로 넘긴다2. (y,x)좌표를 탐색했으므로 visited[y][x]=1으로 방문처리를 한다2. 이동 할 수 있는 좌표값을 저장할 Queue를 선언하고 (x,y)를 저장한다 3.  Queue 가 비어있지 않을때 까지 반복한다    3-1. Queue에서 처음 입력값을 꺼내 nowY와 nowX를 저장한다    3-2. (nowY,nowX)를 기준으로 상,하,좌,우로 인접한 노드를 탐색해서 이동가능하고 방문하지 않은 노드가 있다면 Queue에 저장한다    3-3. 인접한 노드(ny,nx)를 (nowY,nowX)보다 1 큰 값을 visited배열에 저장한다 (최단거리를 나타내는 배열이다)   ⚠️입력..

📌 문제  📝풀이과정인구이동이 없을 때까지 모든 좌표를 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()을 사용하여 입출력 처리를 한다. 하지만 코딩테스트에서는 시간초과로 안되는 경우도 있는 것처럼 시간 소모가 심하다는 단점이..