Door

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/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