Dalin's Archive

흑흑 ㅠㅠㅠㅠ 드디어 맞았습니다.!! 이 문제는 무슨 알고리즘을 써야할까? 이런 고민보다는.. 아 이거 맞겠지 ? ? 이러고 돌렸는데 자꾸 틀렸다..ㅠㅠ 그러다가 이 분의 포스팅을 보고 어디에서 문제가 있었는지 알게 되었다 !! 아.. 이걸 설명하기 전에 아이디어를 쓰겠다! 아이디어 ✨ '입구에서 출구 방향으로 걸어갈 때 동쪽에서 서쪽으로 이동을 전혀 하지 않아도, 즉, 보행자의 현재 위치를 나타내는 좌표의 x축 값이 작아지는 경우가 없이도 출구까지 도달할 수 있다. ' 라고 되어 있다 => 항상 왼쪽(x축이 작은 쪽)에서 오른쪽(x축이 큰 쪽)으로만 간다! X축은 항상 증가하는 쪽으로 가야 한다. 같은 X축에 여러 개의 카페가 있을 수도 있는데, 모두 방문해서 번호를 줘야 한다. 그래서 ..

트리.. 몇 번 들어본 것 같기는 한데, 잘은 모르고 있었다. 이번에 싸피에서도 트리를 배웠는데, 마침 스터디 과제로도 이 문제가 있어서 반가웠다 ㅎㅎ 접근 🤔 맨 처음에는 한 명의 직속 상사가 여러 명의 직속 부하가 있는 걸 생각 못해서 틀렸다. 그 다음에는 칭찬을 받을 때마다 쭉 ~ 내려 보내서 시간 초과가 나왔다. (칭찬 받을 때마다, 그 칭찬받은 당사자를 루트 삼아서 쭉 트리를 순회하면서 직속 부하, 그 직속 부하, 그 직속 부하...에게 compliment 리스트에 칭찬의 수치를 더해줬다.) 그래서 일단은 칭찬이 입력될 때, 칭찬 받은 그 당사자만 칭찬을 받게 했다. (compliment 리스트에 더해서) 그 후에 트리를 1부터 전위 순회했다. 그러면서 직속 상사가 칭찬 받은 걸 더해서 받게 했..

문제 보러 가기! 아이디어 😍 뭔가 특별한 알고리즘을 쓰진 않은 것 같다. 다만 y축(column) 받을 때 인덱스가 좀 헷갈렸다.. (column 인덱스는 위에서 아래로 갈 때 0부터 수가 증가하는데, 문제에서는 아래에서 위로 갈 때 1부터 수가 증가하는 모양으로 입력이 들어온다.) 그것만 주의하면 괜찮을 것 같다 ! 코드 😆 import collections direction_move_index = {'W': (0, -1), 'S': (1, 0), 'E': (0, 1), 'N': (-1, 0)} r_direction = ['N', 'E', 'S', 'W'] # 오른쪽으로 l_direction = ['N', 'W', 'S', 'E'] # 왼쪽으로 def crash_wall(i, j): """ 범위 밖으..

문제 보러 가기~~ 아이디어 ✨ BFS인데 3차원 리스트를 활용해야 한다. 문제에서 3차원 리스트 쓰는 건 처음 해봤다 !! 일반적인 최단 거리 찾기에서 벽을 최대 한번 부술 수 있다는 조건이 추가되었다. 그래서 벽을 부수었는지 여부에 따라서 다른 2차원 리스트로 방문 체크를 해줬다. (즉 3차원 리스트를 만듦) 큐에 해당 인덱스, 벽을 부수었는지, 출발점부터 해당 위치까지의 거리를 넣어줬다. 큐 안에 요소가 있을 때, 하나씩 꺼내보면서 도착이면 그걸 따로 저장해줬고 그게 아니라면 4면을 돌아보면서 범위 이내인지 체크한다. 방문을 하지 않았고 벽인데, 아직 한번도 벽을 부수지 않았다면 벽을 부수고 거기로 간다. 방문을 하지 않았고 길이면, 벽을 부수지 않고 거기로 간다. '거기로 간다'라는..

