Algorithm

🗂️ 문제문제김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시작했다. 의심을 피했다고 생각한 형택이는 다시 게임을 켰다. 그 때 형택이는 잠시 코딩을 하는 사이에 자신의 게임 실력이 눈에 띄게 향상된 것을 알았다.이제 형택이는 앞으로의 모든 게임에서 지지 않는다. 하지만, 형택이는 게임 기록을 삭제 할 수 없기 때문에, 자신의 못하던 예전 기록이 현재 자신의 엄청난 실력을 증명하지 못한다고 생각했다.게임 기록은 다음과 같이 생겼다.게임 횟수 : X이긴 게임 : Y (Z%)Z는 형택이의 승률이고, 소수점은 버린다. 예를 들어, X=53, Y=47이라..

🗂️ 문제문제현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 하였다. 현우는 통장에서 K원을 인출하며, 통장에서 뺀 돈으로 하루를 보낼 수 있으면 그대로 사용하고, 모자라게 되면 남은 금액은 통장에 집어넣고 다시 K원을 인출한다. 다만 현우는 M이라는 숫자를 좋아하기 때문에, 정확히 M번을 맞추기 위해서 남은 금액이 그날 사용할 금액보다 많더라도 남은 금액은 통장에 집어넣고 다시 K원을 인출할 수 있다. 현우는 돈을 아끼기 위해 인출 금액 K를 최소화하기로 하였다. 현우가 필요한 최소 금액 K를 계산하는 프로그램을 작성하시오.입력1번째 줄에는 N과 M이 공백으로 ..

🗂️ 문제https://www.acmicpc.net/problem/2512 💡 접근법총 예산이 예정 예산을 초과할 경우 예산의 상한액을 설정해야 하며, 이때 이분탐색을 사용한다.하지만 만약 모든 예산이 배정될 수 있는 경우에는 상한액을 설정할 필요가 없으니 예산의 최댓값을 리턴한다. 이분탐색을 위해 low=1, high는 예산들 중 최댓값으로 설정한다. 이때 mid를 통해 상한액을 정하고,상한액보다 적은 예산은 그대로 예산을 적용하되, 상한액을 초과하는 예산은 상한액으로 금액을 산정하여 예산의 합을 계산한다. 만약 예산의 합이 총 예산보다 크다면, 상한액을 더 내려야 하므로 high 값을 mid-1로 조정한다. 만약 예산의 합이 총 예산보다 작다면, 이는 상한액을 더 올려야 하므로 low 값을 mid..

🗂️ 문제링크: https://www.acmicpc.net/problem/10026 💡 접근법적록색약인 경우 R과 G를 같은 색으로 취급한다.따라서 BFS를 일반 BFS와 적록색약을 처리하는 BFS 두 함수를 정의하고, 적록색약을 처리하는 BFS 함수에서(color == "R" or color == "G") and (maps[nx][ny] == "R" or maps[nx][ny] == "G") 조건을 통해 R과 G를 같은 색으로 처리한다. 아니면, 적록색약용 맵(R을 모두 G로 변경)을 따로 생성하여 정상인을 처리할 때와 동일한 BFS를 사용할 수도 있다. 😎 내 코드(1) 적록색약 유무에 따른 BFS 함수 분리import sysfrom collections import dequeN = int(sy..

🗂️ 문제https://www.acmicpc.net/problem/2468 💡 접근법영역의 최대 높이를 구한 뒤 0부터 최대높이까지 모든 경우에 대해 안전한 영역의 수를 센다. 이때 안전한 영역의 수를 세기 위해 DFS나 BFS를 통해 지도를 탐색하여 특정 높이보다 해당 영역의 높이가 높다면(maps[nx][ny] > m) 탐색을 계속한다. 그리고 최종적으로 영역의 개수의 최댓값을 출력한다. 또한, 상하좌우로 이어진 것을 하나의 영역으로 보기 때문에 BFS를 썼을 경우에 성능을 더 최적화할 수 있다. 😎 내 코드import syssys.setrecursionlimit(10**6)N = int(sys.stdin.readline())maps = []max_value = 0for _ in range(N)..

🗂️ 문제링크: https://www.acmicpc.net/problem/4963  💡 접근법섬의 개수를 세기 위해 DFS를 통해 탐색한다.이때 상하좌우뿐만 아니라 대각선으로 연결되어 있어도 하나의 섬으로 본다. 따라서 이를 고려하여 탐색해야 한다. 또한 파이썬의 최대 재귀 깊이가 1000이므로 의도적으로 깊이를 늘려줘야 한다. 그렇지 않으면 RecursionError가 발생한다. 😎 내 코드import syssys.setrecursionlimit(10**6)dx = [0, 0, -1, 1, 1, 1, -1, -1] # 상하좌우 + 대각선dy = [1, -1, 0, 0, 1, -1, 1, -1]def DFS(y, x): visited[y][x] = True for ax, ay in zi..

🗂️ 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 💡 접근법DP의 top-down 방식으로 풀었다.triangle을 모두 탐색하면서 값을 업데이트 해나갔다. 현재 위치까지 도달하는 모든 경로 중 최댓값을 저장해야 한다. 따라서 위의 칸의 대각선 두 값 중 더 큰 값을 선택하여 더한다. 만약 대각선에 값이 존재하지 않는다면, 이는 삼각형의 범위를 벗어난 것이므로 이를 따로 처리해야 한다. 점화식은 dp[i][j] = dp[i-1][j-1] + dp[i-1][j] (i>=1, ..

🗂️ 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/42898# 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 🚀 시행착오def solution(m, n, puddles): # m: 열, n: 행 answer = 0 dict = {} # key: 경로, value: 경로 개수 visited = [[False] * (m+1) for _ in range(n+1)] dx = [0, 1] # 아래쪽, 오른쪽 dy = [1, 0] def DFS(y, x, cnt): visi..