happindex

💡 대부분의 내용을 Do it! 알고리즘 코딩테스트 with JAVA 강의를 참고하여 정리하였습니다. DFS (Depth - First Search) DFS (깊이 우선 탐색)은 그래프 완전 탐색 기법 중 하나이다. 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른쪽 분기로 이동하여 다시 탐색한다. (최대 깊이까지 탐색한 후 다음으로 넘어간다!) 특징 재귀함수로 구현한다. 이때, stack overflow에 유의해야 한다. 스택 자료구조를 이용한다. 시간 복잡도 O(V + E) O(노드 수 + 엣지 수) 핵심 이론 노드 방문 여부를 체크할 배열이 필요하다. 한 번 방문한 노드는 다시 방문하면 안 되기 때문이다. 중복 방문 불가!! 그래프(데이터를 담는 자료구..

💡 대부분의 내용을 Do it! 알고리즘 코딩테스트 with JAVA 강의를 참고하여 정리하였습니다. 합 배열 구간 합 알고리즘을 활용하기 위해서는 먼저 합 배열을 구해야 한다. 배열 A가 있을 때, 배열 S를 합 배열이라고 하면, 다음과 같이 나타낼 수 있다. S[i] = A[0] + A[1] + A[2] ... + A[i-1] + A[i] 합 배열 공식은 다음과 같다. S[i] = S[i-1] + A[i] 구간 합 구간 합은 합 배열을 이용하여 시간복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘이다. 배열에서 특정 범위의 값들의 합을 구하고 싶을 때 합 배열을 이용하면 빠르게 구할 수 있다. i에서 j까지의 구간 합을 구할때, 공식은 다음과 같다. S[ j ] - S[ i-1 ]

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net Solution 1. 문제에서 0번째 배열을 1번째 배열이라고 지칭하고 있다. 따라서, 0번째 배열을 비워두고 1번째 부터 값을 채워나가면 로직이 더 간편해진다. 예제를 대입하여 그림으로 이해하는 것이 빠르다. import java.io.*; import java.util.*; public class Main { public static void main(String[] a..

BufferedReader는 Java.io에 속하는 입력 클래스로, Scanner에 비해 처리 속도가 빠르다. 때에 따라 2배 이상 차이 나는 경우도 있다. 알고리즘 문제를 풀 때 유용할 것!! Scanner Scanner sc = new Scanner(System.in); String str = sc.next(); // 문자열 입력받기 int i = sc.nextInt(); // 정수 입력받기 long l = sc.nextLong(); // long타입 입력받기 BufferedReader BufferedReader br = new BufferedReader(new InputStreamReader(Syste.in)); String s = br.readLine();// 문자열 입력받기 int i = Int..

💡 대부분의 내용을 Do it! 알고리즘 코딩테스트 with JAVA 강의를 참고하여 정리하였습니다. 배열 배열은 연속 공간에 값이 채워져 있는 형태의 자료구조이다. 배열의 특징 인덱스를 사용하여 값에 바로 접근이 가능하다. 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다. (연속 공간에 값이 채워져 있는 형태이기 때문) 삽입 및 삭제를 원하는 인덱스 주변에 있는 값을 이동시켜야 한다. 배열의 크기는 선언 할 때 지정해야 하고, 한번 선언하면 크기를 늘리거나 줄일 수 없다. 리스트 리스트는 값과 포인터를 묶은 노드를 포인터로 연결한 자료구조이다. 리스트의 특징 인덱스가 없다. 따라서 값에 접근하려면 Head 포인터부터 순서대로 접근해야 한다. → 값에 접근하는 속도가 느리다. 포인터로 연..

💡 대부분의 내용을 Do it! 알고리즘 코딩테스트 with JAVA 강의를 참고하여 정리하였습니다. 시간 복잡도 알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 의미한다. 일반적으로 1초에 1억번의 연산을 할 수 있다. 문제에서 시간 제한이 2초라면, 2억 번 이하의 연산 횟수로 문제를 해결해야 한다! 연산 횟수는 1초에 1억번 연산하는 것을 기준으로 생각한다. 시간제한이 2초라면, 2억번 이하의 연선 횟수로 문제를 해결해야 한다! 시간 복잡도 활용 시간 복잡도를 계산하려먼 데이터의 개수와 제한 시간을 보면 된다. 🧐 [문제 1] N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. - 시간 제한 : 2초 - 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,..

💡 대부분의 내용을 점프 투 자바 에서 참고하여 정리하였습니다. final 자료형에 값을 단 한번만 설정할 수 있게 강제하는 키워드이다. 값을 한 번 설정하면 해당 값을 변경할 수 없으므로, 값이 바뀌면 안 될 때 사용한다. final int n = 123; n = 456; // 컴파일 오류 발생!!! list와 final 리스트도 final로 선언하면 재할당이 불가능하다. 하지만, 리스트에 값을 더하거나 빼는 것은 가능하다. (재할당만 불가능할 뿐.) final ArrayList a = new ArrayList(Arrays.asList("a", "b")); a = new ArrayList(Arrays.asList("c", "d")); // 컴파일 에러 발생!!! a.add("c"); // 에러 발생하지..

💡 대부분의 내용을 점프 투 자바 에서 참고하여 정리하였습니다. 형변환 (문자열 ↔ 숫자) 문자열을 숫자로 Integer.parseInt() String str = "100"; int i = Integer.parseInt(str); Long i = Integer.parseLong(str); int형 뿐만 아니라 byte, short, long, float, double 등 숫자 관련 타입은 전부 가능함. pareseByte(), parseShort() … Integer는 int 자료형의 Wrapper 클래스이다. 자바의 자료형은 크게 기본 타입(primitive type)과 참조 타입(reference type)으로 나누어 진다. 기본 타입 - int, char, double 등 참조 타입 - class..

💡 대부분의 내용을 점프 투 자바 에서 참고하여 정리하였습니다. enum enum 자료형은 서로 연관이 있는 것들의 상수 집합을 정의할 때 사용한다. 예를 들어, 어느 카페에서 판매하는 커피의 종류가 다음과 같다고 가정한다. 아메리카노 카페라떼 밀크티 이를 enum으로 상수집합을 만들 수 있다. enum CoffeType { AMERICANO, CAFELATTE, MILKTEA }; 이렇게 정의한 상수집합은 다음과 같이 사용할 수 있다. public class Sample { enum CoffeeType { AMERICANO, CAFELATTE, MILKTEA }; public static void main(String[] args) { System.out.println(CoffeeType.AMERICA..

💡 대부분의 내용을 점프 투 자바 에서 참고하여 정리하였습니다. Math 클래스 Math 클래스는 java.Lang 패키지에 포함된 클래스로 수학과 관련된 일련의 작업들을 처리할 수 있다. Math 클래스의 다양한 메소드들은 전부 static으로 구현되어 있으므로 따로 객체를 생성하지 않고 사용할 수 있다. System.out.println(Math.max(10,50)); // 50 출력 System.out.println(Math.min(10,50)); // 10 출력 System.out.println(Math.abs(-10)); // 10 출력 System.out.println(Math.random()); // 0.0 ~1.0 사이의 난수 출력 메소드 max(), min() 입력한 두 데이터 중 더 큰..