728x90 반응형 자료구조5 [백준]25497번: 기술 연계마스터 임스 https://www.acmicpc.net/problem/25497 25497번: 기술 연계마스터 임스 $1$, $2$, $S$ - $K$, $2$로 스킬을 성공적으로 총 4번 사용했다. www.acmicpc.net 자료구조 알고리즘 중 stack을 이용한 문제다. 푼 사람이 적어 내가 고민한 아이디어를 공유해보려 한다. string을 통해 기술을 입력 받는다면 사실상 N은 필요없다. 접근 아이디어는 다음과 같다. 스킬을 보면 SK와 LR은 세트다. 즉 S가 먼저 나와야 K가 가능하고 L이 먼저 나와야 R이 가능하다. 그렇다면 이 두개의 세트를 담을 stack을 준비한다. 각 stack은 SK와 LR만을 담는다. 이때 lrCombo stack은 LR만을 skCombo stack은 SK 기술만을 처리한다... 2023. 12. 6. [자료구조] 스택(Stack) 스택이란 -가장 나중에 추가된 데이터가 먼저 출력 처리되는 Last In First Out(LIFO) 자료구조다. -가장 최근에 입력된 순서대로 처리해야 하는 상황에 이용된다. -자료를 스택에 저장할 땐 Push, 꺼낼 땐 가장 최근 것부터 꺼내는데 이를 Pop 이라 한다. -스택에서 Pop시 스택에 top 값을 가져오면서 삭제한다. Stack 클래스 -.NET에는 Non-Generic인 Stack 클래스와 Generic 형태인 Stack 클래스가 있다. -Stack은 내부적으로 순환 배열로 구현되어 있으며, 스택이 가득 차면 자동으로 배열을 동적으로 확장한다. 사용 예제 using System; using System.Collections; using System.Collections.Generic; .. 2023. 6. 23. [자료구조] 연결 리스트(Linked List) Linked List 란? -데이터를 포함하는 노드들을 연결하여 컬렉션을 만든 자료 구조 -각 노드는 데이터와 다음/이전 링크 포인터를 갖게 된다. -단일 연결 리스트(Singly Linked List)는 노드를 다음 링크로만 연결한 리스트 -이중 연결 리스트는 각 노드를 다음 링크와 이전 링크 모두 연결한 리스트 -Circular Linked List(순환 연결 리스트)는 마지막 노드의 다음 링크가 맨 처음 노드를 가리키게 연결한 리스트 LinkedList 클래스 -.NET에서 LinkedList 클래스는 이중 링크드 리스트로 구현되어 있다. -LinkedListNode 클래스는 리스트 노드를 표현한다. -AddFirst, AddLast, AddBefore, AddAfter등으로 링크스 리스트 맨 앞,.. 2023. 6. 22. [자료구조] 시간 복잡도 정리 자료 구조 삽입 검색 삭제 인덱스 접근 T[] O(n) O(n) O(n) O(1) List O(1) O(n) O(n) O(1) LinkedList O(1) O(n) O(n) O(n) Dictionary O(1) O(1) O(1) - SortedDictionary O(log n) O(log n) O(log n) - HashSet O(1) O(1) O(1) - SortedSet O(log n) O(log n) O(log n) - Stack O(1) - O(1) - Queue O(1) - O(1) - 2023. 6. 21. [자료구조] 배열(Array) 배열 -연속적인 메모리상에 동일한 타입(or 그의 파생타입)의 요소를 일렬로 저장하는 자료구조 -인덱스를 사용하여 직접적으로 엑세스 가능 -고정된 크기를 갖는다 -> 초기화시 해당 크기 그대로 유지 (중간에 새로 사이즈를 바꾸지 않는다면) 배열의 시간 복잡도 -배열의 사이즈와 상관없이 한 요소에 접근하는 시간은 인덱스 사용시 O(1) -특정 요소를 찾기 위해선 배열의 크기 n에 대하여 O(n) 배열 최적화 -정렬된 배열에서 값을 찾는 경우, Binary Search를 이용하여 O(long n) 가능 배열 사용법 -ex) 1부터 10까지 합을 출력하는 프로그램 class Program { static void Main(string[] args) { int[] numArray = new int[10]; in.. 2023. 6. 20. 이전 1 다음 728x90 반응형