2JINISHAPPY 2JINISHAPPY

www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 컴퓨터를 연결하는 네트워크(가중치 무방향 그래프)가 주어졌을 때, 해당 네트워크의 MST를 구하는 문제이다 MST는 프림 알고리즘으로 구할 수 잇다 #include #include #include #include #define INF 987654321 using namespace std; priority_queue pq; vector edge; int v, e, cost[10005], pre[10005], ans; bool visit[10005]; void prim(int u) { visit[u] =..

programmers.co.kr/learn/courses/30/lessons/49993 코딩테스트 연습 - 스킬트리 programmers.co.kr 스킬과 스킬트리가 아래와 같다면, 스킬트리에 있는 element가 스킬의 순서대로 있는지 count 하는 문제 "CBD" ["BACDE", "CBADF", "AECB", "BDA"] def solution(skill, skill_trees): answer = 0 for s in skill_trees: idx=0 k=1 print(s) for i in range(len(s)): if idxidx: k=0 if k==1: answer+=1 return answer

www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 유니온 파인드(Disjoint Set)을 활용해서 정점간의 연결을 확인하는 문제이당 도시의 연결 정보가 주어질 때 마다 Union 연산을 한 뒤, 여행 계획에 속한 정점들이 같은 Parent에 속해있는지 확인하면 된다 #include #include using namespace std; struct disjointSet { vector parent, rank; disjointSet(int n) { rank.re..

www.acmicpc.net/problem/19235 19235번: 모노미노도미노 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net (구)삼성 기출문제집에 있던 문제들 중 단연 난이도 1위를 자랑했던 문제이자 인턴 지원할 때 코테에서 만났던 문제........!! 물론 체감 난이도 자체는 엄~~~~~청 높은 편은 아니었기에 2솔을 할 수 있었다 하지만 해당 링크의 문제는 까다로운 조건이 있어서..... 그걸 모두 만족시켜주어야만 솔브 가능하다 이렇게 빨간색 구역 내의 좌표에 블럭을 놓으면, 그걸 아래와 오른쪽으로 모두 내리고 추가 연..

Heap은 자료구조의 한 종류로써, 특정 property를 만족하는 Complete Binary Tree를 말한다 Heap의 어떤 node p에 대해, p의 parent node를 q라 하면 q의 value는 p의 value보다 작다 ❗❗ 이런 property를 만족하는 힙은 Min-Heap이라고 하며, 반대(q.value>p.value)의 경우에는 Max-Heap이라고 한다 Heap은 보통 Priority Queue 혹은 Heap Sort를 구현하는데에 사용된다 그리고 Complete Binary Tree의 한 종류이기 때문에, Linked List보다는 Array로 구현하는 것이 효율적이다 😉 (중간에 낭비되는 공간이 없기 때문) 이 때, Heap의 대표적인 연산은 min(max)반환/insert/d..

BST는 (sorted array라는 가정하에) 시간복잡도가 O(log n)이 걸리는 Binary Search를 활용한 트리 형태이다 하지만 그러한 Binary Search를 굳이 배열이 아닌 트리를 이용해서 구현하는 이유는? - 다른 element에 비해 특정 element에 대한 검색을 많이 할 경우 ➡ 해당 element를 root에 가깝게 위치시키면 시간을 절약할 수 있음(ADT BST) - Array에 element를 삽입 혹은 삭제하는 경우 ➡ 최악의 경우 O(n)시간이 소모된다 이러한 이유로 ㅇㅣ진 탐색트리를 이용한다 다시 정확하게 정의하자면, Binary Search Tree: 자식이 최대 2명이고, Binary Search를 가이드하는 형태를 띤 트리 BST의 가장 큰 특징은 key값 k..

www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치� www.acmicpc.net 정말 애증의..... 문제 .......... 일단 풀이부터 올린다 #include #include using namespace std; typedef struct { int r, c; }point; typedef struct { int w, s, d; }cosm; vector map[51][51]; vector tmp[51][51]; int n, m, k,ans, dc..

www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주�� www.acmicpc.net 처음 다익스트라 알고리즘을 모를 때는 바보같이 BFS로 푸는 줄 알았지만..... 가중치 그래프에서 최단거리를 찾는 문제이기 때문에 다익스트라로 풀어야 한다 !! #include #include #include #define INF 987654321 using namespace std; typedef struct { int x, y; }point; struct compare { bool o..