본문 바로가기

전체 글108

[UCPC] B번 던전 지도, 백준 19543 https://www.acmicpc.net/problem/19543 19543번: 던전 지도 첫 번째 줄에 던전의 행 개수 $N$, 열 개수 $M$, 블록의 종류 $K$가 공백으로 구분되어 주어진다. ($1 \leq N, M \leq 200\ 000$, $1 \leq K \leq 26$) 두 번째 줄부터 $K$개의 줄에 R과 U로만 이루어진 길이 $M$의 문� www.acmicpc.net 문제를 잘 이해하면 쉽게 풀 수 있습니다. 위에서 i번째 행이 i번째 알파벳에 대응되는 행입니다. 아래의 예제에서 A에 대응되는건 RRURRR 이고, B는 RRURRRU, C는 RRRRRRR입니다. 3 7 3 RRRURRR RRURRRU RRRRRRR CBA 주어진 길이 n의 k개의 문자로 이루어진 지도를 그리면 j번째.. 2020. 8. 18.
머지 소트, 머지 소트 트리 및 관련 백준 문제 풀이 머지 소트 트리를 이용한 백준 문제 풀이 수열과 쿼리 1 , 수열과 쿼리 3 , 트리와 색깔 , K번째 수 는 맨 아래를 참고해주세요. 코드 스포일러를 방지하기 위해 접은 글로 풀이를 남겼습니다. 알고리즘에서 c++의 algorithm 헤더에 있는 내장 sort함수는 코드의 간결성과 실수를 줄여줍니다. 그러나, 내장함수가 있다고해서 정렬 알고리즘을 구현할줄 몰라도 되는 것은 아닙니다. 아래의 버블 소트는 알고리즘 입문자들이 대부분 알고있는 정렬 알고리즘으로 O(N^2)의 비효율적인 복잡도로 작업을 수행합니다. 모든 수를 비교하면서 큰 수를 뒤로 보내는 단순한 방식으로 동작합니다. // 버블 소트 for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) {.. 2020. 8. 17.
[BOJ] 백준 10830번: 행렬 제곱 (빠른 거듭 제곱) 먼저 우리는 빠른 거듭 제곱 알고리즘을 알고있습니다. pow(a,y), 즉 a^y 를 구할때 만약 y가 홀수면 a * a^y/2*a^y/2로 분해하여 짝수 거듭 제곱의 반을 구해가면서 O(lgY)의 복잡도로 구할 수 있습니다. int pow(int a, int y) { int x = 1; while (y) { if (y & 1) { x *= a; } a *= a; y /= 2; } return x; } math.h 헤더의 내장 pow를 사용하지 않고 직접 구현하여 쓰는 이유는, 몇몇 문제에서 특정 수로 나눈 나머지 값을 요구하기 때문입니다. 이유는 답이 너무 커지거나 하는 경우에, 보통 1,000,000,007 (1e9+7)와 같은 소수로 나눈 나머지 값을 요구합니다. 소수는 어떠한 수와도 나누어 떨어지.. 2020. 8. 17.
[알고스팟] 종만북 게임판 덮기 ID: BOARDCOVER https://algospot.com/judge/submission/recent/ algospot.com :: 답안 목록 683263 JUMPGAME Moongthy cpp 800B 컴파일 실패 13분 전 algospot.com 현재 좌표 x, y 가 비어있다면 x,y를 기준으로 블록을 놓을 수 있는 경우의 수는 4가지가 있습니다. 먼저 맨 위쪽이면서 가장 맨 왼쪽에 블럭을 놓을 수 잇는 게임판 좌표 x,y를 찾아 4가지 블록에 대하여 가능한 블록으로 덮고 DFS를 진행하면 됩니다. cover 함수를 만들어서 flag가 1이면 해당 좌표에 블록을 두고 0이면 둔 블록을 해제 하는 식으로 방문 배열 역할을 하게끔 만들었습니다. (이런 구현 이슈가 있는 문제들은 모듈화 시켜놓는 것이 좋습니다.) 또한 게임판.. 2020. 8. 17.
[알고스팟] 종만북 소풍 : PICNIC https://algospot.com/judge/problem/read/PICNIC algospot.com :: PICNIC 소풍 문제 정보 문제 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 algospot.com 모든 친구가 서로 친한 친구의 쌍을 이루는 조합의 개수를 찾는 문제입니다. n이 10이므로 모든 경우를 완전 탐색을 통해 찾아 가면서 가능한 경우만 세어주면 됩니다. 예를 들어 n이 6인경우 친구관계가 모두 친하다고 가정한다면, (1,2),(3,4),(5,6) , (1,3),(2,4),(5,6) ... 등 이 있습니다. 그러나 (1,2)와 (2,1) 쌍은 같으며 (3,4),(.. 2020. 8. 17.
오일러 𝜑(피 또는 파이) 함수, 서로소 개수 구하기 서로소란 1 을 제외하고 공약수가 없는 두 수의 관계입니다. 오일러 피함수 φ(n)은 n이하의 자연수 중 n과 서로소인 자연수의 개수를 의미하는 함수입니다. 예를 들어 φ(6)은 2로 1과 5의 서로소가 있음을 의미합니다. 모든 자연수는 소수들의 (prime) 곱으로 표현 할 수 있습니다. 예를들어 16은 2^4 로 표현할 수 있고 15는 3^1 * 5^1 로 나타낼 수 있습니다. φ(16)은 2, 4, 6, 8, 10, 12, 14, 16을 제외한 나머지 자연수와 서로소입니다. 여기서 알 수 있는 사실은, 자연수를 구성하는 소수들의 배수는 전부 서로소가 아닙니다. 즉, φ(16) = 16 - (16/2) = 8개로 구할 수 있습니다. ( n 이하의 k의 배수의 개수는 n/k로 구할 수 있습니다, 나머지.. 2020. 8. 13.
[BOJ] 백준 1028번: 다이아몬드 광산 https://www.acmicpc.net/problem/1028 1028번: 다이아몬드 광산 첫째 줄에 R과 C가 주어진다. R과 C는 750보다 작거나 같은 자연수이다. 둘째 줄부터 R개의 줄에는 다이아몬드 광산의 모양이 주어진다. www.acmicpc.net R, C 가 750으로 (i, j) 좌표에서 우측 하단으로의 대각선 길이 DP[i][j][0], 좌측 하단으로의 대각선 길이 DP[i][j][1], 좌측 상단으로의 각선 길이 DP[i][j][2], 우측 상단으로의 대각선길이를 구해놓고 모든 좌표에 대하여 O(R*C*750*4)의 복잡도로 가능한 다이아몬드 크기를 구할 수 있습니다. (시간초과가 날것 같지만 가지치기를 통해 충분히 시간을 줄일 수 있습니다.) #include #include #i.. 2020. 8. 12.
[BOJ] 백준 1027번: 고층 건물 https://www.acmicpc.net/problem/1027 1027번: 고층 건물 세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작)�� www.acmicpc.net 기울기를 이용한 문제입니다. ccw 알고리즘을 이용하여 세점의 방향성으로도 풀 수 있습니다. 여기 참고 n; for (int i = 0; i > a[i]; } for (int i = 0; i -1; j--) { if (j .. 2020. 8. 12.
[BOJ] 백준 1026번: 보물 https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거� www.acmicpc.net B를 재배열하지 말라고 하지만, 그 말을 듣지 마세요. #include #include #include #include using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, a[51],b[51]; cin >> n; for (i.. 2020. 8. 12.

티스토리툴바