Door

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu&categoryId=AV5V61LqAf8DFAWu&categoryType=CODE&problemTitle=SW&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=2&&&&&&&&& SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 완전탐색유형. 어떻게하면 시간초과를 줄일까 고민하면서 어떤 좌표에서 bfs를 해줄지 고민하다가 해당 좌표마다 최대의 마름모를 만들고..

알고리즘 공부 2022. 10. 11. 13:58

https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 이 문제는 백트레킹 문제중에서 난이도가 상당히 높은 문제. 우선 제가 초기에 풀었을 때는 '정석(?)'대로 대각선이 비어있는지 확인해주고 비숍을 넣는 방식이었습니다. import sys sys.setrecursionlimit(10**8) N=int(input()) room=[list(map(int,input().split())) for _ in range(N)] ga=[False]*(2*N-1) sa=[F..

알고리즘 공부 2022. 10. 8. 11:16

https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 의외로 이 문제로 헤메는 사람이 많고 저 역시나 제법 오랜 시간 뻘짓했다가 풀었습니다. 예전에 이 문제와 유사하게 밖으로 나가는 경우를 구하는 문제가 있었습니다. 해당 문제의 경우처럼 전체 크기를 h+2 x w+2로 해줬습니다. 기존 입력한 거에서 ['.']*(w+2)행을 위 아래로 추가 각 열 앞뒤에 '.'을 추가해줬습니다. 그럼 사람의 x,y좌표가 0or h+1 0 or w+1이면 탈출. 그런데 제출하고 ..

알고리즘 공부 2022. 10. 8. 00:36

https://www.acmicpc.net/problem/3101 3101번: 토끼의 이동 첫째 줄에 N, K가 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K ≤ 300,000) N은 행렬의 크기, K는 토끼가 점프한 횟수이다. 둘째 줄에는 'U','D','L','R'로 이루어진 문자열이 주어진다. 이 문자열의 길이는 K이며, 토 www.acmicpc.net 이 문제를 보고 '지그재그로 가는 모든 경로를 다 구하자' 라는 마인드를 가지면 바로 시간초과. N이 10만까지 된다면 지그재그 하다가 시간이 다 소요가 됩니다. 결국 해당 좌표지점의 수를 예측해서 더하는 게 관건. 이 부분이 상당히 까다로웠습니다. 수학적 능력이 필요한 부분이라... 생각하기 상당히 어렵습니다. 제 나름대로 스스로 풀어볼려다..

알고리즘 공부 2022. 10. 5. 22:44

https://www.acmicpc.net/problem/11567 11567번: 선진이의 겨울 왕국 첫 번째 테스트 케이스의 경우에는 (1,6) → (2,6) → (3,6) → (4,6) → (4,5) → (4,4) → (4,3) → (4,2) → (4,1) → (3,1) → (2,1) → (2,2) → (2,3) → (1,3) → (1,2) → (2,2) 의 순서로 가면 탈출이 가능하다. www.acmicpc.net 문제 조건이 헷갈려서 체감적으로 까다로울 수 있는 문제. 이 문제에서 주의할 점들. 1. 도착점이 이미 X일 수 있다는 점. 2. 움직일 때 추락이 가능하다는 점. 3. 출발,도착점이 같을 수 있다는 점. 여기서 2번이 직관적으로 와닿지 않는데요. 그냥 일반적인 탈출만 생각하면 '시작점과..

알고리즘 공부 2022. 10. 4. 10:34

https://www.acmicpc.net/problem/12908 12908번: 텔레포트 3 첫째 줄에 xs와 ys가, 둘째 줄에 xe, ye가 주어진다. (0 ≤ xs, ys, xe, ye ≤ 1,000,000,000) 셋째 줄부터 세 개의 줄에는 텔레포트의 정보 x1, y1, x2, y2가 주어진다. (0 ≤ x1, y1, x2, y2 ≤ 1,000,000,000) 입력으로 주 www.acmicpc.net 이 문제는 언뜻보면 bfs같았지만 좀 다르게 풀어야했습니다. #백준 12908번 텔레포트3 from collections import deque dx=[0,0,1,-1] dy=[1,-1,0,0] sx,sy=map(int,input().split()) ex,ey=map(int,input().spli..

알고리즘 공부 2022. 10. 3. 17:40

https://www.acmicpc.net/problem/1726 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net 나온지 좀 된 문제인만큼 푸는 사람도 많은 문제. 그리고 고통받는 사람도 참 많은 문제. 이 문제는 단순한 bfs로 풀면 안 됩니다. '방향'이 중요하기 때문. 방향에 따라서 움직임이 카운트가 되기 때문에 이를 신경써줘야합니다. 주의할 부분들 살펴보면 1. K이동-->최대 3개까지 이동이 가능합니다. K이동시 벽을 만나면 멈춥니다. 단, 이전에 방문한 곳을 또 지나칠 수는 있습니다. 만약 0 0 0 인데, ..

알고리즘 공부 2022. 9. 29. 23:42

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 상당히 까다로웠던 dp문제. DP+길찾기가 합쳐져서 어려웠습니다. #백준 1520번 내리막길 #시간초과 코드 from collections import deque dx=[0,0,1,-1] dy=[1,-1,0,0] N,M=map(int,input().split()) room=[list(map(int,input().split())) for _ in range(N)] dp=[[0]*M for _ in ran..

알고리즘 공부 2022. 9. 29. 11:05