본문 바로가기

Algorithm/백준

 (16)
백준 1030번 프렉탈 평면 (JavaScript) 1초마다 가로세로가 N배씩 커지고 가운데 K*K개는 검은색으로 칠해진다. 이를 0초일 때부터 차곡차곡 블럭을 붙이면서 만들게 되면, O(N^s) 만큼의 시간복잡도와 공간복잡도를 가지게 된다. N는 최대 8이고 s는 최대 10이다. (2^3)^10 = 2^30 = 10^9 인데, 0,1을 1byte로 저장한다면 1GB의 공간이 필요하게 된다. 그래서 전부다 계산하는 것은 비효율적이고 문제의 128MB메모리 제한에 걸리게 된다. 그래서 역으로 x,y 좌표의 프렉탈 평면의 값이 무엇일지를 계산한다. find함수 내에서 하는 것이 바로 그 일이다. 먼저 복사 되기 이전의 가로길이(beforeWidth)를 구하고, n과 k를 이용해 x,y가 검은색으로 칠해지는 범위에 있는 값인지 확인한다. 만약 범위 안이라면 1..
백준 15678번 연세워터파크 (JavaScript) 1번째 징검다리부터 N번째 징검다리를 순차적으로 확인하면서, 현재징검다리보다 d개 전까지의 징검다리중 최대 값과 현재의 징검다리의 값을 비교하여 최대값을 현재 징검다리 값으로 업데이트한다. d개전의 징검다리의 최대값을 그냥 구한다면 O(d)가 걸리겠지만, 세그먼트 트리를 구성하여 구한다면 O(log(d))가 된다. 따라서 이 문제를 O(nlog(n))으로 풀 수 있게 된다. 아래는 JavaScript 풀이 코드이다. const readline = require('readline'); const rl = readline.createInterface({ input: process.stdin, output: process.stdout }); let input = []; rl.on('line', function..
백준 11724번 연결 요소의 개수 (c++) 1부터 n까지 방문하지 않은 노드를 확인할 때마다, 해당 노드와 연결된 노드들 전부를 방문하고 정답에 +1을 해준다. 연결된 노드를 방문하는 방식은 BFS를 이용하면 된다. #include #include #include using namespace std; vector node[1010]; int visited[1010]; int main() { int n, m; cin >> n >> m; for (int i = 1; i > l >> r; node[l].push_back(r); node[r].push_back(l); } int answer = 0; for (int i = 1; i
백준 1764번 듣보잡 (c++) 듣도 못한 사람을 map에 저장한 뒤에, 보도 못한 사람을 해당 map에서 찾는다. map에서 결과가 있을 경우 이사람은 듣보잡이다. 이사람들을 모은 뒤에, 정렬하고 출력해주면 된다. #include #include #include #include #include using namespace std; unordered_map kiku; vector answer; int main() { int n, m; cin >> n >> m; string s; for (int i = 0; i > s; kiku.insert(make_pair(s, 0)); } unordered_map::iterator iter; for (int i = 0; i > s; iter..
백준 1697번 숨바꼭질 (c++) +1, -1, *2 로 탐색하는 경우에 대해서 BFS로 문제를 풀어주면 된다. Queue에는 해당 위치와 몇번만에 도착했는지를 pair로 저장해서 넣어주고, 목적지에 도달했을 때, pair에 저장되어 있는 값을 확인해주면 된다. #include #include using namespace std; bool visited[100010]; int main() { for (int i = 0; i > n >> k; queue q; pair start = make_pair(n, 0); q.push(start); visited[n] = true; int answer = 0; while (!q.empty()) { pair..
백준 1012번 유기농 배추 (c++) BFS문제입니다. 모든 지역을 방문하고, 배추가 있는 지역에 방문했을 때, BFS로 연결되어있는 모든 지역을 다 방문합니다. 배추가 있는 지역을 처음 방문할 때의 횟수를 정답으로 출력해주면 됩니다. #include #include using namespace std; int hatake[55][55]; bool visited[55][55]; int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; int m, n, k; bool isSafe(int x, int y) { if (x >= 0 && x = 0 && y > t; while (t--) { cin >> m >> n >> k; for (int i = 0; i < n; i++) { for (int j = 0; j..
백준 17626번 four squares (c++) 어떤 수를 제곱수의 합으로 표현할 때, 사용되는 최소 제곱수의 개수를 구하는 문제이다. 다이나믹 프로그래밍으로 문제를 해결할 수 있다. n = (0, 1, 2, 3, ... n -1) + k2(k는 k2 > n; dp[0] = 0; dp[1] = 1; for (int i = 2; i
백준 11049 행렬 곱셈 순서 행렬의 곱셈 순서에 따라서 필요한 곱셈의 수가 달라진다. 최소 곱셈 횟수를 찾는 것이 문제의 목표이다. 어떤 n이 주어졌을 때, A0A1...An-1에서 모든 곱셈의 경우를 보고 그 최소값을 찾아야된다. 곱셈의 결과를 저장하는 배열을 dp라고하고 dp[i][j]를 i부터 j번째까지의 최소 곱셈의 수를 저장한다. 행렬의 행과 열의 값을 페어로 저장하여, a에 저장한다. a[i].first는 Ai행렬의 행, a[i].second는 Ai행렬의 열의 값을 가진다. 이때 dp[i][i] = 0이고, 1 n; for (int i = 0; i > l >> r; a.push_back(make_pair(l, r)); dp[i][i] = 0; } for (int ..

티스토리툴바