Door

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 전형적인 BFS를 이용한 풀이입니다. 이런 유형의 문제는 풀이방법을 모른다면 체감난이도가 확 올라갈 수 있습니다. 그 이유는 '최소일수'를 구하는 것 때문이죠. 이 문제를 BFS로 푼다, 아니면 하다못해 DFS로 푼다는 것까지는 문제 유형을 읽다보면 생각이 어느정도 납니다. '토마토가 익을 때는 인접한 왼쪽 오른쪽만 익히는 구나. 그럼 토마토가 익는 걸 기점으로 그래프를 이동시키면..

알고리즘 공부 2022. 6. 22. 10:56

https://www.acmicpc.net/problem/22858 22858번: 원상 복구 (small) 수가 적혀있는 $P_1, P_2, ..., P_N$ $N$개의 카드가 있다. 1부터 N까지 수가 하나씩 존재하는 $D_1, D_2, ... , D_i , ... D_N$ 가 있다. 이때 $D_i$는 $P_{D_i}$ 값을 $i$ 번째로 가지고 오는 것을 의미한다. 이러한 www.acmicpc.net 문제를 읽으면 다소 복잡해보일 수 있습니다. 한번 이 문제의 요구를 예시와 함께 보겠습니다. 저는 역으로 구해준다는 걸로 이해했습니다. 예시1의 경우를 살펴보면 섞는 패턴이 4 3 1 2 5입니다. 그럼 K=1일 때는 첫번째 숫자가 4번째로. 두번째 숫자가 3번째로. 세번째 숫자가 1번재로. 네번째 숫자..

알고리즘 공부 2022. 6. 7. 18:38

https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 미세먼지를 공기청정기로 돌려주는 것이 까다로웠던 문항. 이 알고리즘에서 구현해야할 것은 2가지입니다. 1. 미세먼지 분배 2. 공기청정기 바람 미세먼지 분배부터 보겠습니다. 문제에서 '동시에'분배된다 라는 것에 유의하셔야합니다. '동시에 분배한다'라고 나오시면 별도의 리스트를 만든 후 분배를 하시는 걸 권장드립니다. 제가 처음 알고리즘 문제를 풀 때 흔히했던 실수입니다. 동시에 퍼진다고 했는데 ..

알고리즘 공부 2022. 4. 27. 00:43

https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 이 문제같은 경우에는 간단하게 deque의 rotate함수를 활용하는 방식이 있습니다만 공부의 관점에서 빡구현을 해봤습니다. 이 문제가 요구하는 사항은 다음과 같습니다. 1. 컨베이어벨트와 로봇을 돌린다. 2. 로봇을 이동 3. 새로운 로봇 투입 이 세가지를 반복해주는 작업을 겨쳐줍니다. 먼저, 컨베이어 밸트를 옮겨주는 작업, 여기서 end는 2*N입니다. #1.밸트위의 로봇..

알고리즘 공부 2022. 4. 24. 15:52

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 이 문제는 DFS로도 풀수는 있지만 일반적인 경우에는 시간초과가 발생합니다. 사실상 이 문제는 combination을 쓰라고 거의 유도한 문제에 가깝습니다. #백준 14899번 스타트와 링크 from itertools import combinations N=int(input()) graph=[list(map(int,input().split())) for _ in range(N)] numbers=[i for i in r..

알고리즘 공부 2022. 4. 24. 12:21

https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 난이도 대비 정답률은 높았던 문제. 아마 널리 알려진 기출이라 '풀이보고 적어서 내야지' 하는 사람이 많았나...하는 예상이 듭니다만... 이 문제가 풀려있고 정답률도 60%대이길래 어 겁나 쉬운가보구나... 했더니 낑낑댔습니다. 문제 난이도 확인했더니 골드2.... 이 문제에서 구해줘야할 것은 다음과 같습니다. 1. 상어가 물고기 먹기 2. 물고기 이동 3. 상어가 이동 ; 여..

알고리즘 공부 2022. 4. 23. 23:40

https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 톱니바퀴가 돌아가는 걸 구하는 문제입니다. 이 문제는 간단하게 rotate 함수를 활용해도 되지만 공부의 관점에서 다른 방식을 사용했습니다. 저는 list로 풀이라는 법 deque로 풀이하는 법 2가지를 보여드릴 건데요 우선 큰 틀에서 먼저 접근해보겠습니다. 우선, 바퀴를 돌리고 양 옆의 바퀴를 보는 것입니다. 돌릴 바퀴를 기준으로 돌릴바퀴[2] 오른쪽[6] 돌릴바퀴[6] 왼쪽[2] 각각을 ..

카테고리 없음 2022. 4. 23. 16:17

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