Dalin's Archive

문제로 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 리스트를 만들어서 체크를 할까 했지만, 갔던 길을 또 갈 수 있으니까 체크할 필요가 없었다. 그 자리에 가만히 있을 수도 있다고 했지만 딱히 고려하진 않았다. 만약에 움직여서 고구마를 먹을 수 있으면, 고구마 먹는 게 이득이니까 움..

문제 보러 가기! 오늘 카카오 코테를 봤는데, 6번 문제에서 정확성은 다 pass했는데 효율성은 아무것도 통과하지 못했다.ㅠㅠ 접근 방법 자체가 잘못되었다는 것은 알았지만, 어떻게 해야 할지 잘 몰라서 그냥 보내줬다.. 끝나고 스터디 팀원분들께 여쭤보니, 이 문제를 좀 응용해서 풀었다고 하셨다..! 누적합 유형(?)이라는데, 나는 이걸 공부해 본 적은 없었다.. 그래서 처음 공부해서 풀어봤다. 주황색처럼 2차원 리스트가 있는데, 보라색 영역의 값들을 다 더하고 싶을 때! 물론 보라색 영역을 한 번만 물어보면, 2중 for문으로 해결할 수 있을 것이다. 하지만 보라색 영역이 바뀌면서, 여러 번 물어볼 때! 그럴 때마다 2중 for문을 돌리면 너무 시간이 오래 걸린다. 그럴 때 이 누적합 방법을 써주면 된다..

문제 보러 가기! 아이디어 ❄ N자리 숫자가 주어졌을 때, 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 만드는 문제였다! 처음에 한 생각은, '아! 그러면 쭉 보면서 작은 숫자 K개를 없애주면 되려나?' 였다. 1924에서 2개를 지우라고 하면, 가장 작은 숫자 1과 2을 없애면 94가 되는 예제를 보고 한 생각이었다. 그런데 4177252841에서 4개 숫자를 지우라고 하면 어떨까? (예제 3번) 작은 숫자 순서대로 4개.. 1, 2, 2, 1를 없애면 477594가 된다. 이는 정답은 775841과 다르다!! 이건 아니었다.. 그래서 다시 생각해봤다. 그랬더니 가장 큰 수가 되려면, 앞의 자리가 큰 게 중요하다는 것이 생각났다! 그래서 맨 앞부터 보면서, 그게 그 다음 숫자보다 작으면 없애는 식으..

문제 보러 가기! 처음 아이디어 원의 중심 좌표 x 기준으로 정렬 옆에 있는 두 개 원씩 만나는지 보기 라는 아이디어로 짠 코드 두 개 원이 만나는지는 '힌트'에 있는 수학 공식을 참고했다 ! 코드 import sys input = sys.stdin.readline def is_meet(circle1, circle2): x1, r1 = circle1 x2, r2 = circle2 if (x1 - x2) == 0 and r1 != r2: # 동심원 return False if (r1 - r2) ** 2

문제 보러 가기! 얼마 전에 누적합을 처음 공부하고, 관련된 문제를 풀고 싶어서 스터디 문제에 추가했다.(한 사람 당 한 문제씩 추가하는 방식으로 스터디를 하는 중입니다~) 그런데 단순한 누적합..만으로는 해결할 수 없었다..ㅠㅠ 0 ≤ 모기의 입장 시각 < 모기의 퇴장 시각 ≤ 2,100,000,000... 너무 컸기 때문이다. 그래서 계속 시간 초과, 메모리 초과..와 싸우다가 스터디를 할 때까지 못 풀었다. 스터디원 분께서 설명해주셔서 값, 좌표 압축이라는 아이디어를 처음 알게 되었다! 그 아이디어를 적용하고, 다른 부분도(이것도 아래에서 설명하겠다.) 바꾸니까 문제를 풀 수 있었다 ! 전에 코드(시간 초과) 💥 import collections import sys input = sys.stdin...

문제 보러 가기!! 와아... 많은 시간 초과를 겪은 끝에 드디어 맞았다. 🤣🤣 아이디어 ⭐ N이 K로 나눠지는지 본다. -> N을 두 번 써서 K로 나눠지는지 본다. -> 쭉 본다. K로 나눠지면(나머지가 0이면) 그만두고, N을 몇 번 썼는지 출력한다. 불가능한지 판단하는 기준은 ?? 나머지를 쭉 저장한다. -> 나왔던 나머지가 또 나오면, 그 패턴이 반복된다는 거니까 불가능하다고 본다. (이걸 증명하는 수학적인 개념은 모르겠는데, 찾아봐야겠다.) N을 n번 쓸 때 모듈러 연산을 활용했다 !! 나도 처음 알게 된 것이라서, 기억할 겸 쓴다. 모듈러 연산의 모듈러는 modulo 즉 나머지이다. 나머지를 구할 때 사용할 수 있는 세 가지 성질이 있다. (A+B) % C = (A%C + B%C) % C (..

문제 보러 가기! 아이디어 💕 도시 간 이동하는 데 드는 비용이 행렬에 저장되어 있다. 모든 도시를 순회하고, 다시 원래 출발점으로 돌아와야 한다. 이때 가장 적은 비용이 들 때 얼마나 드는지 출력하는 문제이다. 도시가 최대 10개니까 브루트포스하게 다 봐도 될 거 같다고 생각했다. 일단은 모든 도시에서 출발해보았다. 방문했던 곳은 못 가니까 방문 체크도 하고 ! 다만 원래 출발점으로는 다시 돌아와야 하니까 그 부분은 다르게 처리했다. 처음 코드(파이썬-시간초과, 파이파이- 3140ms) 😂 import sys input = sys.stdin.readline N = int(input()) cost_matrix = list(list(map(int, input().split())) for _ in range..

문제 보러 가기! 접근 💚 처음에는 소수가 나와서 어떻게 접근할지 고민했다. 우주 생명체 수 N에서 핑거 스냅으로 할 수 있는 4가지 일을 하고, 그게 A와 B 사이의 소수인지 매번 확인하는 것은 힘들 것 같았다. (매번 소수인지 쭉 계산을 해야 하니까.) 그래서 좀 생각을 바꿔봤다! A, B는 100000 이하니까 10만 이하의 소수를 모~두 구하는 것이다. (에라토스테네스의 체로 구했다.) 그리고 A 이상 B 이하의 소수들을 리스트에 저장해두고, 핑거 스냅으로 4가지 일을 한 후에 그 우주 생명체 수가 그 리스트의 값들 중에 있는지 보는 것이다. 최소 몇 번의 핑거 스냅을 해야 할지 구하는 것! 즉 최단 거리를 구하는 것과 같으니까 BFS로 풀었다. 4가지 일을 한 후의 우주 생명체 수를 보고 범위 ..

문제 보러 가기(로그인해야 볼 수 있어용) ㅠㅠㅠㅠㅠㅠ 3~4시간 힘겨운 시간을 보내고 ㅠㅠㅠ 드디어 맞았다 ㅠㅠㅠㅠㅠ 이렇게 오래 씨름한 문제는 오랜만이다... 접근은 그렇게 어렵지는 않았고, 1시간 만에 파이참에서는 정답이 나오게 코드를 짤 수 있었다. 그런데 문제 채점 사이트에서 런타임 에러 나와서 해결하느라고 정말 정말 힘들었다 ..!! 맨 처음 짠 코드 👩‍💻 import sys sys.stdin = open('1242_input.txt') T = int(input()) hex_change = { '0': '0000', '1': '0001', '2': '0010', '3': '0011', '4': '0100', '5': '0101', '6': '0110', '7': '0111', '8': '10..