조이의 개발 성장 다이어리

1697 - 숨바꼭질 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 틀린 풀이 from collections import deque import sys input = sys.stdin.readline n, k = map(int, input().rstrip().split()) visited = [0] * 100001 def bfs(): global board global visited q = deque([n]) vis..

문제 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 시간초과 코드 import Foundation let input = readLine()!.split(separator:" ").map { Int($0)! } let m = input[0], n = input[1] //m: x / n : y var board:[[Int]] = [] for _ in 0.. DP의 메모이제이션 기법 활용 예를들어 이 경우를 비교해보면 20에서 도착지점까지 가는 ..

🥺 이번엔 백트래킹 조지기 https://github.com/tony9402/baekjoon/tree/main/backtracking 해당 링크의 문제들을 도장깨기 하듯? 풀었고 풀이는 주석으로 달아두었습니다. 10971 https://www.acmicpc.net/problem/10971 💡왜 백트래킹인가? 순회에 필요한 비용을 행렬 형태로 주어지는데, 여기서 차례로 탐색하면서 소요되는 비용을 최소화하는 경우의 수가 너~무 많다. 내 풀이 import Foundation let n = Int(readLine()!)! var board:[[Int]] = [] var answer = Int(1e9) var visited = Array(repeating: false, count: n) // "한번 갔떤 도시..

LIS 1. 11053 (가장 긴 증가하는 부분 수열) https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 내 풀이 더보기 import Foundation let n = Int(readLine()!)! let arr = readLine()!.split(separator:" ").map { Int($0)! } var dp = Array(repeating:1, count:n..

문제 https://www.acmicpc.net/problem/20208 20208번: 진우의 민트초코우유 첫번째 줄에 민초마을의 크기인 N과 진우의 초기체력 M, 그리고 민트초코우유를 마실때 마다 증가하는 체력의 양 H가 공백을 두고 주어진다. N, M, H는 모두 10보다 작거나 같은 자연수이다. 두번째 www.acmicpc.net https://www.acmicpc.net/problem/22944 22944번: 죽음의 비 가로, 세로 길이가 $N$인 정사각형 격자가 있다. 해당 격자에는 두 곳을 제외한 모든 곳에 체력을 1씩 감소시키는 죽음의 비가 내리고 있다. 죽음의 비가 안내리는 곳은 현재 있는 위치와 안전지 www.acmicpc.net 처음엔 이문제랑 비슷하다 생각했는데 아니었다. 두 유형이 ..

문제 https://www.acmicpc.net/problem/21921 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net 시간초과 풀이 1 (투포인터 사용) 더보기 import Foundation let input = readLine()!.split(separator:" ").map { Int(String($0))! } let n = input[0], x = input[1] let arr = readLine()!.split(separator:" ").map { Int(String($0))! } var s..

🥺 DP가 너무 약한자의 DP 조지기 https://github.com/tony9402/baekjoon/tree/main/dynamic_programming_1 https://github.com/tony9402/baekjoon/tree/main/dynamic_programming_2 해당 링크의 문제들을 도장깨기 하듯? 풀었고 풀이는 주석으로 달아두었습니다. 2839 https://www.acmicpc.net/problem/2839 내 풀이 import Foundation let n = Int(readLine()!)! var dp = Array(repeating: 0, count:5001) for i in 3...n { if i%3 == 0 { dp[i] = dp[i-3] + 1 // 3으로 나누어떨어질..

문제 : https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 첫번째 풀이 (시간초과) import Foundation let n = Int(readLine()!)! for _ in 0..

문제 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 내 풀이 1. 틀잡기 import Foundation let input = readLine()!.split(separator:" ").map { Int(String($0))! } let n = input[0], l = input[1], r = input[2] var board:[[Int]] = [] var dx = [-1, 1, 0, 0] var dy = [0, 0, -1, 1..

문제 : https://www.acmicpc.net/problem/1713 1713번: 후보 추천하기 첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대 www.acmicpc.net 내 풀이 import Foundation let n = Int(readLine()!)! let m = Int(readLine()!)! //추천 횟수 let nums = readLine()!.split(separator:" ").map { Int(String($0))! } var stack:[Int] = [] //사진틀 (스택) var count:[Int] = Array(repea..