알고리즘63 [C++]백준 1992번 : 네트워크연결 www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 1. 접근, 풀이 모든 node를 대상으로 최소스패닝트리를 구하는 문제로 edge의 정보가 주어진다. 따라서 edge 기준으로 그래프의 최소스패닝트리를 구할 수 있는 크루스칼 알고리즘을 적용했다. union&find에서 더 작은 node를 parent로 선택했다. #include #include #include #include #include #include #include #include using namespace std; struct state{ int a, b, c; }; struct comp.. 2020. 12. 6. [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. [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. [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. [C++]백준 2116번 : 주사위 쌓기 www.acmicpc.net/problem/2116 2116번: 주사위 쌓기 첫줄에는 주사위의 개수가 입력된다. 그 다음 줄부터는 한 줄에 하나씩 주사위의 종류가 1번 주사위부터 주사위 번호 순서대로 입력된다. 주사위의 종류는 각 면에 적혀진 숫자가 그림1에 있는 www.acmicpc.net 1. 접근&풀이 첫번째 주사위의 밑면(혹은 윗면)에 따라 쌓이는 다음 주사위의 밑면(혹은 윗면)이 결정되는 것을 이용한다. 입력은 주사위의 특성을 바로 활용할 수 있도록 주어지지 않으므로 특성을 이용할 수 있도록 입력받는 것이 포인트인 것 같다. (i면의 반대면은 (i+3)%6) #include #include using namespace std; int N, d[10000][6], ans = 0; int main(.. 2020. 11. 29. [C++]백준 1027번 : 고층건물 www.acmicpc.net/problem/1027 1027번: 고층 건물 세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작) www.acmicpc.net 1. 접근 기울기에 따라 옥상이 보이는지 확인할 수 있다. 2. 틀린 이유, 보완점 최대 높이가 1000000000000인 것에 따라 초기 각도 변수 값을 적절하게 초기화해주어야한다. 아니면 -DBL_MAX로 초기화해도 좋다. 추가로 선택한 건물에서 양 옆을 매번 확인할 필요없이 i->j 옥상이 보이면 j->i 옥상이 보이는 것을 이용하여 2차원 배열 check를 통해 연산을 최소화하자. #include #in.. 2020. 11. 29. 이전 1 ··· 3 4 5 6 7 다음
