Door

https://www.acmicpc.net/problem/1113 1113번: 수영장 만들기 지민이는 수영장을 만들려고 한다. 수영장을 만들 곳의 크기는 N*M이고, 각 칸은 직육면체이다. 따라서, 각 칸의 직육면체의 높이가 쓰여 있는 다음과 같은 땅을 생각할 수 있다. 16661 61116 16661 이 www.acmicpc.net 상당히 까다로웠던 문제. 문제 자체가 어려워서 많이 해매었고 구글링을 통해서 해결할 수 있었습니다. https://injae-kim.github.io/problem_solving/2020/02/15/baekjoon-1113.html Injae's devlog 현실의 문제를 해결하는 엔지니어 injae-kim.github.io 제가 참고한 페이지입니다. 이 분은 발상을 다르게..

알고리즘 공부 2022. 9. 10. 18:13

https://www.acmicpc.net/problem/1944 1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net 이 문제를 처음 풀때는 이렇게 생각했습니다. 1. 로봇을 기준으로 key까지의 거리를 구한다 2. 각 key들간의 거리를 구한다. 1까지는 그렇다치더라도 2에서 시간초과가 엄청날 것으로 보였습니다. key의 갯수가 250개가 된다하면 1->2~250번째 key까지의 거리 2->2를 제외한 나머지 키들까지의 거리 3->..... 이렇게 구하다보면.... 역시나 시간초과..

알고리즘 공부 2022. 9. 8. 00:25

https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 이 문제는 좌표평면에 대해서 다르게 관점을 가지게 해준 좋은 문제입니다. 우선, 이 문제는 백트레킹을 공부하셨더라면 '백트레킹쓰면서 퍼즐 좌표를 다 받아야하는건가?' 라는 생각이 자연스럽게 듭니다. 물론 이 방식이 틀린 방법은 아니지만 메모리를 확~~넘게 됩니다. 그럼 어떻게 숫자를 저장하지?? 구글링해본 결과 퍼즈를 숫자로 바꾸면서 구할 수 있었습니다. 파이썬은 딕셔너리에 숫자를 저장해주어서 dict[숫자]=걸리는 시간 이렇게 저장해주면 문제를 풀어낼 수 있었습니다. #백..

알고리즘 공부 2022. 9. 5. 22:11

https://www.acmicpc.net/problem/2021 2021번: 최소 환승 경로 첫째 줄에 역의 개수 N(1≤N≤100,000), 노선의 개수 L(1≤L≤100,000)이 주어진다. 다음 L개의 줄에는 각 노선이 지나는 역이 순서대로 주어지며 각 줄의 마지막에는 -1이 주어진다. 마지막 줄에는 출발 www.acmicpc.net 이 문제에서 구현해야할 부분은 '어떻게 경로가 만나는 걸 표현할지'입니다. 처음에 저같은 경우에는 경로의 숫자 하나하나를 탐색하면서 다른 루트에 있는지 확인하는 쪽으로 갔습니다. 근데 이 방식은 경로가 많아질수록 시간초과가 어마어마하게 된다는 단점이 있습니다. 그래서 미리미리미리 '어떤 역은 몇번 경로랑 겹친다' 라는 걸 구현해주면서 문제를 풀었습니다. #백준 202..

알고리즘 공부 2022. 9. 5. 00:00

https://www.acmicpc.net/problem/10711 10711번: 모래성 첫째 줄에는 모래성의 가로세로 격자 크기 H, W가 주어진다. (1 ≤ H, W ≤ 1,000) 그 다음 H줄에 걸쳐 W개의 문자로 모래성의 상태를 나타내는 문자가 들어온다. 각 문자는 1~9 사이의 숫자, 또는 '.' 이 www.acmicpc.net 이 문제는 구글링하면서 허탈했던 문제. 아니...뭐야...이렇게 쉬웠다고? 하지만 정작 문제를 처음 접할때는 많이 낑낑댔습니다. 체감상 어렵게 느껴진 부분은 8방향의 좌표를 다 보고 모래성을 무너트리는 것. H와 W의 범위값이 최대 1000이라고 되어있으니 첫,마지막 행과 열을 제외하더라도 최대 999x999x8의 경우를 계산해야합니다. 모래성이 없는 경우는 스킵하더라..

알고리즘 공부 2022. 9. 4. 21:28

https://www.acmicpc.net/problem/1400 1400번: 화물차 입력은 여러 개의 테스트 케이스로 구성된다. 각 테스트 케이스의 첫째 줄에는 두 개의 정수 m과 n이 주어진다, 여기서 m은 지도를 나타내는 행렬의 행의 크기이고 n은 열의 크기이다(2 ≤ m, n ≤ 2 www.acmicpc.net 이 문제는 억울함이 많았던...ㅠ 우선 처음에 생각했던 풀이는 '교차로를 만날 때 바로 신호등이 켜지는 경우와 신호가 켜지기 기다렸다가 건너는 케이스 두 가지를 구현한다' 였습니다. #백준 1400번 화물차 from heapq import heappop,heappush dx=[0,1,0,-1] dy=[1,0,-1,0] while True: m,n=map(int,input().split())..

알고리즘 공부 2022. 8. 31. 21:51

https://www.acmicpc.net/problem/1938 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4 ≤ N ≤ 50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문 www.acmicpc.net 이 문제를 들었던 생각들. '통나무를 어떻게 옮기지???' 3개를 한번에 옮겨? 3개를 deque에 받고 옮겨? 이렇게 생각하니 문제가 전혀 안풀렸습니다. 그러다가 질문하기 글을 봤는데 의외로 간단한 해결책이 있었습니다. '중앙점을 중심으로 옮긴다' 중앙점 x,y를 기준으로 가로,세로인지 확인해주고 그걸 옮긴다는 개념이었습니다. 그렇게 머릿속에 박고 다시 시작하니 문제가 체..

알고리즘 공부 2022. 8. 30. 16:07

https://www.acmicpc.net/problem/22949 22949번: 회전 미로 탐색 $4k$×$4k$의 크기인 미로가 있다. 이 미로의 최상단 왼쪽을 $(1, 1)$, 최하단 오른쪽을 $(4k, 4k)$로 하자. $\{(y, x) | 4×i < y ≤ 4×(i+1), 4×j < x ≤ 4×(j+1), (0 ≤ i, j < k)\}$ 를 만족하는 영역이 하나의 구역으 www.acmicpc.net 문제를 보자마자 이게 뭐지?? 하면서 당황했던 문제. 가장 문제에서 난감했던 부분은 '배열을 돌리고 해당 구역 이외에는 원상복귀시킨다' 구역이 계속 바뀐다고? 그러면 dfs로 풀어야하는거 아닌가? 구역을 계속 업데이트해주고... 하...이게 뭔 쌉소리지?? https://nahwasa.com/entr..

알고리즘 공부 2022. 8. 30. 11:03