2진수(Binary), 8진수(Octal), 10진수(Decimal), 16진수(Hexadecimal) 등 진법을 변환하는 방법을 정리한다.10진수를 2, 8, 16 진수로 변환int a = 10;// 2진수System.out.println(Integer.toBinaryString(a));System.out.println(Integer.toString(a, 2).toUpperCase());// 8진수System.out.println(Integer.toOctalString(a));System.out.println(Integer.toString(a, 8).toUpperCase());// 16진수System.out.println(Integer.toHexString(a));System.out.println(In..
CS Fundamentals/Data Structures & Algorithms
자신과 연결된 인접 노드를 모두 방문 하는 그래프 완전 탐색 방식BFS 사용 고려 기준양방향 그래프, 사이클이 있는 그래프에서는 제약 조건이 주어지지 않을 경우 무한루프가 발생한다.큐에 들어가는 모든 노드를 한 번씩 방문하기 때문에 방문할 필요가 없는 노드의 정보를 큐에 담지 않는게 좋다.그래프 정보를 인접행렬에 담을 때는 메모리의 낭비가 많고, 노드의 개수가 많아 질 경우 사용이 제한된다. ※ 1만개의 노드 정보를 담기 위해 2차원 배열 생성시 380MB 수준의 메모리 소요인접 리스트는 간선 정보가 많을 때 메모리 소비가 늘어나고, 탐색 시간이 오래 걸린다.단 하나의 간선 정보를 관리해야 할 때는 인접 행렬이 용이하다. 샘플 예제 코드노드 정보 입력// 인접행렬 무가중치arr[from][to] = ..
Array 또는 ArrayList 배열의 내부 요소 정렬 기준을 Customize 하는 방법을 정리한다.기본 sort() 함수 사용Array 정렬// 오름차순int arr[] = {1, 2, 6 ,7, 8, 2 ,3, 4};Arras.sort(arr);// 내림차순Integer arr[] = (1, 2, 6 ,7,8 ,2 , 3, 4 };// 내림차순으로 정렬 시 Collections의 reverseOrder 메서드는 객체를 인자 값으로 받기 때문에 Integer 객체로 변환 필요Array.sort(arr, Collections.reverseOrder);Array List 정렬// 오름차순ArrayList arr = new ArrayList();arr.add(1);arr.add(10);arr.add(3)..
MAP을 상속받아 구현되어 Entry (Key : Value) 구조로 데이터가 저장된다. 키 값을 기준으로 검색하기 때문에 내부 데이터를 순회하며 조회하기 위한 자료 구조가 아니다.HashMap 사용 고려 기준HashMap은 주로 DAT로 활용하는데, 아래의 세 가지 경우 Array 타입 대신 HashMap을 이용해 DAT를 구성한다.인덱스의 값이 정수가 아닌 경우 사용한다.저장하고 싶은 값이 음수인 경우 사용한다.저장할 데이터의 양이 1,000만 개를 넘기는 경우 사용한다. ※ int 타입 Array 기준 1억 개 공간 확보 시 380MB 소요 HashMap의 시간 복잡도Array와 동일하게 O(1)의 시간 복잡도를 가지지만 상대적으로 느리다.키 값을 hashcode에 넣어 연산 후 나오는 숫자로 b..
Java의 Collection과 Map을 이용해 알고리즘 문제를 해결할 때, 어떤 자료 구조를 사용할지 선택할 때 고려하는 기준을 정리한다.Array배열의 사이즈를 알 수 있는 경우 기본 Array를 사용하는 것이 가장 좋다.배열은 물리 메모리의 연속된 공간을 확보 후 데이터를 저장한다.데이터 접근 시 배열의 시작 지점 메모리 주소를 기준으로 특정 인덱스의 메모리 주소를 연산하는 공식을 사용한다.더보기Array 배열 내부 데이터의 메모리 주소를 구하는 공식 [배열의 시작 주소] + ( [요소의 크기] × [인덱스 번호] ) 배열의 시작 주소 : 0x00000000 요소의 크기 : (chat) 1byte, (int) 4btye, (double) 8byte 2번째 인덱스 메모리 주소: 0x00000000 ..
변수는 값을 담아두고 재사용하기 위해서 사용하는데, 변수의 기본적인 사용법과 Custom Data Type(Custom Variable Type) 사용법을 정리한다.변수 초기화// [Data Type] [Variable Name] = [Value]String name = "GilDong";변수는 대입 연산자(=)를 이용해서 값을 메모리에 담는다.변수 초기화 과정: 메모리 확보 → 데이터 저장 → 메모리 주소를 Variable Name에 맵핑메모리 주소의 형태: (16진수) 0x00000000메모리를 확보하는 공간은 Data Type에 따라서 다르다. (char = 1byte, int = 4byte, double = 8byte) 변수의 종류전역 변수: 특정 함수에 종속 되지 않고 모든 영역에서 사용되는 변..
2차원 배열이나 그리드 기반의 문제에서 주어진 위치의 4방향(상, 하, 좌, 우) 또는 8방향(상, 하, 좌, 우, 대각선 포함) 으로 이동하기 위한 좌표 값 획득을 위해 사용한다. DFS, BFS, 다익스트라 알고리즘에서 활용할 수 있다.방향 배열 Offset Sample4방향, 8방향 배열을 만들 때는 행, 열을 기준으로 2개의 Offset을 만들어야 한다.4방향 배열 Offset (상, 하, 좌, 우)int[] dRow = {-1, 1, 0, 0}; // 행 방향int[] dCol = {0, 0, -1, 1}; // 열 방향8방향 배열 Offset (상, 하, 좌, 우, 상우, 하우, 하좌, 상좌)int[] dRow = {-1, 1, 0, 0, -1, 1, 1, -1}; // 행 방향int[]..
배열의 인덱스(Index) 값에 의미를 부여해서 사용하는 자료구조다. 저장하려는 데이터의 키(key) 값과 배열의 인덱스 값을 직접 연동시켜 데이터의 저장 위치가 키 값에 의해 결정되고, 데이터를 저장하거나 빠르게 접근하고자 할 때 사용한다.Direct Address Table의 장점배열은 인덱스에 저장된 요소의 값을 꺼내 오는데 필요한 연산의 시간 복잡도가 O(1)이다. DAT 자료 구조를 사용해 값을 저장할 경우 배열의 빠른 연산 속도를 활용해 알고리즘 문제 해결에 적용할 수 있다. 입력 받은 알파벳이 샘플 데이터에 존재하는지 체크하는 예제 코드변수 값 초기화// 샘플 데이터char[][] sampleArr = { {'C', 'D', 'A'}, {'B', 'M', 'Z'}, {'..
Char 자료형에 저장되는 단일 문자는 내부적으로 정수형 아스키 코드 값으로 표현된다. 이 특징으로 문자열 조작, Direct Address Table에서 활용하여 프로그래밍에 활용할 수 있다.ASCII (American Standard Code for Information Interchange) 컴퓨터와 통신 장비에서 문자를 표현하는 데 사용되는 7비트 인코딩 표준이다.128개의 문자를 표현할 수 있다. 각 문자의 순서에 따라서 0부터 127까지 고유 숫자 값이 할당되어 있다. 영문 알파벳, 숫자, 특수 문자, 제어 문자가 포함되어 있다.대문자소문자숫자CharASCII Char ASCII Char ASCIIA65a97048B66b98149C67c99250D68d100351E69e101452F70f..
