728x90 [대회] 2022 ICPC Sinchon Winter Algorithm Camp Contest - 초급 22W 신촌 겨울 알고리즘 캠프가 끝난 후, 곧이어 22W Camp Contest에도 참가하였다. (캠프 후기 링크) 지금까지 SUAPC, Camp Contest, 홍익 프로그래밍 대회, ICPC 등등 수많은 대회에 참여했었지만 이번만큼 긴장된 적은 없었다. 예전엔 '잘 보면 좋고 아님 말고'의 마인드로 그저 수많은 연습게임 중 하나인 것처럼 문제를 풀었었다. 하지만 이번엔 달랐다. 두 달 동안 알고리즘 캠프에 열심히 참여했어서 그런지 대회를 잘 치르고 싶었고 전날부터 긴장이 되었다. 그래서 11주 동안 캠프에서 배운 내용들을 계속해서 복기하고 풀었던 주요 문제들을 복습했다. 예전에 참여했던 Camp Contest에서는 실버4, 실버1을 풀었고 실버3을 맞왜틀하다가 끝났었다. 골드5인 D와 E는 어려워서.. 2022. 2. 20. [알고리즘 개념정리] 11. 분리집합/최소 신장 트리 **본 포스팅은 22Winter 신촌캠프 초급반 강사 raararaara님의 강의를 참고하여 작성하였습니다.** 분리 집합 (Disjoint Set) 서로 겹치는 원소가 없는 집합들을 관리하는 자료구조 서로소 집합, 유니온-파인드 (Union-Find) 포레스트의 일종 Find - 주어진 원소가 포함된 집합의 대푯값을 구하는 연산 - 집합마다 유일한 대푯값 존재 - 나머지 다른 원소에서 대표로 가는 경로 존재 Union - 두 집합을 합치는 연산 - 한 집합의 대푯값을 다른 집합의 대푯값으로 linking int par[1000001], height[1000001]; int find(int num){ if(num==par[num]) return num; //self roop만났음! 즉, 대푯값 찾았음! .. 2022. 2. 17. [백준/C++] 15942번: 전구를 켜라(G2) 문제 https://www.acmicpc.net/problem/2423 2423번: 전구를 켜라 첫째 줄에 문제의 정답을 출력한다. 전구에 불을 켜는 것이 가능하면, 몇 개의 칸을 돌려야 하는지를 출력하고, 불가능할때는 "NO SOLUTION"을 따옴표 없이 출력한다. www.acmicpc.net 사용한 알고리즘 2022.02.14 - [PS/Algorithm] - [알고리즘 개념정리] 10. 최단경로 알고리즘 -> 다익스트라 풀이 타일 말고 꼭짓점을 기준으로 생각해보자. (0,0)에서 (n,m)까지 가는 최단경로를 구하면 된다. 타일들이 간선역할을 한다고 생각하고, 타일을 회전시키지 않아도 만들어지는 연결은 가중치 0, 타일을 회전시켜야 만들어지는 연결은 가중치 1로 간선을 모델링한다. 이때, 2차원 .. 2022. 2. 14. [알고리즘 개념정리] 10. 최단경로 알고리즘 **본 포스팅은 22Winter 신촌캠프 초급반 강사 dart님의 강의를 참고하여 작성하였습니다.** 가중치 그래프 그래프에 더 많은 정보를 표현하기 위해 간선에 여러 가지 속성을 부여할 수 있는데, 그중 하나가 바로 '가중치'라는 수 하나를 부여하는 것 두 정점간의 거리, 이동시간, 두 물건 사이의 교환비율, 한 정점에서 다른 정점으로 갔을 때 얻을 수 있는 이득/손해 등 -> 간선에 가중치를 부여해보자! 인접 리스트 adj[s].push_back({e,c}); s에서 e로 가는, 가중치 c를 갖는 간선 : pair을 이용해서 간선의 가중치도 같이 넣는다. 인접 행렬 adj[s][e]=c; : 연결을 1로 나타내는 게 아니라 그 가중치로 나타낸다. 최단경로 알고리즘 BFS를 이용하면 그래프에서의 최단경.. 2022. 2. 14. [백준/C++] 15942번: Thinking Heap(G2) 문제 https://www.acmicpc.net/problem/15942 15942번: Thinking Heap Binary heap은 Heap을 구현하는 방법의 하나이며 Complete binary tree 형태로 만들어진다. Complete binary tree는 Binary tree의 종류 중 하나로, 마지막 레벨을 제외한 나머지 레벨에는 노드가 꽉 차 있고 마지막 www.acmicpc.net 사용한 알고리즘 2022.02.09 - [PS/Algorithm] - [알고리즘 개념정리] 9. 트리 -> Binary Heap 풀이 heap[idx] 배열로 min-heap binary tree를 관리해준다. 1-based로 하면 부모 idx가 i일 때, 자식은 2i 와 2i+1이고 자식 idx가 i일 때,.. 2022. 2. 11. [알고리즘 개념정리] 9. 트리 **본 포스팅은 22Winter 신촌캠프 초급반 강사 raararaara님의 강의를 참고하여 작성하였습니다.** 트리 (Tree) Connected Acyclic Undirected Graph 모든 정점이 이어져있음(연결 그래프) / 사이클 존재하지 않음 / 방향성 없음 계층형 자료구조 리프노드를 제외한 노드들은 T1, T2, ... Tn을 root로 하는 서브트리들을 가진다. 부모/자식, 형제(부모 노드가 같음), 조상(부모 노드들의 집합), 자손(자식 노드들의 집합), 리프 노드, 서브 트리(어떤 노드 t와 그 자손들로 구성된 트리), 포레스트(트리가 여러개) 간선의 개수 = 정점의 개수 -1 : sparse graph 이므로 인접리스트로 표현할 수 있다. 임의의 서로 다른 두 정점 사이의 경로가 유.. 2022. 2. 9. 이전 1 ··· 3 4 5 6 7 8 9 ··· 13 다음 728x90
