본문 바로가기
728x90
반응형

Java

 (376)
[프로그래머스-LEVEL 1] 2. x만큼 간격이 있는 n개의 숫자 x만큼 간격이 있는 n개의 숫자 문제 설명 함수 solution은 정수 x와 자연수 n을 입력 받아, x부터 시작해 x씩 증가하는 숫자를 n개 지니는 리스트를 리턴해야 합니다. 다음 제한 조건을 보고, 조건을 만족하는 함수, solution을 완성해주세요. 제한 조건 x는 -10000000 이상, 10000000 이하인 정수입니다. n은 1000 이하인 자연수입니다. 입출력 예 x n answer 2 5 [2,4,6,8,10] 4 3 [4,8,12] -4 2 [-4, -8] class Solution { public long[] solution(int x, int n) { long[] answer = {}; answer=new long[n]; for(int i=0;i 테스트시 3가지 테스트케이스는 통과하..
[프로그래머스-LEVEL 1] 1. 직사각형 별찍기 이 문제에는 표준 입력으로 두 개의 정수 n과 m이 주어집니다. 별(*) 문자를 이용해 가로의 길이가 n, 세로의 길이가 m인 직사각형 형태를 출력해보세요. 제한 조건 n과 m은 각각 1000 이하인 자연수입니다. 예시 입력 5 3 출력 ***** ***** ***** import java.util.Scanner; class Solution { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int a = sc.nextInt(); int b = sc.nextInt(); for(int j=0;j
[알고리즘] 4-2. 클래스 이진트리 1. Node Class protected static class Node { protected E data; protected Node left; protected Node right; public Node(E data) { this.data = data; left = null; right = null; } public String toString() { return data.toString(); } } 2. BinaryTree Class public class BinaryTree { protected static class Node { protected E data; protected Node left; protected Node right; public Node(E data) { this.data ..
[알고리즘] 4-1. 검색 트리 트리와 이진 트리 1. 트리 : 계층적 구조를 표현 [조직도, 디렉토리와 서브 디렉토리, 가계도] 루트 노드 : 맨 위의 노드 리프 노드 : 자식이 없는 노드 내부 노드 : 리프노드가 아닌 노드 노드 연결 선 : link, edge, branch 부 트리 : 노드와 그 노드의 자손으로 이루어진 트리 루트 노드를 제외한 모든 노드는 유일한 부모 노드를 갖는다. 부모-자식 관계와 조상-자손 관계 -> 부모 자식은 1촌, 조상 자손은 n촌 트리의 성질 1. 레벨은 1부터 시작한다. 2. 노드가 N개인 트리는 항상 N-1개의 링크를 갖는다. 3. 루트에서 어떤 노드로 가는 경로는 유일 4. 임의의 두 노드간의 경로도 유일 이진 트리의 성질 1. 각 노드가 최대 2개의 자식을 갖는다. 2. 각각의 자식 노드는 부..
[알고리즘] 3-5. 자바의 정렬 1. 기본 타입 int [] data = new int [capacity]; Arrays.sort(data); //int 배열이 모두 꽉 차있을 경우 Arrays.sort(data, 0, size); //int 배열이 size-1까지 size개만 있을 경우 2.객체의 문자열 정렬 String [] fruits = new String[] {"Pineapple", "Apple", "Oragne", "Banana"}; Arrays.sort(fruits); for(String name : fruits) System.out.println(name); 3.ArrayList의 문자열 정렬 List fruits = new ArrayList(); fruits.add("Pineapple"); fruits.add("Appl..
[알고리즘] 3-4. 분할 정복을 이용한 정렬 (3) 비교 정렬 1. 데이터 간 상대적 크기 관계를 이용해 정렬 2. 데이터 간 크기 관계가 정의되어 있을 경우 적용 가능 3. 버블정렬, 삽입정렬, 합병정렬, 퀵정렬, 힙정렬 논-비교 정렬 1. 정렬할 데이터에 대한 사전지식 이용 2. Bucket Sort (버킷 정렬) 3. Radix Sort (기수 정렬) 하한 1. 입력된 데이터 한번씩 보기 위해 O(n) 시간복잡도 필요 2. 합병정렬과 힙정렬 알고리즘 시간복잡도 : O(nlog2n) 3. O(nlog2n)이 가장 빠른 비교정렬 결정 트리 1. Leaf 노드 수 : n!개 2. 최악의 경우 시간복잡도 (트리의 높이) :height >=log2n!=O(nlog2n) 선형 시간 정렬 알고리즘 Counting Sort (세는 정렬) -> 배열의 각 정수의 개..
[알고리즘] 3-3. 분할 정복을 이용한 정렬 (2) 힙정렬 1. 최악의 경우 시간복잡도 : O(nlog2n) 2. sorts in place : 추가 배열 불필요 [공간 복잡도 이득] 3. 이진 힙 자료구조 이용 힙의 정의 힙 : 완전이진트리이면서 힙 속성 만족 [힙은 동일 데이터를 가진 서로 다른 힙이 존재 가능하며, 유일하지 않다] [최대 힙 : 부모는 자식보다 크거나 같다.] [최소 힙 : 부모는 자식보다 작거나 같다.] 전이진 트리 : 모든 레벨에 노드들이 꽉 차있는 형태 완전이진트리 : 마지막 레벨 제외하면 완전히 차있고, 마지막 레벨에 가장 오른쪽부터 연속된 노드가 비어있을수있음 힙의 표현 1. 일차원 배열로 표현 : A[1...n] 2. 루트 노드 : A[1] 3. A[i]의 부모 : A[i/2] 4. A[i]의 왼쪽 자식 : A[2i] 4...
[알고리즘] 3-2. 분할 정복을 이용한 정렬 분할 정복법 -> 작은 크기의 동일 문제로 분할 후 순환적으로 해결 -> 작은 문제의 해를 합쳐 원래 문제의 해를 구한다. 합병정렬 1. 데이터가 저장된 배열을 절반으로 나눈다 2. 각각을 순환적으로 정렬 3. 정렬된 두 개의 배열을 합쳐서 전체를 정렬 mergeSort(A[], p, r) { if (p
728x90
반응형

티스토리툴바