공부 기록

✏️ 문제 문제 파악7562번 나이트의 이동 의 업그레이드 버전인 듯? 똑같이 풀면 쉽게 답이 나온다! 알고리즘그래프 이론그래프 탐색너비 우선 탐색  코드from collections import dequeimport sysinput = sys.stdin.readlinen = int(input())graph = [[0] * (n) for _ in range(n)]visited = [[0] * (n) for _ in range(n)] d = [(-2, -1), (-2, 1), (0, -2), (0, 2), (2, -1), (2, 1)]start_x, start_y, end_x, end_y = map(int, input().split())def bfs(x, y): q = deque([(x, y)]) vi..

✏️ 문제 문제 파악예전 트리 부모 찾기  문제랑 비슷한 맥락이다.인접리스트를 사용해서 풀었고 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..

✏️ 문제 문제 파악상하좌우 4가지가 붙어있으면 하나의 무리가 되므로 다음과 같이 방향 배열을 구성했다.d = [(1, 0), (0, 1), (-1, 0), (0, -1)] 무리의 개수를 구하는 것이므로 BFS가 한 무리를 돌 때마다 +1 하면 무리의 개수가 나온다. 알고리즘그래프 이론그래프 탐색너비 우선 탐색깊이 우선 탐색  코드from collections import dequeimport sysinput = sys.stdin.readlinefor _ in range(int(input())): h, w = map(int, input().split()) graph = [[0] * w for _ in range(h)] visited = [[0] * w for _ in range(h)] d = [(..

✏️ 문제 문제 파악문제를 읽어봤을 때 방향이 정해졌을 시 그 방향으로 칸에 적혀있는 수만큼 움직일 수 있는 것 같았다. 그래서 다음과 같이 코드를 짰다.다음 x위치 = 현재 x위치 + (움직일 방향 * 현재 밟고 있는 칸에 쓰여 있는 수)다음 y위치 = 현재 y위치 + (움직일 방향 * 현재 밟고 있는 칸에 쓰여 있는 수)  다음 x, y 위치가 -1일 경우 1을 리턴하고 끝까지 만나지 못할 경우 0을 리턴하여 이 리턴값을 기준으로 출력하는 문자열을 달리하였다. 알고리즘구현브루트포스 알고리즘그래프 이론그래프 탐색너비 우선 탐색깊이 우선 탐색  코드from collections import dequeimport sysinput = sys.stdin.readlinen = int(input())graph =..

✏️ 문제 문제 파악글자인 부분 1이 상, 하, 좌, 우, 대각선으로 인접하여 서로 연결되어 있다면 한 개의 글자라고 생각하므로 다음과 같이 방향 배열을 구성했다.d = [(-1, 0), (0, 1), (1, 0), (0, -1), (-1, -1), (-1, 1), (1, 1), (1, -1)] 글자의 개수를 구하는 것이므로 BFS가 한 번 돌면 한 글자이므로 돌 때마다 +1 하면 글자의 개수가 나온다.알고리즘그래프 이론그래프 탐색너비 우선 탐색깊이 우선 탐색  코드from collections import dequem, n = map(int, input().split())graph = [[0] * n for _ in range(m)]visited = [[0] * n for _ in range(m)]d ..

✏️ 문제 문제 파악최소한의 이동 횟수를 출력하라 했으므로 BFS를 사용하여 푼다.동규가 현재 위치에서 다음 위치로 갈 수 있는 방법은 8가지가 있다.현재 위치 - 1현재 위치 + 1현재 위치 - A현재 위치 + A현재 위치 - B현재 위치 + B현재 위치 * A현재 위치 * B현재 위치에서 위 8가지의 다음 위치를 덱에 넣는 방법은 다음과 같다.for next_v in (v-1, v+1, v-a, v-b, v+a, v+b, v*a, v*b): q.append(next_v) 이렇게 for 문을 만들면 next_v에 8가지의 v의 다음 위치가 차례대로 대입하게 된다. 처음엔 graph와 visited 배열의 크기를 주미의 위치까지만 만들었는데 생각해보니 주미의 위치보다 더 멀리갔다가 다시 돌아오는 경..

✏️ 문제 문제 파악가장 왼쪽이 두거나 가장 오른쪽에 두는 특징을 보면 양쪽에서 push, pop이 가능한 덱을 사용해서 풀어야한다!!  알고리즘그리디 알고리즘자료 구조문자열덱 코드from collections import deque for _ in range(int(input())): n = int(input()) card = input().split() q = deque() q.append(card[0]) stand = card[0] for i in range(1, len(card)): if stand >= card[i]: q.appendleft(card[i]) stand = card[i] else: q.append(card[i]) ..

✏️ 문제 문제 파악s 문자열의 문자가 해당할 경우 임의의 변수의 값을 +1 함으로써 "t 문자열을 전부 돌았을 때 임의의 문자열이 s 문자열의 길이와 같으면 s가 t의 부분 문자열이다" 라는 조건을 세워 코드를 짰다. 이렇게 하면 문자열의 순서도 지킬 수 있다. 또한 여기서는 입력의 개수를 따로 입력받지 않는데 이를 무한 반복문으로 짠 후 try-catch문을 사용해서 풀어야한다!(필자는 왜 없지? 이러고만 있었음..)  알고리즘그리디 알고리즘문자열 코드while True: try: s,t = map(str, input().split()) list_s = list(map(str, s)) index = 0 for i in range(len(t)): if index == l..

✏️ 문제 문제 파악이전에 붙인 테이프의 길이가다음 위치까지 사용할 수 있는 지 (테이프 개수 추가 x)다음 위치까지 테이프 길이가 되지 않아 새로 테이프를 붙여야 하는 지 (테이프 개수 추가 o)조건을 잘 세워 코드를 짜야하는 문제이다. 알고리즘그리디 알고리즘정렬  코드n, l = map(int, input().split())position = list(map(int, input().split()))position.sort()start = position[0]count = 1for i in position[1:]: if (i + 0.5) - (start - 0.5)

✏️ 문제 문제 파악이전에 붙인 테이프의 길이가다음 위치까지 사용할 수 있는 지 (테이프 개수 추가 x)다음 위치까지 테이프 길이가 되지 않아 새로 테이프를 붙여야 하는 지 (테이프 개수 추가 o)조건을 잘 세워 코드를 짜야하는 문제이다. 알고리즘그리디 알고리즘구현  코드실패한 코드s = input()ary = list(map(str, s.split('.')))x_length = 0for i in range(len(ary)): x_length += len(ary[i]) # X의 전체 개수가 홀수면 -1 출력for i in range(len(ary)): if x_length % 2 != 0: # X 개수가 홀수면 -1 만 출력이므로 첫 조건문으로 줌 print(-1) break else..