본문 바로가기

PYTHON

[Baekjoon]백준 9465 스티커(실버 1) - Python/C/C++ 문제를 살펴보면 스티커를 떼어내는데, 스티커당 점수가 존재한다그리고 해당 점수가 최대가 되도록 스티커를 떼어내야한다이 문제를 보자말자 dp알고리즘으로 해결해야할 것 같은 느낌이 들었다 sticker[0][i]는 위쪽행, i번째 열의 점수를 저장하고 sticker[1][i]는 아래쪽 행, i번째 열의 점수를 저장한다스티커와 닿아있는 면은 다 떼어지기 때문에 제일 점수가 높은 상황은 지그재그로 떼어내는 것이라 생각할 수 있지만첫번째 예시의 경우 50 50 100 10 40 보다 50 50 100 60이 점수의 합이 더 크다따라서 현재 열의 점수에 이전 열과 전전열에서 올 수 있는 최댓값을 더해 계산해야한다해당 방식으로 계산하면 지그재그만 확인하는 것이 아니라 모든 가능한 선택 경로 중 최대값이 저장된다파이썬.. 더보기
[Baekjoon]백준 21736 헌내기는 친구가 필요해(실버 2) - Python 문제를 살펴보면 어떠한 하나의 위치에서 상하좌우로 움직여 벽을 피해 사람을 찾는 문제이다즉, 해당 문제는 최근들어 자주 사용한 bfs를 사용하여 해결할 수 있다 row, col 변수에 캠퍼스의 크기를 저장하고 campus 리스트에 캠퍼스의 정보를 저장한다이후 for문을 돌면서 도연이가 위치한 곳을 찾고 해당 위치를 기록해준다이렇게 찾은 도연이의 위치를 bfs함수를 통해 이동가능한 공간에 사람이 존재하는지,존재한다면 cnt 변수에 1씩 더해준다이번에 해결할 때에는 visited 리스트를 정의하여 도연이가 이미 만난 사람인지 판단하도록 하였다import sysfrom collections import dequeinput = sys.stdin.readlinedx = [-1, 1, 0, 0]dy = [0, 0,.. 더보기
[Baekjoon]백준 7576 토마토(골드 5) - Python 문제를 살펴보면 익은 토마토 옆으로 토마토가 익어가게 되는데, 대각선이 아닌 바로 옆, 위, 아래만 해당된다따라서 이전 문제에서 주로 사용하였던 dx = [-1, 1, 0, 0], dy = [0, 0, -1, 1]을 사용하면 된다해당 문제에서는 이전에 queue()를 선언할 때, deque([(x, y)])과 같은 방식으로 선언해주었지만, 1인 토마토(익은 토마토)에서 출발해야하기 때문에 append()하는 과정이 추후에 이루어져야한다그래서 이번에는 bfs() 함수에 전달하는 인자 없이 그냥 작성해주면 된다(python)2중 for문을 통해 모든 창고를 확인하며 익은 토마토의 위치를 확인하고 해당 위치를 queue에 추가해준다이후 이전과 동일하게 while queue: 과정을 통해 탐색을 해나가면된다 마.. 더보기
[Baekjoon]백준 7562 나이트의 이동(실버 1) - Python/C/C++ 문제를 살펴보면 이번에는 한 칸씩만 이동한 것과 다르게 체스의 말로 움직이기 때문에 조금 어렵게 느껴질 수는 있으나 dx, dy 배열에서 말이 움직일 수 있는 위치만큼 지정해주면 이전 문제와 동일하다이전에는 dx = [-1, 1, 0, 0], dy = [0, 0, -1, 1]과 같이 지정해주었다면이번에는 dx = [-2, -2, -1, -1, 1, 1, 2, 2], dy = [1, -1, 2, -2, 2, -2, 1, -1]와 같이 지정해주면된다또한, 이번에도 행과 열로 계산이 이루어지기 때문에 x, y와 같은 index 계산에 헷갈리지 않도록 유의해야한다import sysfrom collections import dequeinput = sys.stdin.readlinedx = [-2, -2, -1, -.. 더보기
[Baekjoon]백준 1697 숨바꼭질(실버 1) - Python/C/C++ 문제를 살펴보면 이때까지의 문제 유형과는 사뭇 다르다2차원 배열에서 경로를 찾아나간것과는 다르게 1차원 배열에서 경우의 수를 찾는 문제이다문제의 목표가 수빈이의 위치에서 동생의 위치까지 가는 가장 빠른 시간을 구하는 것이기 때문에 bfs가 가장 효율적이다bfs는 시작점으로부터 거리가 1인 모든 정점, 거리가 2인 모든 정점...과 같은 방식으로 동작하므로목표 지점에 도달하였을 때 그 경로가 최단 경로임을 보장할 수 있다 이전에는 dx = [-1, 1, 0, 0]과 같은 방식으로 방향을 설정하였지만 해당 문제에서는 순간이동(곱하기)도 존재하기 때문에어떻게 해결할지 고민하다가 python에서 for문의 range 부분을 활용하였다for nx in (x-1, x+1, x*2)를 통해 각각의 경우에 대해 확인을.. 더보기
[Baekjoon]백준 2178 미로 탐색(실버 1) - Python/C/C++ 해당 문제를 살펴보면 서로 인접한 이동가능한 칸으로 이동하여 제일 왼쪽 위(0,0)에서제일 오른쪽 아래(n-1, m-1)로 이동하는 가장 적은 경우의 수를 출력하는 문제이다해당 문제의 경우 이전 문제에서 자주 사용하였던 DFS가 아니라 BFS를 사용하여 문제를 해결해야한다DFS는 한 방향으로 끝까지 탐색한 후 다른 경로를 찾아보기 때문에 최단 경로를 찾아야하는 해당 문제에서는 BFS를 사용해야한다 그에 맞게 적절히 코드를 수정하면 다음과 같다dx = [0, 0, -1, 1]dy = [-1, 1, 0, 0]def bfs(x, y): queue = deque([(x, y)]) while queue: x, y = queue.popleft() for i in range(4):.. 더보기
[Baekjoon]백준 1012 유기농 배추(실버 2) - Python/C/C++ 문제를 살펴보면 이전 문제(2667)는 총 몇개가 붙어있고, 붙어있는게 몇 묶음인지 물어보았다면이번에는 입력 자체도 여러번 가능하며 총 몇 묶음인지 확인하는 문제이다따라서, 이전 문제에서 사용한 dfs 함수에서 count 변수를 제거하여 dfs를 구현해야한다dx = [0, 0, -1, 1]dy = [-1, 1, 0, 0]def dfs(x, y): if x = width or y = length: return if field[y][x] == 1: field[y][x] = 0 for i in range(4): nx = x + dx[i] ny = y + dy[i] dfs(nx, ny)해당 함수를 사용하기.. 더보기
[Baekjoon]백준 2667 단지번호붙이기(실버 1) - Python/C/C++ 문제를 살펴보면 지도가 주어지고, 해당 지도에서 연결된 단지를 찾아 출력하는 문제이다.일단 위에서부터 지도를 확인하다가, 1을 발견하면 해당 위치로부터 연결된 모든 집을 탐색해야한다.문제 해결을 위해 DFS를 사용하기로 하였으며, 사용 과정에 있어서 스캔이 완료되면중복 검사의 가능성이 존재하므로 0으로 바꾸어주어야 중복 탐색을 막을 수 있다.DFS를 사용하기위해 dx, dy 배열을 선언하여 방향을 설정해준다이후 앞서 dfs 함수를 선언하고 탐색하였을때 1이 존재한다면 0으로 변환함과 동시에 count 변수에 값을 저장한다import sysinput = sys.stdin.readlinedx = [0, 0, -1, 1]dy = [-1, 1, 0, 0]def dfs(x, y): global count .. 더보기

티스토리툴바