Codingtest

출처 https://www.acmicpc.net/problem/4195 접근 처음에는 문제가 잘 이해되지 않았습니다.1 몇 번 읽어보니, 두 정점이 주어지면 두 정점을 연결하고 같은 그래프 내에 있는 모든 친구 개수를 출력하는 문제임을 알았습니다. ①, ②을 통해 연결된 네트워크는 각각 친구가 2명이며, ③을 통해 두 네트워크가 연결되면 총 친구는 4명입니다. 친구관계가 연결되어 같은 그래프에 포함되는 과정이 Union-Find 알고리즘과 동일하기 때문에, 이를 활용하여 해결할 수 있습니다. 유니온 파인드(Union Find) Union과 Find 메서드를 통해 서로소 집합2을 연결하는 알고리즘입니다. 각 집합의 단위는 Root로부터 하위 원소들로 구성되며, 모든 원소들은 동일한 Root를 바라보는 특징이 있습니다. Union과 Find를 간략히 그림으로 나타내면 다음과 같습니다. 노란색 : 부모 / 빨간색 : 유니온(Union) 메서드 / 파란색 : 파인드(find) 메서드 ...

출처 https://www.acmicpc.net/problem/12904 접근 처음에는 DP문제인줄 알고 접근했으나, 시간 초과로 실패했습니다.1 S로부터 T로 갈때는 여러 경로가 존재해서 DP와 같은 최적화가 필요해보입니다. S에서 시작할 경우 2^(T의 길이 - S의 길이) 만큼의 탐색이 필요합니다. 그러나 반대로 T에서 S로 갈때는 경로가 1개만 존재하므로, (T의 길이 - S의 길이)만큼만 탐색하면 S를 구할 수 있습니다. T에서 S로 갈때는 T의 맨뒤 값으로 이전 노드를 예측하는 것이 가능합니다. ...

출처 https://www.acmicpc.net/problem/16927 접근 돌려야 하는 배열을 1차원 배열로 만들어서 R만큼 이동하면 다음 배열 값을 얻을 수 있습니다. 1차원 배열과 2차원 배열을 변환하는게 조금 귀찮은데, 저는 하 -> 우 -> 상 -> 좌(반시계) 순으로 이동하도록 설계했습니다. 2차원 배열을 위 순서로 탐색해서 1차원 배열로 만듭니다. 이 때, 1차원 배열의 크기는 2차원 배열의 (가로 + 세로) * 2 에서 네 귀퉁이(위 사진에서 (1) ~ (4))가 중복되므로 4를 빼주어야 합니다. ...