분류 전체보기104 [C++]백준 13913번 : 숨바꼭질4 www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 1. 접근 초당 +1,-1,*2로 이동하여 최단 시간 목적지에 도착하는 경로를 구하는 것이므로 pq를 사용하고 cnt 배열로 위치마다 최단 시간을 갱신하고 이때마다 pre[] 배열로 processor 위치를 갱신했다. 경로는 pre[]배열을 이용해서 K==N일 때까지 경로를 stack에 쌓고 순서대로 출력했다. #include #include #include #include #.. 2020. 12. 4. [C++]백준 1261번 : 알고스팟 www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 1. 접근 pq를 통한 bfs에서 각각의 방에 몇번 벽을 깨고 들어왔는지 3차원 배열에 저장을 하며 정답을 구했다. 해당 방식은 아래의 코드와 같고 정답을 받을 수 있었지만 시간과 메모리 사용량이 너무 크다고 생각했다. #include #include #include #include #include #include #include using namespace std; struct state.. 2020. 12. 4. [자료구조] 3. Graph : MST, 최단거리, Union-Find 0. Graph 노드들과 그 노드들을 연결한 간선에 대한 정보를 저장하는 자료구조 1. Terminology 1) vertex(정점), edge(간선) 2) degree : 한 정점에 간선으로 연결된 정점 개수 2-1) in-degree : 방향 그래프에서 한 정점으로 들어오는 간선 개수 2-2) out-degree : 방향 그래프에서 한 정점에서 나가는 간선 개수 3) Simple Path : 경로 내 중복되는 정점이 없는 경로 1) Ordered/unOrdered : 간선의 방향 유무 2) Weighted : 간선에 가중치 유무 3) Connected/Disconnected : 그래프 내 한 정점에 대해서 나머지 정점으로의 경로 존재 유무 4) Cycle/Acycle : 시작점과 도착점이 동일한 Si.. 2020. 12. 3. [C++]백준 9944번 : NxM 보드 완주하기 www.acmicpc.net/problem/9944 9944번: NxM 보드 완주하기 N×M 보드 위에서 할 수 있는 게임이 있다. 보드는 크기가 1×1인 정사각형 칸으로 나누어져 있다. 보드의 각 칸은 빈 칸 또는 장애물이다. 장애물은 아래 그림에선 어두운 사각형으로 표시되어져 www.acmicpc.net 1. 접근 공이 방향을 전환하는 분기가 있고, 각 분기로 나누어진 경우마다 모든 map을 탐색할 수 있는지를 알아야하기 때문에 dfs를 생각했다. 모든 맵을 탐색했는지 확인하기 위해서 1) 더 이상 못움직이는 경우 모든 맵을 탐색했는지 반복문으로 확인하여 결과 도출 2) map을 입력 받을 때 탐색할 수 있는 공간의 개수를 따로 저장해서 활용하여 결과 도출 두 가지를 생각했는데 2번째 방식이 가독성,.. 2020. 12. 2. [C++]백준 16137번 : 견우와 직녀 www.acmicpc.net/problem/16137 16137번: 견우와 직녀 견우와 직녀는 여러 섬과 절벽으로 이루어진 지역에서 살고 있다. 이 지역은 격자로 나타낼 수 있으며, 상하좌우로 인접한 칸으로 가는 데 1분이 걸린다. 7월 7일은 견우와 직녀가 오작교를 건너 www.acmicpc.net 1. 접근 일단 목적지까지의 최소 도달 시간을 구하는 것이기 때문에 priority queue를 사용한 bfs를 해야겠다고 생각했다. 구현 과정에서 여러 조건들을 맞춰야했다. 2. 풀이 과정 이 문제만의 조건과 그에 따른 처리는 다음과 같이 생각했다. 1) 목적지로 가는 과정에서 딱 한번 M주기의 다리를 만들어 건널 수 있다. check[N][N][2]를 통해 check[][][0]은 다리를 만들어 건넌 경.. 2020. 12. 1. [자료구조] 2. Tree : Binary Tree, Heap, BST 1. Terminology 1) Degree : # of child the node has 2) Size : total # of node in tree 3) Depth : # of edge that need to pass from root node(>=0) 4) Height : maximum value of depth 5) Level : set of node at same level 2. Binary Tree Tree의 각 Node가 최대 2개의 Children Node를 가지는 Tree 자료구조 * number of node in tree = n, height of tree = h 일때 → 2h + 1 ≤ n ≤ 2^(h+1)-1 1) Compelete Binary Tree : 완전이진트리 마지막 le.. 2020. 12. 1. [자료구조] 1. Array, Pointer, Stack, Queue, LinkedList 1. Array 연속적인 memory에 저장된 같은 type의 data집합 2. Pointer // 일반 포인터 type* var_name; cout data = (element); // == *(*ptr).data = (element); 3. Stack 한쪽 끝에서만 자료를 추가하고 삭제할 수 있는 FILO형태의 자료구조 4. Queue 한쪽 끝에서만 자료를 추가하고 삭제할 수 있는 FIFO형태의 자료구조 5. Linkedlist 기준에 따라 순서대로 배치할 때 새로운 element 삽입/삭제를 단순 Array보다 빠르게 할 수 있는 자료구조 typedef struct listNode *listPtr; typedef struct listNode{ int data; listPtr link; } listP.. 2020. 12. 1. [C++]백준 16986번 : 인싸들의 가위바위보 www.acmicpc.net/problem/16986 16986번: 인싸들의 가위바위보 두 사람이 같은 손동작을 내어 무승부가 발생할 경우 경기 진행 순서상 뒤인 사람이 이긴 것으로 간주함에 다시 한 번 유의한다. 구체적으로, 경기 진행 순서는 지우, 경희, 민호 순으로 고정되 www.acmicpc.net 1. 접근 경우의 수마다 체크해야할 것이 1) 지우가 K번 이겼는지 2) 다른 두 명이 먼저 K번 이겼는지 3) 지우가 중복하지 않게 손동작을 했는지 4) 이번 가위바위보가 몇 번째 차례인지 라고 생각하여 재귀로 풀어야 한다고 생각하고 접근했다. 2. 오해 경희, 민호의 20번 손동작에 대한 정보가 입력으로 주어지는데, 해당 순번은 가위바위보의 총 turn 수가 아닌 개개인의 turn에 따라 내는 손동.. 2020. 11. 30. [C++]백준 10836번 : 여왕벌 www.acmicpc.net/problem/10836 10836번: 여왕벌 입력의 첫 줄에는 격자칸의 가로와 세로 크기 M(2 ≤ M ≤ 700)과 날짜 수 N(1 ≤ N ≤ 1,000,000)이 자연수로 주어진다. 첫날 아침의 애벌레 크기는 모두 1이므로 입력에 주어지지 않는다. 다음 N개의 www.acmicpc.net 1. 접근 문제에서 주어진 그대로 첫 row, col은 입력대로 증가시키고 이 외의 원소는 3방향 중 가장 큰 증가량을 조사하면서 하나하나 증가시켰다. 하지만 700*700 크기의 배열을 1000000에 대해서 해당 연산을 하니 당연히 시간초과 2. 풀이 규칙을 찾아야 했는데, "오름차순으로 주어진 0,1,2가 몇번 연속적으로 쓰여있는지"가 입력으로 주어지므로 '첫 번째 열의 원소'들은.. 2020. 11. 30. 이전 1 ··· 6 7 8 9 10 11 12 다음
