Door

https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 문제가 말하는 것이 어려워서 아래에 예시까지 봐야 이해가 잘 됩니다. 문제가 요구하는 걸 짚어보겠습니다. 0. A[r][c]==k를 만족하는지 보기. (만족하면 time출력) 1. 행과 열 각각 뭐의 갯수가 더 큰 지 파악한다. 2. R연산 C연산 수행 (R연산-->행의 갯수가 더 큰 경우) (C연산-->열의 갯수가 더 큰 경우) 3. 연산을 시켜준 후, 빈 공간에 0을 추가한다. 문..

알고리즘 공부 2022. 4. 22. 02:06

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 가장 전형적인 DFS BFS로 알고리즘을 푸는 문항입니다. 문제 알고리즘은 다음과 같습니다. 1. 벽을 3개까지 세운다 2 바이러스를 퍼트린다. 3. 안전영역 각각을 구한다. 이 문제를 처음 접했다면 dfs로 어떻게 벽을 구할지는 대강 감이 오셔도 그 다음이 문제입니다. 빈칸에 벽을 3개 설치해야하는데 빈칸이 만약 총 25개라면 25C3(25 com 3)의 케이스를 구해야합니다. 이걸 일일이 손으로 볼 순 없..

알고리즘 공부 2022. 4. 21. 21:59

https://www.acmicpc.net/problem/21611 21611번: 마법사 상어와 블리자드 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, ( www.acmicpc.net 구현할 것이 전체적으로 많은 문제입니다. 정리해보면 다음과 같습니다. 1. 마법으로 구슬 제거함 2. 제거한 칸 달팽이로 모으기 3. 같은 게 4개만큼 이어지면 폭파시킴 폭파시키고 2도 수행. (더 이상 제거가 안될 때까지) 4. 달팽이돌면서 그룹화시켜보기 1까지는 할만합니다. 그런데 2부터가 참 난감하죠. 제거한 칸을 달팽이모양대로 모은다?? 와...저걸 어떻게하지....?? ..

알고리즘 공부 2022. 4. 20. 23:38

https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 이 문제는 처음 접했을 때 구현할 것이 상당히 많아 어렵게 느껴집니다. 특히나 이런 류의 문제에 익숙하지 않는다면 좀 많이 빡세게 느껴질 수 있습니다. 여기서 조심할 부분은, 알파에 들어갈 값인데요 알파에 들어갈 값이 '이동하지 않은 남은 모래량' 이라는 문구입니다. 잘못 생각한다면 '나머지를 모두 구해보니 45% 그럼 알파는 55%겠네?' 라고 생각하기 쉽습니다...

알고리즘 공부 2022. 4. 20. 14:08

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 길찾기까지는 쉬운데 조건 붙은 것이 살짝 까다로워서 '맞왜틀'이 반복되는 문제입니다. 사실, 아기상어가 먹을 좌표를 구하는 건 생각보다 간단한 편입니다. BFS DFS로 길찾기하면 그만이니까요. 문제는 '물고기가 상어보다 큰 건 못지나간다' 라는 부분입니다. OK의 경우를 본다면 현재 4 물고기가 목적지 사이에 가로 막혀있으므로 돌아서 가면 이동이 6입니다. 그런데, 무턱대고 '먹을 물고기..

알고리즘 공부 2022. 4. 20. 11:21

https://www.acmicpc.net/problem/23290 23290번: 마법사 상어와 복제 첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향 www.acmicpc.net 저 같은 경우에는 상어이동때문에 애를 많이 먹었습니다. 저거 때문에 예시 하나가 안 풀려서 솔루션까지 참고했는데 제가 틀린 것을 발견하는데 상당히 애를 먹었습니다. 1. 물고기이동 저는 별도의 temp리스트에서 물고기가 이동하는 케이스를 받았습니다. 원래 상어는 graph에 두고 temp에 물고기가 이동하는 걸 그려넣었습니다. 2. 상어이동 노트를 꼼꼼히 봐야하는..

알고리즘 공부 2022. 4. 14. 00:37

https://www.acmicpc.net/problem/22869 22869번: 징검다리 건너기 (small) $N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다. 항상 오른쪽으 www.acmicpc.net 이 문제같은 경우에는 DFS를 활용해서 맨 오른쪽까지 가는 케이스를 구할 수도 있지만 저는 그렇게 구했더니 시간초과 이슈가 떠서 DP로 구현했습니다. (문제 알고리즘 분류가 DP이기도 하고....) dp테이블을 -1로 초기화하고 처음 돌맹이 위치는 1로 넣어줍니다. 그 다음, 1 다음(2부터 N번째 돌까지) 건너갈 수 있는지 여부를 확인..

알고리즘 공부 2022. 4. 13. 22:23

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제는 짧지만 공부할 것은 많은 문제. 이 문제는 DP로 풀어야하는데 처음 보는 입장에서는 많이 난감합니다. 직접 그려보면서 이야기를 하겠습니다. n, k = map(int, input().split()) c = [] dp = [0 for i in range(k + 1)] dp[0] = 1 for i in range(n): c.append(int(input())) for i in c: for j i..

알고리즘 공부 2022. 4. 12. 03:15