PS/백준 (329) 썸네일형 리스트형 [BOJ] 백준 21736 헌내기는 친구가 필요해 (Swift) 문제https://www.acmicpc.net/problem/21736풀이전형적인 그래프 문제이다.BFS, DFS로 풀 수 있는 문제문제 그대로 X 인 곳은 이동 불가능하고, DFS나 BFS로 탐색을 진행하면 쉽게 풀 수 있는 문제이다.소스코드후기그래프 탐색에 대한 이해가 있다면 쉽게 풀 수 있는 문제 [BOJ] 백준 18111 마인크래프트 (Swift) 문제https://www.acmicpc.net/problem/18111풀이이 문제를 처음 봤을 때, 어떻게 풀어야 할 지 생각을 좀 해봤다.결론으로는 가능한 높이를 모두 만들어보고, 최소한의 수를 구하는 방법을 택해야겠다고 생각했다.원래 이런 문제들을 풀 때, 사람이라면 어떻게 계산할 까 생각을 해봤는데..뭐 전부 1이고 하나만 0이면 그냥 한 개 가방에 있는거 꺼내면 되겠다 이런 생각이 들었었다.그런데 제각각 다른 수일 때, 인간이 이걸 어떻게 계산할까 생각을 해보다가모든 경우의 수를 확인해봐야겠다고 생각이 들었다.이 문제에서는 최소 0에서 255까지의 높이까지 쌓을 수 있다고 했으므로, 모두 균일하게 해당 높이를 맞춰보는 식으로 구하고자 했다.n,m이 500이고 높이가 255이므로 255 * 500 .. [BOJ] 백준 17626 Four Squares (Swift) 문제https://www.acmicpc.net/problem/17626 풀이DP로 풀이할 수 있는 문제$f(1) = 1^2$ 이고, $f(2) = 1^2 + 1^2$로 나타낼 수 있다.최대 갯수는 $f(n) = f(n - 1) + 1$으로 볼 수 있다.$f(4) = 2^2$ 같은 경우에는 $2^2$를 어떻게 도출할 수 있을지 생각해보자.이렇게 생각해보면 되지 않을까?4는 $2^2$ 이므로, $f(4) = f(4 - 2^2) + 1$n이 어떤 수의 제곱보다 크거나 같다면 n에서 해당수를 뺀 값에서 +1만큼 경우의 수를 더해주어 n을 만들 수 있다.$f(n) = min(f(n-1)+1, f(n-i*i)+1$소스코드후기기본적인 DP 문제 [BOJ] 백준 11727 2xn 타일링 2 (Swift) 문제https://www.acmicpc.net/problem/11727풀이dp로 풀 수 있는 문제2x1 을 놓을 수 있는 경우의 수 = 12x2 을 놓을 수 있는 경우의 수 = 3 이지만, || 블럭을 제외하면 2개이다.2x3을 놓을 수 있는 경우의 수는 5이고, 직접 그려서 세보았다.이것을 어떻게 도출해 낼 수 있을지 한 번 생각해보자.2x1 까지 채워져 있는 경우, 해당 경우에서 '=' 블럭과, 2x2 블럭을 넣는 두가지 경우가 있다.2x2 까지 채워져 있는 경우에는 | 블럭밖에 놓을 수 없다.여기서 점화식을 도출 할 수 있다.$f(1) = 1, f(2) = 3$$f(n) = f(n-1) + 2*f(n-2)$소스코드후기기본적인 dp 문제였다. [BOJ] 백준 9375 패션왕 신해빈 (Swift) 문제https://www.acmicpc.net/problem/9375 풀이조합 문제이다.옷이 2벌 바지가 3벌 있다면, 옷과 바지를 조합해서 입는 경우의 수는 단순히 2 * 3 = 6으로 나타낼 수 있다.하지만 이 문제에서는 옷만 입거나 바지만 입는 경우도 가능하다.단, 모두 입지 않은 경우를 제외해야한다.따라서 옷이 2벌있다고해도 안입는 경우 까지 총 3벌이 있다고 가정할 수 있다.물론 바지도 마찬가지다.그러면, 3 * 4 = 12 로 나타낼 수 있다.하지만 모두 안입는 경우의 수는 1이다. 해당 경우의 수를 뺴주어야 한다.dictionary를 사용하여 종류를 구분하였고, value의 갯수를 세어 배열로 만들어주었다.해당 배열의 원소들에게 전부 +1을 해주고, 원소들끼리 곱한 후 마지막에 1을 빼주면 .. [BOJ] 백준 1074 Z (Swift) 문제풀이문제에서 주어진 표를 2 * 2 형태가 될 때 까지 분할을 해주어야 한다.n이 3이라면, 8 x 8 형태일 것이고, 4개로 분할을 하면 중간값이 4일 것이다.즉 중간값은 $2^n % 2$로 볼 수 있다.중간 값이 정해졌다면, 좌표가 어느 공간에 속했는지 확인해주자.y값이 0 ~ mid 사이, x 값이 0 ~ mid 사이y값이 0 ~ mid 사이, x 값이 mid ~ $2^n$ 사이y값이 mid ~ $2^n$ 사이, x 값이 0 ~ mid 사이y값이 mid ~ $2^n$ 사이, x 값이 mid ~ $2^n$ 사이n이 1이 될 때 까지 n을 1씩 줄여 반복을 해주면 y,x 값이 0 ~ 1 사이에 있을 것이다.구간을 찾으면서, 해당 구간의 시작점? 을 누적해서 더해주어야 한다.n이 3이라고 가정했을 때.. [BOJ] 백준 14940 쉬운 최단거리 (Swift) 문제https://www.acmicpc.net/problem/14940 풀이BFS로 쉽게 풀 수 있는 문제이다.다만 문제에 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다. 라는 문장이 있어BFS를 한번 돌리고 난 이후 검사를 해서, 갈 수 있는 땅인데 도달하지 못했다면 -1로 변경시켜주는 과정을 거쳤다.소스코드후기기본적인 BFS 문제였다. [BOJ] 백준 11726 2xn 타일링 (Swift) 문제https://www.acmicpc.net/problem/11726풀이dp로 풀이할 수 있는 문제$f(1) = 1, f(2) = 2$ 이다. 이는 그림을 그리면 쉽게 확인할 수 있다.f(3)을 구해야하는데, 이는 $f(1)$에다가 2x2의 타일을 하나 붙이기 + $f(2)$ 에다가 2x1 타일을 하나 붙인 것과 동일하다.2x2 타일은 || 이렇게 생긴 타일은 붙일 수가 없다.f(3)을 예시로 들면 f(1)이 | 이라고 가정하고, 2x2인 || 타일을 붙인다고 가정할 때, f(2)인 || 타일에 |을 붙이는 것과 동일하기 때문이다.따라서 2x2 타일은 = 와 같인 타일밖에 붙일 수 없다.점화식은 다음과 같다.$f(1) = 1, f(2) = 2$$f(n) = f(n - 1) + f(n - 2)$소스코드후.. 이전 1 2 3 4 ··· 42 다음
