공부 기록

✏️ 문제 문제 파악예전 트리 부모 찾기  문제랑 비슷한 맥락이다.인접리스트를 사용해서 풀었고 BFS를 활용했다.  해당 도시까지 가는 거리가 거리 정보 k와 같다는 조건문을 어디다가 둬야할 지 조금 헤맸다. visited 1차원 배열에 처음 넣은 도시에서 다른 도시까지의 거리를 +1씩 하며 이 거리가 k와 같으면 해당 visited 배열의 인덱스를 출력하는 방식으로 코드를 짰다. 알고리즘그래프 이론그래프 탐색너비 우선 탐색데이크스트라최단 경로  코드from collections import dequeimport sysinput = sys.stdin.readlinen, m, k, x = map(int, input().split())graph = [[] * (n+1) for _ in range(n+1)]v..

✏️ 문제 문제 파악k = 2일 때, 최소값인 1+2보다 n이 작으면 -1k = 3일 때, 최소값인 1+2+3보다 n이 작으면 -1 이다. 그리고 최소값보다 클 때는 다음과 같은 규칙이 보였다. 알고리즘그리디 알고리즘수학 코드n, k = map(int, input().split())basket = k * (k + 1) // 2if n

✏️ 문제 문제 파악중요한 삼각형의 조건은 다음과 같다." 가장 긴 변은 다른 두 변의 합보다 작다. "이 조건을 만족하게 코드를 짜면 쉽게 해결할 수 있는데 삼각형 세 변의 길이의 합이 최대로 되려면 3연속인 값을 써야한다는 생각을 못하고 3중 for반복문을 썼더니 시간초과가 계속 떴었다 ㅠㅠ..근데 3연속인 값을 안썼을 때 합이 최대가 되는 세 변의 길이는 진짜 없을까...? 알고리즘그리디 알고리즘정렬수학 코드import sysinput = sys.stdin.readlinen = int(input())length = sorted([int(input()) for _ in range(n)], reverse=True)result = -1for i in range(n-2): if length[i]

✏️ 문제문제 파악자른 길이는 다른 막대에 붙이거나 연결해서 쓸 수 없기 때문에 버린다고 가정하고 코드를 짜야한다. 알고리즘이분 탐색매개 변수 탐색  코드import sysinput = sys.stdin.readlinem,n = map(int, input().split())snacks = list(map(int, input().split()))length = 0start, end = 1, max(snacks)while start = m: length = max(length, mid) start = mid + 1 else: end = mid - 1print(length)

✏️ 문제문제 파악 알고리즘이분 탐색  코드import sysinput = sys.stdin.readlinen, m = map(int, input().split())power = []for i in range(n): a, b = input().split() power.append([a, int(b)])for j in range(m): char = int(input()) start, end = 0, len(power) - 1 while start power[mid][1]: start = mid + 1 else: end = mid - 1 print(power[start][0])

✏️ 문제 문제 파악이번 문제에서는 방문할 필요가 없는 위치가 아니라 방문해야 하는 위치만 알려주므로 이를 잘 알고 코드를 짜야한다.나는 다음과 같이 visited 배열을 줬다. 1 → 음식물이 있지만 방문하지 않은 위치2 → 음식물이 있어 이미 방문한 위치이를 바탕으로 다음 위치를 방문할 때 다음 위치가 음식물이 있지만 방문하지 않은 위치인 지(if visited[위치] == 1) 조건문을 주어 풀었다. 알고리즘그래프 이론그래프 탐색너비 우선 탐색깊이 우선 탐색  코드from collections import dequen, m, k = map(int, input().split())graph = [[0] * m for _ in range(n)]visited = [[0] * m for _ in range(..

✏️ 문제 문제 파악예전 트리 부모 찾기  문제랑 비슷한 맥락이다.인접리스트를 사용해서 풀었고 BFS를 활용했다.  개수가 아닌 순서이므로 들렸으면 +1 씩 해줘야 한다. 그래서 인접리스트의 한 배열을 방문한 후에 순서를 +1 하도록 코드를 짰다.그리고 문제에서 오름차순으로 방문한다고 했으므로 인접리스트의 한 배열을 방문하기 전에 인접리스트를 오름차순하고 돌아가도록 코드를 구성했다. 알고리즘그래프 이론그래프 탐색너비 우선 탐색정렬  코드from collections import dequeimport sysinput = sys.stdin.readlinen, m, r = map(int, input().split())graph = [[] * (n+1) for _ in range(n+1)]visited = [0..

✏️ 문제   문제 파악입력으로 주어진 값을 잘 구분해야 한다.X → 벽이므로 아예 방문을 자체를 안해도 됨I → 도연이의 위치로, 즉 탐색의 초기 위치 값P → 사람이 있는 위치로 이 위치에 해당될 때만 카운트  또한 이 문제의 경우 가로, 세로로 이동해서 방문할 수 있으니 방향 배열을 다음과 같이 구성했다.d = [(-1, 0), (1, 0), (0, -1), (0, 1)]   알고리즘그래프 이론그래프 탐색너비 우선 탐색깊이 우선 탐색  코드from collections import dequeimport sysinput = sys.stdin.readlinen, m = map(int, input().split())graph = [[0] * m for _ in range(n)]visited = [[0..

✏️ 문제   문제 파악처음에는 위의 사진과 같이 해당 범위 내에 있는 값 중 제일 큰 값과 그 값의 인덱스 값을 받아와 제일 큰 값이 있는 인덱스로 점프하는 방향으로 코드를 짰다. 점프한 인덱스의 visited 배열에 1을 넣어 최종적으로 sum(visited)을 출력하는 코드를 짰는데 자꾸 값이 몇 개는 맞으면 몇 개는 1씩 차이가 났었다.  반례 모음 72 3 1 2 6 4 7# 3101 2 0 1 3 2 1 5 4 2# 520 0# -132 5 0# 11021 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ..

✏️ 문제 문제 파악입력으로 주어진 배열을 두 가지로 병사를 나눴다. 1 → 'W'가 입력으로 들어온 위치, 즉 우리팀 병사2 → 'B'가 입력으로 들어온 위치, 즉 상대팀 병사병사를 구분하여 병사의 수를 세야하므로 카운트할 때 다음 위치에 있는 병사가 현재 병사와 같은 팀이라는 조건이 붙어야 한다. 또한 이 문제의 경우 가로, 세로로 이동해서 방문할 수 있으니 방향 배열을 다음과 같이 구성했다.d = [(-1, 0), (1, 0), (0, -1), (0, 1)]   알고리즘그래프 이론그래프 탐색너비 우선 탐색깊이 우선 탐색  코드from collections import dequeimport sysinput = sys.stdin.readlinem, n = map(int, input().split())..