문제 보러 가기! 트리 순회를 구현하는 문제! 숫자가 아니라 알파벳으로 들어와서, 그걸 숫자로 바꿔주는 것만 신경쓰면 될 것 같다! N = int(input()) # 노드의 개수 tree = list([0] * 2 for _ in range(N + 1)) # 왼쪽 자식, 오른쪽 자식 def pre_order(node): # 전위 순회 if node: print(chr(node+64), end='') # 할 일 pre_order(tree[node][0]) # 왼쪽 자식 pre_order(tree[node][1]) # 오른쪽 자식 def mid_order(node): # 중위 순회 if node: mid_order(tree[node][0]) # 왼쪽 자식 print(chr(node+64), end='') #..

문제 보러 가기! 아이디어 라고 할 것도 없는 것 같다. 다익스트라로 풀었다.. 다익스트라..는 전에도 들어는 봤지만, 딱히 공부하지는 않았었다. 이번 기회에 다익스트라를 공부할 수 있었다! 참고한 자료 안경잡이 개발자님의 글과 레드캐럿님의 벨로그 포스팅!!. 안경잡이 개발자님은 영상으로도 있어서, 다익스트라가 뭔지 이해하는 데 도움이 되었고, 레드캐럿님의 벨로그 포스팅은 파이썬 코드라서 코드 구현을 어떻게 해야 할지 알 수 있었다!! 또 플로이드워셜과의 차이점도 궁금했는데, 잘 설명해주셔서 좋았다 ㅎㅎ 코드 👩‍💻 import heapq import sys input = sys.stdin.readline V, E = map(int, input().split()) # 노드 개수, 간선 개수 start =..

문제 보러 가기! 문제 🤔 버스가 종점에 들어온다. 종점에 와서는 정비를 해야 하기 때문에, 버스 정비 공간에 가야 한다. 버스가 종점에 들어오는 시각, 종점에서 나가는 시각이 주어진다. 버스 정비 공간이 최소로 몇 개 필요한지 계산하는 문제 즉, 한번에 종점에 버스가 최대 몇 개까지 있는지를 계산하는 문제이다! (단, 같은 시각에 종점에 들어오는 버스- 나가는 버스가 있으면 먼저 나간 후에 출발한다) 아이디어 😍 일단은 버스가 들어오고 나가는 시각이 복잡하게 들어오기 때문에(HH:MM:SS.sss) 편하게 바꿔줬다. 다행히도 들어오는 숫자의 자릿수는 늘 같으니까, 시각에 곱하기 천만 + 분에 곱하기 십만 + 초에 곱하기 천+ 밀리초는 그대로 받아왔다. 그러면 하나의 숫자가 되어서 다루기 편하다. 그리고..

문제 보러 가기! def sol(order, num): global final_ans if order == len(str(N)): if not '0' in str(num): # K의 원소는 1~9 자연수이므로 0이 들어간 건 안됨 final_ans = max(final_ans, num) return for i in range(K): # K의 원소가 그 자릿수에 들어갈 수 있는지 살펴보기(큰 자릿수부터 채움) now_num = arr[i]*(10**(len(str(N))-order-1)) + num if now_num

문제로 GO! 전형적인 BFS를 활용했다. 다만 이동경로가 상하좌우나 대각선이 아니라서 특이했던 것 같다 ㅎㅎ import collections T = int(input()) # 한번 이동에 가는 경우들 directions = [(-2,-1),(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2)] for _ in range(T): l = int(input()) # 체스판 한 변의 길이 start_i, start_j = map(int,input().split()) final_i, final_j = map(int,input().split()) check = list([0]*l for _ in range(l)) # 거기까지 출발점에서 몇 번 이동했는지 체크 D = collect..

문제 보러 가기 아이디어, 배운 점 😍 맨 처음엔 가희의 위치를 찾아야 한다. 그리고 가희의 위치를 길로 만들었다.(그래서 갈 수 있도록~) 가희의 위치부터 탐색을 시작한다. 상하좌우를 탐색해서 범위 내이고 장애물이면 못가니까 continue 고구마이면 거기로 이동하되, 시간과 고구마 먹은 양을 1씩 증가 길이면 거기로 이동하되, 시간만 1 증가했다. 시간이 다 되었을 때 먹은 고구마를 최대값으로 갱신한 후에 return을 해주었다. 처음에는 기계적으로..(?) visited 리스트를 만들어서 체크를 할까 했지만, 갔던 길을 또 갈 수 있으니까 체크할 필요가 없었다. 그 자리에 가만히 있을 수도 있다고 했지만 딱히 고려하진 않았다. 만약에 움직여서 고구마를 먹을 수 있으면, 고구마 먹는 게 이득이니까 움..