https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모www.acmicpc.net   문제를 보고 .replace()같은 라이브러리를 쓰면 무조건 시간초과가 날것이 뻔했으므로O(N)혹은 최대 O(KN) (K = 36)안에 문제를 해결하는 방법을 찾다가문자열 수식에서 괄호의 유효성을 체크하는 문제가 떠올라서스택으로 풀었다. 처음에 한번 풀다가 틀렸었는데 틀린 이유는 모든 문자를 일단 스택에 집어넣어야한다는점을 간과했다. 나는 PS를 할때 자바를 사용하는데 그 이유는 클..

https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적www.acmicpc.net   제목에 낚여서 PriorityQueue 두개를 만들어서 풀었더니 시간초과가났다. TreeMap을 사용해서 풀었더니 시간초과가 해결되었음. 뭔가 시간초과를 해결할때 HashSet등을 많이 생각했었는데 TreeMap을 생각해본적은 없는것같아 반성하게되었다. import java.io.BufferedReader;import java.io.InputStreamReader;import java.util..

https://swexpertacademy.com/main/talk/codeBattle/problemDetail.do?contestProbId=AV-fO0s6ARoDFAXT&categoryId=AYIPD136YD8DFATO&categoryType=BATTLE&battleMainPageIndex=1  SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com   수열에 수가 두개씩 추가되는데 실시간으로 중앙값을 게속 찾아야되는 문제이다.실시간으로 진행되기때문에 수가 들어올때마다 정렬하고 , 중앙값을 찾는 방식으로 구현하면 타임아웃이 뜬다. 검색해보니 맥스 힙과 민 힙을 사용하여 실시간으로 중앙값을 찾는 알고리즘이 있었다.그것을..

우선순위 큐 일반적인 큐는 들어온 순서대로 나가는 구조를 취하는데, 우선순위 큐는 크기 순(우선순위) 순으로 정렬하여 poll하게 되면 가장 큰 값을 추출하게 된다. 일반적으로 우선순위 큐는 최대 힙을 이용해 구현한다. 힙 완전 이진 트리의 한 종류 이며 우선순위 큐를 목적으로 만들어진 자료구조. 데이터들의 집합중 최소값, 최소값을 추출하기 쉽다는 장점이있다. 힙에는 최대 힙(가장 큰값이 루트), 최소 힙(가장 작은 값이 루트) 두 종류가 있다. (편의상 최대 힙 기준으로 설명하겠음) 루트노드는 가장 큰 값(최소 힙일때는 가장 작은값) 자식노드들은 부모노드들보다 항상 작은 값. 완전 이진트리를 만족 완전 이진트리를 강조하는 이유는 완전이진트리라는 성질떄문에 트리를 배열로 구현하기 쉽기 떄문이다. 루트노드..

그래프 그래프는 정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge) 들의 집합으로 구성된 자료구조 형태 선형 구조나 트리 형태로 나타내기 어려운 N:N 관계를 가지는 원소들의 표현에 적합하다. 그래프 유형 무향 그래프(Undirected Graph) 유향 그래프(Directed Graph) 가중치 그래프(Weighted Graph) 사이클 없는 방향 그래프(DAG, Directed Acyclic Graph) 완전 그래프 (정점들에 대한 모든 간선이 존재하는 그래프) 부분 그래프 (원래의 그래프에서 일부의 정점이나 간선만 나타낸 그래프) 인접하다 (Adjacency) 두개의 정점에 간선이 존재 하면 두 정점은 인접해 있다. 완전 그래프는 임의의 정점 V1,V2가 모두 인접해 있다. 경로 단순경로..

Binary Search Tree 검색을 하기위해 유용한 자료구조 배열, 연결리스트 의 경우 앞쪽부터 뒷쪽까지 순차적으로 탐색하기때문에 O(n) 배열로 구현한 이진 탐색의 경우 O(logN) 데이터의 크기가 커질수록 최악과 최선의 경우의 편차가 큼. 이진 탐색 트리 이진 탐색 트리에서 평균적으로 탐색 시간 복잡도는 O(logN) 이다. 최악의 경우 이 경우 O(N) 단점 똑같은 키인 2,3,4,5,6이 들어갔다고해서 이진 탐색 트리의 탐색 시간이 항상 똑같은것은 아니다. 키의 삽입 순서에 따라 트리의 균형이 달라지기 때문에 트리의 균형을 예측하기 어렵다. 크기 순으로 넣으면 불균형해진다. 시간복잡도 이진 탐색 트리의 특징 모든 원소의 키는 유일한 키를 가진다. 왼쪽 서브 트리 키들은 루트 키보다 작다. ..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15PTkqAPYCFAYD&categoryId=AV15PTkqAPYCFAYD&categoryType=CODE&problemTitle=%EA%B3%B5%ED%86%B5%EC%A1%B0%EC%83%81&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1  SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com  주어진 입력을 트리로 저장할 수 있으면 정답을 도출하는데에는 별로 어려움이없었다.대신 ..

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=4&contestProbId=AV141176AIwCFAYD&categoryId=AV141176AIwCFAYD&categoryType=CODE&problemTitle=&orderBy=PASS_RATE&selectCodeLang=ALL&select-1=4&pageSize=10&pageIndex=1  SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com[연산이 가능한 경우][연산이 불가능한 경우]                                       수식 트리 (Expressi..