Coding/Algorithm 썸네일형 리스트형 BOJ(백준) 3780 - 네트워크 연결 아이디어처음에 독립집합으로 시작해서 연결해나가는 과정을 문제화 시키면 유니온파인드일 가능성이 크다고 생각했다. 지금까지 경험한 유니온파인드들 중에 보통은 그래왔기 때문에 배경지식으로 먼저 떠올렸다. 특이한 것은 find와 merge연산을 할 때, 가중치가 갱신되어야 한다. merge로 처음에 가중치를 초기화 시켜두고, find를 통해 경로압축하는 과정에서 가중치를 더해주어야 한다. 점검해볼 사항- 경로압축하는 과정에서 가중치 업데이트 설계 오래걸린 이유- 재귀 및 변수 추적 힘들었던 부분- 유니온파인드의 응용- 유니온파인드. 분리집합에서 시작해서 합집합 해나가는 과정에서 자주 쓰이는 것 같다는 생각. 시간복잡도 유니온파인드 find와 merge를 O(1)로 가정했을 떄(O(1)에 수렴), O(N + M).. 더보기 BOJ(백준) 2504 - 괄호의 값 아이디어 짝을 맞추는 것이기 때문에 스택(Stack)이 아닐까 생각을 했는데, 조금 까다로웠다. 다른 괄호가 껴있다보니? 스택의 냄새가 너무 강해서, 발상의 전환을 하기까지 시간이 조금 오래 걸렸다. 그러다보니 트리의 관점에서 트리는 선형자료구조로 표현을 할 수가 있었다는 것이 생각이 났고, 트리의 후위순회로 한번 풀어볼 수 있을 것 같았다. 해당 문자열 "(()[[]])([])"의 인덱스(index)는 1번부터 시작한다고 가정했을 때, 루트노드를 0번으로 잡는다고 하자. 일단, 올바른 문자열이 아닐 조건은 크게 3가지로 나눌 수 있다. 1. ((() (열려있는 상태로 끝나는 형태)2. ())) (열려있지 않는데 닫는 형태)3. (] or [) (괄호의 짝이 맞지 않는 형태) 이것에 대한 정리는 트리에서.. 더보기 BOJ(백준) 13119 - Mountains Beyond Mountains 아이디어시뮬레이션에 필요한 것은 경험+배짱이다. 5분만에 풀어줘야하는 문제인데, 더 원활하게 풀기 위해서는, 여러가지 조건들 중에 어떤 것이 더 상위 조건인지. 풀어서 말하면, 어떤조건이 어떤조건보다 우선 시되는지 그 관계만 빨리 잡았으면 과감하게 코딩해도 됬었다. 코드의 간결함 이런거 신경쓰지말고 빨리 코딩해서 답맞추는게 중요하다. 점검해볼 사항- 조건의 관계(상위, 하위)- 코드의 간결함은 신경쓰지 말자 시간복잡도 O(N*M) https://github.com/jongwuner/Algorithm/blob/master/BOJ/13119.cpp 1234567891011121314151617181920212223242526272829303132333435363738394041#include#includeu.. 더보기 BOJ(백준) 11003 - 최솟값 찾기 아이디어 처음엔 보자마자 세그먼트트리를 떠올렸었다. 근데 세그먼트트리의 연산은 갱신과 질의인데, 질의만 사용할 거면 굳이 쓸 필요가 없다고 생각했다. 그리고 세그먼트트리 시간복잡도를 고려했을 때, 세그먼트트리 생성과 연산의 시간때문에 시간초과가 날 우려가 있다고 생각해서, 다른 자료구조와 알고리즘을 고민했다. 스택, 큐, 우선순위 큐는 삽입이 되면 일단 삽입되어있는 내부에 대해서 순서를 알 수 없기 때문에, 자주 활용하는 pair에다가 인덱스(index)를 담아서 삽입하는 아이디어가 있다. 그것을 활용해서, 선형자료구조를 검색하면서 선형자료구조의 인덱스를 체크하는 동시에 우선순위큐의 삽입과 삭제를 활용하면 문제는 쉬워질 것 같았다. 점검해볼 사항- 자료구조에 저장하고 있는 자료. pair- 인덱스 활용-.. 더보기 BOJ(백준) 3078 - 좋은 친구 아이디어 이름의 길이가 상당히 제한적인 것을 보고, 자료구조의 기준을 이름의 길이로 잡아야 겠다는 아이디어를 떠올렸다. if(친구 && 좋은친구)의 기준은 이름의 길이가 같고, 성적의 등수가 K 이하로 나야 하니까, 이름의 길이가 같은 아이들끼리 자료구조에 담아두고, 자료구조에는 그 등수를 담아둔 다음, 정렬을 시킨 뒤, 이진탐색을 하여 좋은 친구의 쌍 수를 구하면 된다. 점검해볼 사항- 이진탐색의 활용.- 정렬을 시켜야하는 아이디어.- 자료구조에 담기는 내용. int, pair- 슬라이딩 윈도우, deque시간복잡도 - Nlog(N) (= N만큼을 사용하여 길이를 인덱스로 가진 선형자료구조에 저장 + 20 * logN (길이는 최대 20이고 그 길이마다의 성적차순을 정렬해준다. + NlogN으로 모든 .. 더보기 BOJ(백준) 6416 - 트리인가? https://github.com/jongwuner/Algorithm/blob/master/BOJ/6416.cpp아이디어 자세히 봐야 알지만 문제에서 '트리'까지는 명시를 해줬지만, 루트가 있는 트리(rooted tree)라는 정보는 숨겨주었다. 어느정도 트리를 경험해본 사람 입장에서는 빨리 캐치했을 것으로 보이지만, indegree가 없는 노드가 루트라는 것을 캐치해내야 한다. 점검해볼 사항- 트리의 정의 : 트리는 공집합도 트리이다. - 루트가 있으면 방향성이 정해진다. (- 방향성이 정해져있는 트리라면, 루트가 있는 것)- indegree가 두개일 수 없다 시간복잡도 O(t*N) : N은 트리의 노드 개수(에지개수 = 노드개수 - 1), t는 테스트케이스 갯수. https://github.com/j.. 더보기 BOJ(백준) 1949 - 우수마을 https://www.acmicpc.net/problem/1949 자료구조(트리, 트리의 독립집합)N개의 노드로 구성된 트리가 있으며, 트리에는 가중치가 있다. 트리의 '독립집합'을 구성할 때, 가장 가중치가 큰 독립집합의 원소 가중치의 합을 구하는 프로그램을 작성하시오. 시간복잡도 : O(N)트리 임을 명시해줬고, 문제에서 트리에 대한 개념적 속성까지 다 명시해줬다. 점검해볼 사항 - 트리의 독립집합- 트리와 DP는 다 후위탐색인가? https://github.com/jongwuner/Algorithm/blob/master/BOJ/1949.cpp 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#.. 더보기 BOJ(백준) 3482 - Labyrinth https://www.acmicpc.net/problem/16437 자료구조(트리), 트리의 지름R x C(3 더보기 이전 1 2 3 다음
