디티 휴게소

문제 소개 17070번: 파이프 옮기기 1 가로 파이프에 세로파이프를 바로 연결할 수 없고, 대각 파이프는 파이프끝지점 기준 위 한칸 왼쪽 한칸이 비어있어야 한다(벽이면 안된다)dfs로 풀어보려 했으나 계속 시간초과가 발생..import sysN = int(sys.stdin.readline())room = [[0]*N for _ in range(N)]for i in range(N): room[i] = list(map(int,sys.stdin.readline().split()))directions = [(0, 1), (1, 0), (1, 1)] # (0,1)가로, (1,0) 세로, (1,1) 대각cnt = 0 def dfs(x,y,d): # (x,y,d(파이프 놓은 방향)) if x >= N..

공부/코딩테스트 2025. 4. 5. 14:57

문제 소개수빈이와 수빈이 동생의 위치가 주어지고, 최소 시간 내 수빈이가 동생을 찾아야 하는 문제다수빈이는 아래와 같이 세 가지 방법으로 이동할 수 있다1. x - 1(1초)2. x + 1(1초)3. x * 2(0초)수빈이의 위치 N, 동생의 위치 K 가 주어지며 수빈이가 K로 이동하는 최단시간을 구하는 것이다문제 풀이 접근방식최단경로를 구할때 유용한 BFS(너비 우선 탐색)을 사용하여 이동하면서 이동가능 위치의 최단방문시간을 갱신해보자큐를 이용하여 방문큐에 현재위치를 저장하여 큐에서 하나씩 꺼내 가능한 이동을 진행한다dist[i](i에 도달하는 최소시간 배열)을 따로 두어 이동을 진행할때 최소 시간이면 방문하고 갱신한다 백준 문제13549번: 숨바꼭질 3 import sysfrom collections..

공부/코딩테스트 2025. 3. 10. 20:04

문제 소개'평범한 배낭' 제목에서 유추가능 하듯 Knapsack Problem(배낭문제)로 정확히는 무게와 가치가 정수인 0/1 Knapsack문제다배낭의 무게를 초과하지 않으면서 가치를 최대로 하는 방법을 찾는 문제로, N개의 물건이 각 무게 W와 가치 V를 가질때 최대무게 K를 넘지않게 가장 가치가 높은 조합을 찾는것이다문제 풀이 접근방식 Brute Force로 모든 N개 물건의 조합을 확인하면 복잡도는 O(2^N)으로 해결할수는 있지만 N이 크면 굉장히 비효율적이다dp로 해결할수 있는데 부분문제 정의를 해야한다DP를 이용한 해결문제에는 배낭의 무게, 물건의 개수, 물건의 무게, 물건의 가치가 있고 물건의 개수와 무게가 부분문제를 정의하는데 필요하다 dp 테이블 정의dp[i][w] = i번째 물건까지..

공부/코딩테스트 2025. 3. 8. 12:49

15663번: N과 M (9)  주어진 N개의 숫자들 중 중복없이 M개의 조합을 사전순으로 출력하는 문제이다가능한 경우를 탐색하면서 조건에 맞지않으면 돌아가서 다른선택을 하는 백트래킹을 이용해서 풀었다 import sysN, M = map(int,sys.stdin.readline().split())num_list = list(map(int,sys.stdin.readline().split()))num_list.sort()comb = []visited = [False for _ in range(N)]def back(): if len(comb) == M: for i in comb: sys.stdout.write(f"{i} ") sys.stdout.write("..

공부/코딩테스트 2025. 3. 3. 18:53

2178번: 미로 탐색  풀이import sysfrom collections import dequemove = [[-1,0],[1,0],[0,-1],[0,1]]def bfs(graph,x,y):    count = 0    queue.append((x,y))    # 상하좌우 탐색 -> 미로범위이고 벽(0)이 아니면 -> 이전위치 ++, 큐에추가    while queue:        x,y = queue.popleft()        count += 1        for i in range(4):            nx = x + move[i][0]            ny = y + move[i][1]            if nx >= N or ny >= M or nx  bfs나 dfs로 풀이..

공부/코딩테스트 2025. 2. 22. 08:57

2805번: 나무 자르기https://www.acmicpc.net/problem/2805  문제 접근절단기의 최적높이 H를 좁혀나가야 할것같다최소 M미터는 갖고가야 하므로 H 시작값은 20(가장 긴 나무) - 7(갖고갸아하는 나무)최대값은 20(가장 긴 나무의 값)으로 두고 이진탐색(binary search)을 하면 될것같다 전체 코드import systreeCount, length = map(int,sys.stdin.readline().split())tree_list = list(map(int,sys.stdin.readline().split()))set_lenght = max(tree_list[0],tree_list[-1],tree_list[len(tree_list)//2]) - length # 세개..

공부/코딩테스트 2025. 2. 15. 15:28

11659번: 구간 합 구하기 4   N개의 수가 주어지고 i, j가 입력으로 들어왔을 때 N에서 i~j 까지의 구간합을 출력해야하는 문제이다 처음에 i ~ j 까지 일일히 더하는 방식으로 구현해봤지만예상대로 시간초과(구간 M개, N개의 수 -> O(MN)) 누적합을 이용해서 구간합을 구해야한다 위처럼 숫자가 주어졌을때(1~8) 임의의 인덱스까지 누적합을 알고있다고 하면i ~ j 까지의 구간합은 j까지의 누적합 에서 i - 1 까지 누적합을 뺀것이다4 + 5 + 6 = (1 + 2...+ 6) - (1 + 2 + 3) 누적합은 어떻게 구현해야할까? 2025.02.06 - [공부/코딩테스트] - 다이나믹 프로그래밍(Dynamic Programing) 다이나믹 프로그래밍(Dynamic Programing)백..

공부/코딩테스트 2025. 2. 10. 20:22

1003번: 피보나치 함수  N이 주어졌을때 피보나치 함수에서 0과 1이 출력되는 횟수를 알아내야하는게 핵심문제에서 주어진 함수를 이용해서 재귀로 문제를 푼다면 시간초과가 발생한다따라서 DP로 해결해야한다  0과1 횟수는 피보나치 성격을 갖기때문에 동일한 규칙을 갖는다fib(n)에서 1과 0의 개수 2개를 저장해줘야 하므로 2차원으로 구현해야한다 import systestcase = int(sys.stdin.readline())for i in range(testcase): N = int(sys.stdin.readline()) dp = [[0] * 2 for _ in range(N+1)] dp[0][0] = 1 dp[0][1] = 0 if N>0: dp[1][0] =..

공부/코딩테스트 2025. 2. 9. 15:03