본문 바로가기

cpp

[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]백준 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 .. 더보기
[Baekjoon]백준 2293 동전 1(골드 4) - Python, C++ 문제를 살펴보면 그리디 알고리즘의 거스름돈 문제가 약간 생각나게 되는 문제이다동적 프로그래밍 알고리즘의 핵심은 점화식을 찾는 것이다그래서 점화식을 어떻게 만들어서 어떻게 값을 넣을지 고민해보았는데, index를 n원을 만드는 경우의 수로설정하여 점화식을 찾아보고자 노력하였다 예를 들어 dp[2]의 경우라면 2원을 만드는 경우의 수, dp[5]라면 5원을 만드는 경우의 수가 들어가도록 설정하였다이제 이 값을 어떻게 설정할 지가 고민인데, 일단 예제를 보고 직접 값을 넣어가면서 규칙을 찾아보았다우선, 동전 1을 통해 만들수 있는 경우의 수는 모두 1이다이후 동전 2를 사용한다고 가정할 때, 동전 2를 사용해서 1원을 만들수는 없기 때문에dp[1]의 값은 더이상 갱신되지 않고 값이 확정된다는 사실을 알 수 있.. 더보기
[Baekjoon]백준 2629 양팔저울(골드 3) - Python, C++ 해당 문제는 해당 추의 개수를 가지고 원하는 무게를 만들수 있는지에 대해 물어보는 문제이다예제 2번을 보면 구슬 4개를 가지고 1, 4, 10을 만들어야한다1의 경우 3과 2, 4의 경우 3, 3과 2로 만들수 있고 10의 경우 2, 3, 3, 3의 추로는 만들수 없기 때문에 N이 출력된다 일단 dp라는 배열에 어떠한 값을 넣을지 고민해보았다 사실상 이것이 동적 프로그래밍의 핵심이다dp[사용한 추의 개수][무게 차이]를 기준으로 1이라는 값을 넣어주고 나머지는 0으로 초기화한다그렇게 하게 되면 함수를 재귀적으로 호출할 때 1인 경우 바로 return을 함으로써 불필요한 계산을 하지 않는다또한 구슬이 기존에 입력된 수보다 더 큰 경우에도 바로 return을 하여준다def sol(num, wg): if.. 더보기

티스토리툴바