본문 바로가기

CS

[ 프로그래머스 ] 소수 만들기 ( 자바 ) [ 프로그래머스 ] 소수 만들기 ( java ) 주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.제한사항 nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다. nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다. 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/courses/30/lessons/12977 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로.. 더보기
Binary Search Tree binary tree에서 검색 효율이 좋은 자료구조다. 장점 이진 탐색과 링크드 리스트 자료구조를 결합한 형태로 각 장단점을 보완한 것이 BST 이진탐색 : O(logn) 으로 탐색한다. 매번 원소를 비교 시, 비교 대상이 절반으로 줄어든다. 링크드 리스트 : 추가 삭제 시 O(1) 시간 복잡도 트리 높이에 비례한다. 따라서, balanced/unbalanced인지에 영향을 받는다. balanced경우, 탐색이 O(logn)이지만, unbalanced 되면 O(n)이 된다. 이 경우, 다시 rebalancing이 필요하다. 이 기법을 갖는 자료구조가 AVL, red black tree 특징 1 모든 key값은 unique. 그렇지 않으면 조건 2,3 번에 위배된다. 그래서 중복된 key입력이 보이면 co.. 더보기
tree 자료구조 tree 자료구조 tree는 계층적 관계(Hierarchical Relationship)를 표현하는 자료구조다. 큐, 스택, 리스트와 같은 서형 자료구조와 다르다. parent, child로 노드간의 상위/하위 노드를 표현한다. root노드를 제외한 나머지 노드는 단 하나의 부모노드만 갖는다. 1 tree에는 사이클이 없다. 2 모든 노드는 모두 연결되어 있다. 3 임의의 노드에서 다른 노드로 가는 경로가 유일하다. 쓰임 1 현실 세계 개념을 추상화 2 탐색형 자료구조 구성 Node(노드) : tree를 구성 요소 Edge(간선) : Node간에 연결하는 선 Root Node : 트리에서 최상위 노드 Leaf Node : 트리에서 최하위 노드들로 다른 하위 노드가 없다. Internal Node : Le.. 더보기
구현) 정렬 선택 정렬 - 어떤 정해진 위치에 들어갈 원소를 선택하는 정렬 - in-place 정렬 중 하나다. in-place정렬이란 입력 배열 외에 추가적인 메모리가 필요없는 정렬을 의미한다. 공간 복잡도 O(1) - 시간복잡도 항상 O(N^2) 왜냐하면 원소를 선택하기 위해 모든 원소를 검사하기 때문이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 static void swap(int a, int b) { int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } static void selectionSort() { // 최소 원소가 들어갈 위치 for(int place = 0 ; place 공간 복잡도 O(1) - 단점 .. 더보기
구현) 큐, 스택 자료구조 구현 1. 자료구조 특징 정리 2. 자료구조 특징에 사용될 변수를 정의한다. 3. 자료구조 특징에 따라 구현한다. 구현 시, 변수를 어떻게 활용할지 고려 4. 자료구조 '최대 입력', '비었을때 제거'와 같이 경계영역? 예외 처리 해준다. ex) 배열 크기, 포인터 역할의 변수 ( 경계 영역에서 어디를 가리켜야 하는지 ) 스택 1. Last In First Out 2. top 이용 마지막 원소의 인덱스 3. 구현 시 주의할 점 pop() 스택이 빈 경우 push() 스택이 다 찬 경우 배열을 이용한 스택 구현 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 static class mySta.. 더보기
선형 자료 구조 일렬로 늘어선 자료를 저장하기 위한 자료구조. 종류 정적 배열 동적 배열 연결 리스트 정적 배열 - 데이터가 메모리에 연속적으로 저장된다. - 크기가 고정이다. - 시간 복잡도 인덱스를 알면 O(1)로 접근 가능 ( Random Access ) 동적 배열 - 데이터가 메모리에 연속적으로 저장된다. - 크기(capacity)가 동적으로 증가한다. 자바에서 대표적으로 ArrrayList가 동적배열이다. - 시간 복잡도 인덱스 통한 접근 O(1) ( Random Access ) capacity 증가 시, 배열을 복사 후 더 큰 배열로 옮기기 때문에 O(N) 삽입/삭제 시, 기존 원소들의 shift 연산이 필요해서 최악으로 O(N) ex) 첫 번째에 삽입/삭제는 기존의 모든 원소들을 밀어야 하기 때문에 O(N).. 더보기
플로이드 와샬 알고리즘 모든 쌍 최단 거리 알고리즘 단일 시작점 최단 거리 알고리즘인 다익스트라, 벨만 포드와 다르게 모든 쌍 최단 거리 알고리즘이다. 음수 사이클이 없는 음수 가중치에서도 작동한다. vs 다익스트라, 벨만포드 단일 시작점 최단 거리 알고리즘을 모든 정점에서 실행하여도 모든 쌍 최단 거리 알고리즘을 구할 수 있다. 하지만, 구현하기에 플로이드 워샬이 더 간단하다. 또한, 간선이 많은 경우에도 시간 복잡도가 더 낫다. 모든 쌍 최단 거리 시간 복잡도 다익스트라 O(V x ElgE) 벨만포드 O(V x VE) 플로이드 O(V^3) 핵심 1 dist[u][v] 2차월 배열의 dist[u][v]를 사용한다. u에서 v까지의 최단거리 유지 이동 불가능한 경우는 큰 수로 초기화하며 동일한 정점의 경우는 0으로 초기화한다... 더보기
벨만-포드 알고리즘 ( 자바 ) 벨만-포드 알고리즘이란? (Bellman-Ford's algorihm) 1. 단일 시작점 알고리즘 시작점에서 다른 모든 정점까지의 최단 거리를 찾는다. 2. 방향 그래프 방향 그래프를 가정으로 둔다. 따라서, 무방향 그래프가 주어진다면 간선을 쪼개 방향 그래프로 바꿔야 한다. 3 음수 가중치 음수가 아닌 가중치만 다루는 다익스트라와 다르게 음수 가중치에서도 최단 거리 문제를 정의할 수 있는 알고리즘이다. 또한, 음수 싸이클로 인해 최단 거리를 정의할 수 없는 경우도 알아낼 수 있다. 동작 과정 1 상한을 두고 최단 거리 줄여나가기 upper[i] : 정점 i까지의 최단 거리의 상한을 의미한다. 알고리즘이 진행되며 upper 오차를 줄여나간다. 최종적으로 작동이 완료되면 upper값들이 최단 거리가 된다... 더보기

티스토리툴바