Seok_In

문제 접근방법 처음 봤을때 중복에 대한 생각을 Set을 생각하지 못해 접근이 어려웠었다. 1. 우선 Ban Id에 해당되는 아이디들을 구하여 ArrayList로 만든다. 2. DFS를 통해 1번에서 구한 아이디들을 BanID의 갯수만큼 하나씩 검색해서 HashSet에 넣는다. 2-1. 이 과정에서 중복을 피하기 위해 BanID의 사이즈와 Depth가 같도록 해서 종료조건을 설정한다. 답 import java.util.*; import java.util.regex.Pattern; class Solution { HashSet result; ArrayList banUsers; public int solution(String[] user_id, String[] banned_id) { result = new Ha..

문제 접근방법 1. 제한사항이 결국 5 * 5 대기실이 5개가 있기때문에 브루트포스로 접근하여 문제를 해결하기로 했다. 2. 기본적으로 참가자들을 모두 담을 자료구조가 필요했기때문에 간단히 큐를 생각해서 참가자들의 자리를 배열로 넣었다. 3. 큐에서 꺼낸 참가자의 4방을 모두 탐색한다. 3-1. 파티션인 경우 해당사항이 없으니 넘어간다. 3-2. 다른 참가자인 경우 False 3-3. 빈자리인 경우 한 번더 4방 탐색을 진행한다. 이 때 기존에 시작했던 참가자의 자리는 탐색하면 안되기에 체크해준다. 3-4. 4방 탐색시 다른 참가자인 경우 False 코드 import java.util.*; class Solution { static int dx[] = {1,-1,0,0}; static int dy[] =..

문제 접근방법 s의 길이가 1부터 1000까지이므로 모든 경우에 대해서 검사해도 N^2으로 시간복잡도에서 가능하다. 괄호를 쌍으로 맞는지 짝으로 비교해야하기 때문에 Stack 자료구조를 떠올려서 문제에 접근하고자 하였다. Stack에 앞에서부터 순서대로 문자열을 넣어주고 닫는 문자열이 나왔을 때 스택의 Peek와 비교하여 완전한 문자열인지 판단하면 된다. 경우는 아래와 같이 나눴다. 1. 여는 괄호일 경우 1-1. 마지막 원소인 경우 False 처리 1-2. 그 외의 경우는 Stack에 Push 2. 닫는 괄호일 경우 2-1. Stack이 비어있을 경우 False 처리 2-2. Stack의 Peek와 비교하여 맞는 쌍이 아닐때는 False 처리, 그 외엔 Stack을 Pop 답 import java.ut..

Hash 가변길이 데이터를 해시 함수를 통해 고정길이 데이터로 바꾸는 것을 말한다. Hash Table Key, Value 로 데이터를 저장하는 자료구조이다. 해시 테이블에서는 내부적으로 배열을 사용하여 저장하고 키 값에 해시 함수를 적용해 인덱스를 만들고, 이를 활용하여 값을 조회하거나 저장한다. Hash Collision 해시 함수를 통해 반환되는 값이 동일한 해시코드가 될 수 있는 경우 문제가 된다. 해결방법 1. 체이닝 : 연결리스트로 노드를 계속 추가해나가는 방식 2. 오픈 어드레싱 : 해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용 (해당 키 값에 저장되어있으면 다음 주소에 저장) 2-1. 선형 탐사 2-2. 제곱 탐사 2-3 이중해싱 Trie(트라이) 트라이는 문자..

Tree 트리는 대표적인 비선형 자료구조로 방향성이 있는 비순환 그래프의 한 종류이다. 값을 가진 노드(Node)와 이 노드들을 연결해주는 간선(Edge)으로 이루어져 있다. 트리는 2개의 노드 사이에서 1개의 간선만을 가지며 사이클이 절대 존재하지 않는 방향 그래프이다. Tree vs Graph 그래프는 노드(하나의 점)와 노드 간을 연결하는 간선으로 구성된 자료 구조이다. 이를 통해 연결된 노드 간의 관계를 표현할 수 있는 자료구조이다. 트리 순회 방식 전위 순회 Root → 왼쪽 자식 → 오른쪽 자식 중위 순회 왼쪽 자식 → Root → 오른쪽 자식 후위 순회 왼쪽 자식 → 오른쪽 자식 → Root 레벨 순회 루트부터 계층별로 방문하는 방식 이진트리 각 노드가 최대 두 개의 자식노드를 갖는 트리로 ..

스택(Stack) 스택은 먼저 삽입된 데이터가 가장 마지막에 제거되는 후입선출(last-in first-out) 형태의 자료구조다. 간단하게는 배열로 구현할 수 있으며, 연결리스트를 이용하여 구현할 수 있다. 삽입(push)과 삭제(pop)는 스택포인터를 이용함 isEmpty는 SP가 -1이면 true// false isFull은 SP값이 MAX_SIZE와 같으면 true//false 연결리스트를 통해 구현하면 크기가 동적인 스택 만들 수 있음. 큐(Queue) 큐는 먼저 삽입된 데이터가 가장 먼저 제거되는 선입선출(first-in first-out) 형태의 자료구조다. 보통 연결리스트를 이용하여 구현한다. 삽입(enQueue)과 삭제(deQueue)는 front, rear를 이용함 isEmpty는 fr..

자료구조 자료구조는 전산학에서 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법이다. 올바른 선택의 자료구조는 보다 효율적인 알고리즘을 사용할 수 있도록 한다. 선형과 비선형 선형 자료구조 : Data요소가 순차적으로 저장되어있는 자료구조 비선형 자료구조 : Tree나 Graph 처럼 멀티 레벨로 구성되어 있고 데이터 요소가 순차적으로 저장되어있지 않는 것. 배열(Array) 배열은 메모리에 데이터를 연속적으로 저장하는 자료구조. 인덱스로 조회할 수 있기에 Random Access가 가능함. 하지만 삽입과 삭제시에 앞 요소들을 이동해야하기 때문에 더 많은 비용이 발생 단순 연결리스트(Singly Linked List) 단순 연결리스트는 노드에 다음 노드의 주소를 가리키는 정보만 추가되어있는 가장..

📌 문제 📌풀이 처음 봤을 때 N과 K의 범위가 300,000 이기 때문에 보석을 전부 가방에 넣어보는 식으로 구현하면 시간초과가 발생한다. 따라서 O(NlogN)의 시간복잡도로 접근해야한다. 생각해보면 풀이는 간단하다. 그리디적으로 생각해봤을때 각 가방에 들어갈 수 있는 보석들 중에서 가장 가치가 높은 보석을 가방에 넣으면 된다. 하지만 모든 보석을 각 가방마다 탐색하게 된다면 O(N^2)의 시간복잡도가 발생하게 된다. 따라서 가방을 정렬하고 보석들도 정렬한 후에 한 번 살펴본 보석들은 다시 안 보는 방식으로 구현하도록 해야한다. 1. 보석들 무게 순으로 정렬하기(오름차순, 같으면 비싼순으로) 2. 가방들 무게 순으로 정렬하기(오름차순) 3. 가장 가벼운 가방부터 보석의 무게와 비교하며 넣을 수 있는 ..

병합정렬은 nlogn의 시간복잡도를 가진다. 1초 기준 100,000의 범위까지 정렬가능 public static void mergeSort(int arr[]){ sorted[] = new int[arr.length]; mergeSort(arr, 0, arr.length-1); sorted = null; } // 왼쪽 오른쪽 나누기 public static void mergeSort(int arr[], int left, int right){ // 같으면 return if(left==right) return; int mid = (left+right)/2; mergeSort(arr,left,mid); mergeSort(arr,mid+1,right); merge(arr,left,mid,right); } pub..

시간제한이 1초인 문제의 경우 N의 범위가 500 : O(N^3) 알고리즘 N의 범위가 2000 : O(N^2) 알고리즘 N의 범위가 100,000 : O(NlogN) 알고리즘 - 병합정렬 N의 범위가 10,000,000 : O(N) 알고리즘 공간 복잡도 int arr[1000] : 4KB int arr[1000000] : 4MB 자료구조에 따른 시간복잡도 ArrayList - 접근 : O(1) - 마지막 값 삽입/삭제 : O(1) - i번째 값 삽입/삭제 : O(n) -처음 값 삽입/삭제 : O(n) LinkedList - 접근 : O(n) - 마지막 값 삽입/삭제 : O(n) - i번째 값 삽입/삭제 : O(n) - 처음값 삽입, 삭제 : O(n) Arrays.sort 는 DualPivotQuickS..