조이의 개발 다이어리

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..

문제: https://www.acmicpc.net/problem/18126이 문제는 DFS를 활용하여 푸는 문제다. 문제에서 다음과 같은 근거를 찾았다- 입구는 1번이며, 입구에서 방까지 이동 --> 탐색- 문마다 양방향으로 연결하는 길이 --> 그래프- 최대한 입구에서 먼 방까지의 거리 --> 모든 그래프 탐색을 통해 최댓값 탐색 --> DFS*BFS를 활용할 수도 있으나 최단거리를 이용하는 조건이 없으므로 DFS를 활용하는 것이 효율이 좋음 ✅ 풀이import sysinput = sys.stdin.readlinesys.setrecursionlimit(10**6)n = int(input())graph = [[] for _ in range(n+1)]visited = [False] * (n+1)for _ ..

1. 문제:https://school.programmers.co.kr/learn/courses/30/lessons/72410 ✅ 풀이def solution(new_id): # 1단계 answer = new_id.lower() # 2단계 temp = "" for c in answer: if c.islower() or c.isdigit() or c in ["-", "_", "."]: temp += c answer = temp # 3단계 while ".." in answer: answer = answer.replace("..", ".") # 4단계 answer = answer.strip(".") # 5단계 ..

문제: https://www.acmicpc.net/problem/2437해당 문제는 풀다가 도저히 이해가 안가서 풀이를 보고 이해해보고자 했다 🥲알고리즘 분류를 보니, 그리디 알고리즘을 활용하여 푸는 문제라고 하는데 왜 이게 그리디 알고리즘인지는 아래에서 알아보도록 하자.우선 이 문제를 푸는 방법이다. https://aerocode.net/392 이분의 풀이를 참고했는데, 해당 풀이를 이해한 바는 다음과 같다. 1) "추들을 가지고 측정할 수 있다" = "추를 활용하여 ~ 범위 내의 무게를 측정할 수 있다" 라는 의미로 이해한다. --> 측정할 수 있는 범위를 수직선으로 그려보기2) 무게가 작은 추를 활용하여 측정할 수 있는 무게를 점점 늘려가야하므로, 추들을 오름차순으로 정렬 후 차례대로 올려본다. ..