본문 바로가기

알고리즘74

[BFS] 백준 1600번 : 말이 되고픈 원숭이 - 파이썬 Python https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 생각하기 처음에는 말의 움직임과 원숭이 본래 움직임을 통합하여 BFS로 풀고자 하였다. 하지만 간과한 사안이 있었다. 말의 움직임과 원숭이 본래 움직임이 전혀 다른 패턴이기 때문에 원숭이의 본래 움직임으로 방문한 칸을 나중에 말의 움직임으로 더 짧은 시간에 방문할 수 있다는 점이었다. 만약 움직임의 패턴이 다른 경우, 칸까지 움직인 최소 거리를 하나의 visited 배열에 넣는 방.. 2022. 3. 10.
코딩테스트 필수 파이썬 Sort 메소드 정리! 정렬 sort() list에 대하여 정렬 메소드를 사용할 수 있다 해당 메소드는 list의 내장 메소드로 in-place 방식으로 정렬을 시켜준다 즉, 대상 list 자체를 바꿔버린다 return 값은 None 리스트.sort(reverse=True) : default는 오름차순이며, reverse가 True인 경우에는 내림차순으로 정렬됨 리스트.sort(key=?) : key에 저장된 메소드의 결과를 가지고 정렬함 sorted() 모든 iterable에 대하여 정렬을 만드는 iterable의 내장 메소드 즉, 원본을 변경하지 않고 새로운 정렬된 이터러블을 반환 위의 sort()는 list에만 적용되지만 sorted는 모든 iterable에 적용된다 sorted(이터러블, reverse=True) : d.. 2022. 3. 7.
[구현] 백준 17140 : 이차워 배열과 연산 - 파이썬 Python https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net R 연산과 C 연산을 나누어서 생각했다 각 연산에서의 진행 과정은 아래와 같다 모든 row (R연산) 혹은 col (C연산)에 대해 각 수의 개수 카운팅 하면서 dictionary에 추가 dictionary를 tuple로 풀어서 sort (1 idx 우선, 2 idx 다음) sort된 튜플을 풀어서 새로운 A로 생성 col_cnt (C연산) 혹은 row_cnt (R연산)을 갱신 R,C.. 2022. 3. 7.
[BFS] 백준 2234 : 성곽 - 파이썬 Python https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 생각하기 각 칸의 테두리를 기준으로 구역을 나누는 것이므로 각 칸을 돌면서 해당 칸이 구역에 속하는지, 속하지 않는지를 판단하면 되는 방법이라고 생각했다 BFS를 사용하여 칸들을 돌아보기로 했다 세가지 문제에 대한 답을 풀어야 하는데 1. 성에 있는 방의 개수 각 칸에 대한 BFS를 돌면서 더이상 갈 곳이 없으면 방의 개수를 증가시킨다 2. 가장 넓은 방의 넓이 1번의 방법을 수행하면서 BF.. 2022. 2. 23.

티스토리툴바