(python) 아이디어 일단 연속된 숫자가 L 번 이상 나와야 경사로를 놓을 수 있고, 1칸 차이여야 경사로를 배치해서 지나갈 수 있습니다. 핵심이 되는 아이디어는 "길의 표현법을 수정해서 연속된 번호의 횟수로 표현하겠다" 입니다. (층,연속횟수) 의 배열로 나타냈습니다. (지금은 튜플로 표현했지만 뒤에서 연속횟수를 변경해주어야해서 코드 상에서는 list 를 사용했습니다.) 예를 들어서 [3 2 1 1 2 3] 를 [(3,1), (2,1), (1,2), (2,1), (3,1)] 로 표현을 바꿔주는겁니다. 이렇게 바꾸면서 1. 층이 바뀌는 부분을 바로 알 수 있다. 2.경사로를 놓을 수 있는지 바로 체크할 수 있다. 두가지 장점이 생깁니다. 여기에서 층이 바뀔때마다 1층씩 변경됐는지, 1층 변경됐으면 경..
(python) 백트래킹 디테일 구현 모듈을 잘 쪼개고, 백트래킹 함수를 잘 작성해주면 되는 문제였습니다. 이전에 작성한 청소년 상어와 결이 비슷합니다. 백트래킹 관련된 부분은 이 글로 대신합니다. https://jamong-5.tistory.com/53 백준 #19236 - [G2] 청소년 상어 : 구현, back tracking (python3) 아이디어 까다로운 상어 시리즈의 청소년 버전입니다. 이 문제는 시뮬레이션의 조건이 많기 떄문에 코딩 과정에서 스텝이 꼬이지 않도록 기능을 잘 분리해서 접근해주는게 좋습니다. 저 jamong-5.tistory.com 모듈화 아이디어 이 문제의 모듈화 같은 경우, "상하좌우 각 방향의 전체 칸을 모두 탐색한다" 라는 수행이 가장 기본이 되고, 이걸 방향마다 조합..
https://www.acmicpc.net/problem/8979 8979번: 올림픽 입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 www.acmicpc.net (python) 파이썬에서 제공하는 sort 를 활용하여 간단하게 해결해볼 수 있습니다. https://jamong-5.tistory.com/55 [sort] 파이썬에서 커스텀한 기준으로 이터러블한 객체 정렬하기 key 파이썬에서 제공하는 sorted 기능은 key 파라미터로 커스텀한 기준을 부여하여 정렬할 수 있습니다. 파이썬 sort 관련 독스에서도 이를 확인할 수 있습니..
https://www.acmicpc.net/problem/20040 (python3) 그래프의 대표 유형중 하나인 사이클 존재 유무 탐색 문제입니다. 그래프 사이클 탐색의 경우 유니온 파인드 알고리즘으로 해결할 수 있습니다. 유니온 파인드 이어진 점들을 하나의 그룹으로 표현하는 방식입니다. 가장 직관적인 접근으로는 그룹 A와 B가 합쳐지는 경우 이렇게 모든 점들을 탐색하면서 A 를 B 로 편입시키는 방법입니다. 다만 이 방법을 사용하게 되면 새로운 선이 하나 추가될때 마다 모든 점의 그룹 상태를 모두 확인하여 바꿔야하기에 점이 많아질수록 연산 부담이 커집니다. 이 연산을 획기적으로 줄이는 방식이 union find 가 되겠습니다. 핵심 아이디어는 각 점은 자신의 부모 노드만 저장하고 있고, 필요시마다 해..
(python3) 아이디어 까다로운 상어 시리즈의 청소년 버전입니다. 이 문제는 시뮬레이션의 조건이 많기 떄문에 코딩 과정에서 스텝이 꼬이지 않도록 기능을 잘 분리해서 접근해주는게 좋습니다. 저는 위치가 2차원 행렬로 표현되는 경우 x,y 보다 r,c 를 사용하는게 명료해서 더 선호합니다. 방향 역시 1~8 의 숫자로 문제에서 주어졌지만 배열로 접근할때의 편의성을 위해 0~7 로 변환하여 사용했습니다. 이런 디테일한 변수 설정들이 헷갈리지 않도록 메모하거나 체계를 잡아두는게 좋은 것 같습니다. 상어가 이동할 수 있는 모든 경우의 수를 탐색해야하고, 이전의 선택 뒤에 다음 선택지가 가지치듯 갈라지는게 반복되기 때문에 백트레킹을 사용하는게 좋습니다. 재귀를 활용해서 단순하게 구현이 가능합니다. 백트래킹은 트..
(python3) 구현 아이디어 각 기능을 구현한 함수명을 함께 작성했습니다. 1. 벽 3개를 세울 수 있는 모든 방법을 찾아야 합니다. next() 는 바로 다음 빈칸을 찾습니다. next_wall() 에서는 다음 벽 3개 조합을 찾습니다. 3번 벽을 한칸 다음으로 옮겨보고, 옮길 공간이 없으면 그 2번 벽을 한칸 다음으로, 3번 벽은 2번 벽 바로 다음으로 배치합니다. 이때 3번 벽이 또 갈 곳이 없다면 1번 벽을 한칸 다음으로 옮기고 그 다음에 2번, 그 다음에 3번 벽을 배치합니다. 이때 3번 벽을 배치할 공간이 없으면 모든 벽의 조합을 다 확인해본 꼴이 됩니다. 2. 벽을 세우고, 맨 처음 배치되어 있는 모든 바이러스에 대해 dfs 를 수행하여 바이러스가 다 퍼진 뒤의 상태를 확인합니다. (in..
