xxheexx

import java.awt.*; import java.util.*; import java.io.*; public class Main { static int N; static int S; static ArrayList list = new ArrayList(); static int[] re; static int[] arr; static boolean[] vi; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = I..

배열 for문으로 돌리니까 시간초과 -> 풀이 보니까 투포인터 알고리즘.. import java.io.*; import java.util.*; class Solution { static int[] answer; public int[] solution(int[] sequence, int k) { int[] answer = new int[]{0,sequence.length-1}; int left = 0; int right = 1; int sum = sequence[0]; while(left

백트래킹으로 모두 탐색... -> 최소값 찾기 import java.awt.*; import java.util.*; import java.io.*; public class Main { static int N; static int[] num; static int[] operator; static int max = Integer.MIN_VALUE; static int min = Integer.MAX_VALUE; static Queue q = new LinkedList(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in));..

재귀 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘 재귀 함수의 조건 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 함 (Base condition) 모든 입력은 base condition으로 수렴해야 함 재귀에서는 함수를 명확하게 정의해야한다! - 함수의 인자로 어떤 것을 받을지 - 어디까지 계산한 후 자기 자신에게 넘겨줄지 모든 재귀 함수는 반복문만으로 동일한 동작하는 함수 만들 수 있음 재귀는 반복문 구현보다 코드가 간결하지만 메모리/시간에서는 손해 -> 적절한 때에 재귀 구현 한 함수가 자기 자신을 여러 번 호출 -> 매우 비효율적!! 재귀함수가 자기 자신을 부를 때 스택 영역에 계속 누적이 됨 -> 스택 제한이 있는 경우 메모리 초과 날 수 있음 백준 11729번..

내가 푼 코드 import java.util.*; import java.io.*; class Solution { public int[] solution(String s) { int[] answer = new int[2]; Queue q = new LinkedList(); int changeNum = 0; int zeroNum = 0; while(!s.equals("1")){ zeroNum += s.length()-s.replaceAll("0","").length(); s = s.replaceAll("0",""); int len = s.length(); if(len==1) break; while(len>0){ if(len%2==0){ q.add("0"); len/=2; continue; }if(len%2=..

BFS (Breadth First Search) 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 그래프에서 모든 노드를 방문하기 위한 알고리즘 예시 - (0,0)과 상하좌우로 이어진 모든 파란색 칸 BFS로 확인 (0,0) 방문했다는 표시 남기고 해당 칸 큐에 삽입 초기 세팅 끝난 후에는 큐가 빌 때까지 계속 큐의 front를 빼고 해당 좌효의 상하좌우를 살펴보면서 큐에 넣어주는 작업 반복 큐의 front는 (0,0)이고 pop (0,0)의 상하좌우 칸 확인 -> 파란색 칸이면서 아직 방문하지 않은 칸 큐 삽입 ...큐가 빌때까지 반복 큐가 비었을 때 확인해보면 (0,0)과 연결된 파란색 칸 모두 방문 완료 시간복잡도 : 모든 칸이 큐에 1번씩 들어가므로 칸이 N개일 때 O(N) 좌..

bfs로 count를 구하는 문제 bfs: queue를 이용하여 count 구하기 쉬움 dfs: 재귀 함수로 구현되기에 count 구하기 쉽지 않음 예시 : 수빈이 N - 5, 동생 K - 17 0초 1초 2초 3초 4초에 17 도달 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)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.pa..

자바를 오랜만에 써서 기본 자료구조를 선언하는 방법이 헷갈리는 본인을 위한 정리 map Map map = new HashMap(); SortedMap sortedMap = new TreeMap(); queue Queue q = new LinkedList(); Queue 변수명 = new LinkedList(); //다른 자료형 넣기 가능 // 기본형: 우선순위가 낮은 숫자가 먼저 나옴 (작은 숫자) PriorityQueue pQ = new PriorityQueue(); // 우선순위가 높은 숫자가 먼저 나옴 (큰 숫자) PriorityQueue pQ = new PriorityQueue(Collections.reverseOrder()); stack Stack stackInt = new Stack(); de..

Greedy = 지금 가장 최적인 답을 근시안적으로 택하는 알고리즘 = 관찰을 통해 탐색 범위를 줄이는 알고리즘 이상적인 풀이 흐름 1. 관찰을 통해 탐색 범위를 줄이는 방법 고안 2. 탐색 범위를 줄여도 올바른 결과를 낸다는 사실을 수학적으로 증명 3. 구현해서 문제 통과 관련 문제 풀이 https://ssohee-coding.tistory.com/36

그리디 알고리즘 종료 시간을 기준으로 정렬 -> 이전 종료시간에 대해 겹치는 것들은 제외하고 남은 것들 중 선택 빨리 끝나는 것 선택 : a1 a1을 선택한 뒤 다음으로 빨리 끝나는 것 a2 (a1과 겹치므로 제외), a3도 마찬가지 a4는 a1과 겹치지 않으면서 다음으로 빨리 끝남 -> 총 4개 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)); int N = Integer.parseInt(br.readLine())..