자바127 [백준 1967] 트리의 지름 / 자바 / DFS 문제 레벨: G4알고리즘: DFS풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/19671 번째 시도: 실패 [깨달은 점]dfs는 리턴값이 void이고 전역변수를 고치는 게 구현하기 편함 리턴값이 int면 구현하기 까다로움[알고리즘 설명]지름의 중심점이 될 수 있는 노드는 자식을 2개 가지고 있는 노드이다.그래서 중심점이 될 수 있는 노드들을 dfs하며 답을 업데이트해간다.dfs는 루트노드에서 양갈래로 찢어져 가장 각각 가장 긴 길을 구한다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayL.. 2024. 6. 20. [백준 11723] 집합 / 자바 / 비트마스킹 문제 레벨: S5알고리즘: 비트마스킹풀이시간: 20분힌트 참조 유무: 유https://www.acmicpc.net/problem/11723 1 번째 시도 [비트마스킹]모든 자료형를 이진수로 표현하는 것. 더 빠른 시간과, 더 적은 메모리 사용[비트 연산자]a&b a와b 둘다 1이어야 1a|b a와b 둘 중 하나라도 1이면 1a^b a와b가 다르다면 1~a 0 -> 1, 1 -> 0aa>>b b비트만큼 우측으로 자리이동[집합의 표현]비트의 각 자리수1: 존재한다.0: 존재하지 않는다.즉 아래와 같다.{A,B,C,D,E,F}{A} = 100000{A,F} = 100001 [로직 설명]boolean배열로도 원소가 있다 없다를 표시할 순 있지만, 메모리 제한이 생긴.. 2024. 6. 20. [백준 1987] 알파벳 / 자바 / 백트래킹 문제 레벨: G4알고리즘: 백트래킹풀이시간: 30분힌트 참조 유무: 무https://www.acmicpc.net/problem/19871 번째 시도 백트래킹 기본적인 문제굳이 설명을 적지 않겠다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;public class Main { static int ans = Integer.MIN_VALUE; static boolean[][] visited; static int[] dx = {1,0,0,-1}; static int[].. 2024. 6. 19. [백준 2407] 두 용액 / 자바 / 투 포인터 문제 레벨: G5알고리즘: 투 포인터 풀이시간: 40분힌트 참조 유무: 무https://www.acmicpc.net/problem/24701 번째 시도 [로직 설명]1. 입력받은 숫자를 오름차순으로 정렬한다.2. sum 값을 비교해가면 start, end 두 포인터를 조절해간다.3. 종료조건은 start가 end 같거나 클 때이다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;public class Main { public static void main(String[] args) throws IOException { .. 2024. 6. 17. [백준 1644] 소수의 연속합 문제 레벨: G3알고리즘: 투 포인터 + 에스토라테네스의 체 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/16441 번째 시도 : 시간초과 [코드 설명]1. arr배열에 N이하의 소수들을 담는다.2. 소수들을 순회하며 while문 안의 내용을 반복한다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Scanner;public class Main { public static void main(String[] args) throws IOException { BufferedReader.. 2024. 6. 16. [백준 11728] 배열 합치기 / 자바 /투 포인터 문제 레벨: S5알고리즘: 투 포인터풀이시간: 30분힌트 참조 유무: 무https://www.acmicpc.net/problem/117281 번째 시도 1. 두 개의 포인터가 각각의 패열 최근 원소 지목하기2. 포인터가 지정하는 값들 비교해서 작은 값 넣기 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)); StringBuilder sb = new StringBuilder(); String.. 2024. 6. 14. [백준 1806] 부분합 / 자바 / 투포인터 && 누적합 문제 레벨: G4알고리즘: 투포인터 && 누적합풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/18061 번째 시도 입력값을 보면 O(NS)의 시간복잡도는 안 된다는 것을 알 수 있다.그렇다면 가능성 있어 보이는 건 최대 O(NlogN) 정도이다.(일종의 꼼수) 여기서 얻을 수 있는 점은 배열을 1 ~2번 순회(적은 순회라고 생각하면 됨)정도로 답을 구해야 한다. [아이디어]나는 한 번의 배열 순회로 알아낼 수 없을까 라는 생각에서 출발했다.배열을 전부 순회할 때까지 이 과정을 반복한다.1. 15이하라면 다음 숫자를 합에 포함시킨다.2. 15이고 기존 값보다 작다면 값을 갱신한다.3. 15이상이라면 시작숫자를 합에서 제외시키고 시작숫자+1을.. 2024. 6. 13. [백준 11660] 구간 합 구하기 5 / 자바 / 누적합 문제 레벨: 알고리즘: 누적합풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/116601 번째 시도 이 문제는 이차원배열의 누적합이다.알고 가야 할 것은 일차원 배열의 누적합과 배열에 담기는 값이 다른 거이다. 혹시 O 위치의 담길 값이 ---->를 다 더한 값이라고 생각할 수 있다. 그건 틀렸다. ----------->O우린 1,1,를 좌상 꼭지점으로 O을 우하 꼭지점으로 삼는 직각삼각형의 합으로 생각해야 한다.합을 화살표 표시하고 그림으로 나타내면 아래와 같다------ --->O 위 그림을 보면서 배열에 들어가는 값을 이해해보자.빨간색 위치에 배열값은 초록색 + 파란색 - 노란색(겹치는 부분)이다. 이 공식으로 배열을 채우면 된다. .. 2024. 6. 12. [백준 11659] 구간 합 구하기 4 / 자바 / 누적합 문제 레벨: S3알고리즘: 누적합풀이시간: 16분힌트 참조 유무: 무https://www.acmicpc.net/problem/116591 번째 시도 문제를 보고 엥 이거 너무 기초적인 문제 아니야? 라고 생각했다가 제한을 보고 생각을 바꿨다. 100,000(N의 최댓값) x 100,000(M의 최댓값) = 100,000,000,000(1억 초과)이기 때문에 O(n^2) 시간복잡도로는 풀 수 없다. [아이디어]O(N) 시간복잡도를 생각해봤다. 한번에 탐색으로 1 ~ arr[i]까지 담길 배열을 만드는 것이다. 만약 3~5까지 합을 구하고 싶다면 5인덱스에 있는 값(1~5) - 2인덱스에 있는 값(1 ~ 2)로 구하면 되는 것이다.import java.util.*;import java.. 2024. 6. 12. 이전 1 ··· 7 8 9 10 11 12 13 ··· 15 다음
