백준13 [c++][백준 2169] 로봇 조종하기 백준 2169번: 로봇 조종하기 https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 문제 풀이 이 문제는 DP(Dynamic Programming)로 구현했습니다. 위의 그림에서처럼 한 칸을 계산하기 위해서는 3방향의 값을 고려해야 합니다. 3방향을 모두 고려하여 값을 계산하기 위해 다음과 같은 순서로 연산을 해줍니다. 첫 번째 줄을 계산하기 위해 1~2번의 연산을 하고, 2번째 줄부터 마지막 줄까지 3~5번의 연산을 해 줌으로 dp로 값.. 2022. 4. 19. [c++][백준 1194] 달이 차오른다, 가자. 백준 1194번: 달이 차오른다, 가자. [Gold1] https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 문제 풀이 이 문제는 BFS + 비트마스킹으로 구현했습니다. key를 비트마스킹으로 관리했는데, 아래와 같이 두 가지 경우가 있습니다. 'a' ~ 'f'를 만날 경우 key |= 1 열쇠를 집음 'A' ~ 'F'를 만날 경우 key & 1 열쇠가 있을 경우를 확인 visited는 key의 상태에 따라 관리 -> .. 2022. 4. 14. [c++][백준 2887] 행성 터널 백준 2887번: 행성 터널 [Gold 1] https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 문제 풀이 이 문제는 MST(Minimum Spanning Tree)를 구하는 문제입니다. 처음 문제를 읽으면서 MST를 구해야 하는 것을 파악한 후 Edge의 개수가 매우 많을 것 같아 Kruskal과 Prim 중 Prim을 사용했습니다. 하지만 최대 노드 개수가 100000이기 때문에 Edge 개수는 최대 100000.. 2022. 4. 8. [c++][백준 11401] 이항 계수 3 백준 11401번: 이항 계수 3 [Gold 1] https://www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 이 문제는 주어진 두 수의 이항 계수를 구하여 1,000,000,007(MOD)로 modulo 연산 후 출력해야 한다. 하지만 입력 값의 범위가 크기 때문에 이항 계수 값을 구한 후 modulo 연산을 하게 되면 잘못된 값이 나오게 된다. 또한 매 연산에서 modulo 연산을 해주면 될 것 같지만 이항 계수는 다음 식과 같이 나눗셈 연산이 들어가기 때문에 불가.. 2022. 4. 5. [c++][백준 1016] 제곱 ㄴㄴ 수 백준 1016번: 제곱 ㄴㄴ 수 [Gold 1] https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 문제 풀이 이 문제는 소수를 구할 때 사용하는 에라토스테네스의 체의 원리를 사용해 풀었다. 2부터 시작해서 min ~ max 사이에 있는 제곱수를 체크해야 하는데, 이때 최대 10^12까지 입력이 들어오기 때문에 제곱수를 그대로 arr의 index로 사용하게 되면 메모리가 감당하지 못한다. (arr[10^12]로 선언해야 하기 때문,.. 2022. 3. 28. [c++][java][백준 2357] 최솟값과 최댓값 백준 2357번: 최솟값과 최댓값 [Gold 1] https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 문제 풀이 이 문제는 특정 구간의 최솟값과 최댓값을 찾는 문제로 완전 탐색으로 값을 찾게 되면 시간 초과에 걸리게 된다. 구간 연산에 대한 문제는 세그먼트 트리(Segment Tree)를 생각할 수 있는데, 세그먼트 트리는 각 노드별로 일정 구간의 연산을 가지고 있는 트리를 말한다. 위의 그림이 세그먼트 트리인.. 2022. 3. 25. 이전 1 2 3 다음
