조이의 개발 성장 다이어리

1. 문제: https://www.acmicpc.net/problem/15683✅ 풀이import Foundationlet readline = readLine()!.split(separator:" ").map { Int($0)! }let (n, m) = (readline[0], readline[1])var board:[[Int]] = []let dx = [1, 0, -1, 0]let dy = [0, 1, 0, -1]// 우 하 좌 상 순서 offset 배열var answer = Int.maxvar cctvs:[(Int, Int)] = []for i in 0.. Bool { // 유효한 좌표 내에 있는지 판단하는 함수 return 0 - 해당 문제의 핵심은 모든 cctv의 모든 방향의 조합을 어떻..

문제: https://school.programmers.co.kr/learn/courses/30/lessons/12951import Foundationfunc solution(_ s: String) -> String { let arr = s.components(separatedBy:" ") // 1) var answer: [String] = [] for word in arr { if let first = word.first { // 2) if first.isLetter { // 3) answer.append(word.capitalized) } else { ..

1. 문제: https://www.acmicpc.net/problem/1913✅ 풀이let n = Int(readLine()!)!let m = Int(readLine()!)!var arr = Array(repeating: Array(repeating: 0, count: n), count: n)// 하우상좌 오프셋 (달팽이가 회전하면서 수가 채워지는 순서)let dx = [1, 0, -1, 0]let dy = [0, 1, 0, -1]var dir = 0var num = n * nvar x = 0, y = 0var targetX = 0, targetY = 0while num > 0 { arr[x][y] = num if num == m { // 문제에서 찾고자하는 target의 좌표 저장 ..

1. 문제: https://school.programmers.co.kr/learn/courses/30/lessons/17686- 먼저, 배열 sort시 커스텀하게 비교해야하므로 cmp_to_key 라이브러리를 사용했고, 비교하는 함수인 compare 함수를 작성했다.- 정렬의 조건을 정리하자면 다음과 같다.1) HEAD: 문자로 이루어져있으며, 반드시 한글자 이상이다. 파일명은 HEAD 기준으로 사전순으로 정렬하며, 대소문자를 구분하지 않는다.2) NUMBER: 최소 한글자 이상의 연속된 숫자로 이루어져 있으며, 숫자 순으로 정렬한다.3) TAIL: HEAD와 NUMBER 외의 나머지 부분으로, 이부분은 정렬에 영향을 주지 않는다. ❌ 틀린 풀이from functools import cmp_to_keyd..

문제: https://school.programmers.co.kr/learn/courses/30/lessons/42746 - 해당 문제를 처음 보고 라이브러리를 활용하여 모든 수의 조합 리스트를 만든 다음 정렬을 진행하고자 했으나,조합의 시간복잡도 = O(2^n), 순열의 시간복잡도 = O(n!) 이기에 numbers의 길이가 100,000까지 갈 수 있음을 감안하면 시간초과가 발생한다.- 따라서 다른 방법을 고민해보아야 하는데, 인접한 두 수 끼리 앞 - 뒤, 뒤 - 앞 조합으로 붙여본 후 더 큰 수가 되는 순서대로 정렬하면 된다.ex) 예를들어 numbers의 두번째 예시 중 [3, 30] 을 비교한다고 했을 때330 - 303 과 비교하면 330이 크므로, 3이 더 앞에 온다- 정렬 시 단순 오름차..

문제: https://www.acmicpc.net/problem/9663백트래킹의 대표 유형급인 문제이다.- 퀸의 위치마다 서로 공격할 수 없는 퀸의 위치가 달라짐 --> 가지치기- 모든 퀸의 배치를 끝냈다면 돌아가기 --> 백트래킹 ✅ 풀이n = int(input())answer = 0col = [False] * n # 각 열에 퀸이 있는지 여부를 판단하기 위한 배열diagonal1 = [False] * (n * 2) # 우상 -> 좌하향 대각선(/)diagonal2 = [False] * (n * 2) # 좌상 -> 우하향 대각선(\)def backtracking(y): global answer if y == n: # 모든 행마다 배치를 마쳤다면 answer + 1 하고 retu..

1. 문제: https://www.acmicpc.net/problem/2239해당 문제는 백트래킹으로 풀이할 수 있다.- 행과 열에는 1부터 9까지의 수가 들어가야하는데, 다양한 경우의 수가 포함될 수 있으며 조건이 맞으면 return 해야함 ✅ 풀이import sysinput = sys.stdin.readlineboard = []for _ in range(9): board.append(list(map(int, str(input().rstrip()))))def valid_in_col(col, num): # 열에 수가 포함되어있으면 False return for i in range(9): if board[i][col] == num: return False return Truedef..

1. 문제: https://school.programmers.co.kr/learn/courses/30/lessons/43165해당 문제는 DFS로 풀이할 수 있다.- 더하거나 뺀다 --> 가지치기 -> 트리구조와 유사- 시작 조건은 0이고, 종료 조건 (target) 존재 --> 종료 조건이 있음. 즉 시작부터 종료 조건까지 탐색하는 그래프 탐색 ✅ 풀이answer = 0def solution(numbers, target): def dfs(depth, count, index): global answer if depth == len(numbers) and sum == target: # n개의 정수로 합계가 target일 경우, count + 1..

문제: https://www.acmicpc.net/problem/28069해당 문제는 DP로 풀이했다.- 0번 계단부터 N번째 계단까지 도달하는 종료 조건이 있음- DP[N]을 N번째 계단까지 도달하기 위해 행동한 횟수라고 가정하여 점화식을 세울 수 있음 ❌ 틀린 풀이n, k = map(int, input().split())INF = int(1e9)dp = [INF] * (n+1) # DP[i]: i번째 계단까지 도달하기 위한 행동 횟수dp[0] = 0 # 현재 0번째 계단에 있고, 행동횟수는 0이므로 dp[0] = 0으로 초기화for i in range(n): if i + 1 소수점을 제거한 정수와 같다. # int(i+i/2) : [x]는 x보다 작거나 같은 가장 큰 정수 --> 소..

1. 문제: https://www.acmicpc.net/problem/27971해당 문제는 다음과 같은 근거로 BFS로 풀이했다.- 처음에는 강아지가 0마리임 --> N마리로 가기 위한 최소한의 행동횟수 : BFS- 인덱스가 0부터 N까지 존재하는 배열을 그래프로 가정하고, 각 요소에 도착할 때마다 행동횟수를 +1 하는 방식으로 설계한다. ✅ 풀이from collections import deque# n: 키우길 원하는 강아지의 수# m: 닫힌구간의 갯수n, m, a, b = map(int, input().split())visited = [-1] * (n+1) # 1) -1을 선언함으로써 방문여부와 거리를 모두 판단할 수 있도록 함for _ in range(m): l, r = map(int, in..