Dalin's Archive

며칠 동안 고민 고민하고 많은 '틀렸습니다'와 '시간 초과'를 만났다.. 아직도 파이썬으로는 시간 초과가 나오지만... 파이썬으로 시간 초과 안 나오는 로직은 나중에 생각하기로 하고.. pypy로는 통과했다 !! 빙산 문제 보러 가기~~ 아이디어 ⭐ check 함수 -> 빙산이 두 부분 이상으로 나뉘었는지 체크 melt 함수 -> 1년마다 빙산의 각 구역을 물과 닿은 부분만큼 녹임(0까지만 녹임) all_melt 함수 -> 모든 빙산이 녹았는지 체크하는 함수 year = 0으로 초기화하고 시작 계속 빙산이 두 덩어리로 나뉘었는지 체크함. 1) 두 덩어리로 나뉘었으면 year을 출력하고 break 2) 두 덩어리로 나뉘지 않았으면 1-1) 빙산이 다 녹았으면(두 덩어리로 나뉘는..

백준 정육점 문제보러 가기!! 아이디어, 코드 설명 🌱 고기의 무게, 가격을 튜플로 받아서 리스트를 만든다. 가격이 낮은 순서대로, 가격이 같다면 무게가 큰 순서대로 정렬한다. 그리고 그 가격의 고기를 살 때, 얼마나 고기를 얻을 수 있는지(그 가격보다 낮은 고기는 덤으로 얻을 수 있다)를 dp에 저장한다. 고기의 무게, 가격이 저장된 리스트를 쭉~ 돌면서, 얻을 수 있는 고기의 양이 필요한 양 이상이면 그 가격을 비교해서(필요 고기 양이 충족되었을 때 가격이 같은 고기를 여러 개 샀을 수도 있고, 그것보다 가격이 비싼 고기를 하나 샀을 수도 있으니까!) 싼 가격을 min_price에 대입한다. 다 돌고 나서, min_price가 원래 초기화한 값 그대로라면(얻을 수 있는 고기 양이 필요양보다 적었다는 ..

문제 보러 가기! 생각보다는 쉬웠다.. 요즘 한번에 통과한 적이 많지 않은데, 오랜만에 한번에 통과해서 기분이 좋다 ~ 😆 아이디어 ❕ 딕셔너리를 활용해서 풀었다! 상황을 나누고, 상황마다 어떤 행동을 해야 할지 생각해서 코딩했다. 숫자 1이 들어왔을 때 이름, K개, 각 가치를 각각 저장함(각각의 가치는 리스트로 저장) 1) 처음 나오는 고릴라이면, 딕셔너리에 저장(key는 고릴라 이름, value는 정보의 가치들을 리스트 형태로) 2) 전에 나왔던 고릴라이면, 딕셔너리에 추가된 정보 부분만 추가함(extend 를 썼다. 알고만 있었는데, 이걸 써보는 건 처음인 것 같다 ㅎㅎ) 숫자 2가 들어왔을 때 이름, B개를 각각 저장 1) 그 고릴라가 있는지 체크(혹시 몰라서) 있으면 그 딕셔너리의 value(..

문제 보러 가기! 아이디어 🌼 처음에는 DFS로 코드를 짰다. 2, 10 정도는 금방 답이 나왔지만... N의 범위가 10의 6제곱... 10000 정도만 해도 시간이 오래 걸렸다. 또 지금 생각해보니, 최대 재귀 깊이를 초과할 수 있겠다는 생각도 든다..! 다시 짠 코드 ! 3가지 종류의 계산이 있는데, 가능한 계산을 하고, 그 중에 가장 횟수가 적은 것을 dp에 넣는다! 코드 📝 N = int(input()) dp = [0, 0, 1, 1] + [0] * N # 0, 1번 인덱스는 편하게 쓰려고 추가. 2에서 1로 가는 최소 연산 수는 1, 3에서 1로 가는 최소 연산 수는 1개. for i in range(4, N + 1): # N을 구해야 하니까 그때까지 보기 if i % 6 == 0: # i가 ..

문제 보러 가기~~ 아이디어 🤩 몇 자리 숫자가 들어오는지에 따라서 다른 행동을 하라고 했다. 그래서 숫자(단, str 형식으로 입력받음)와 그때까지 더한 홀수의 합을 받아서, 특정한 행동을 하는 함수를 만들었다. 몇 자리인지에 따라서 다른 행동을 하고, 한 자리가 되어서 종료될 때까지 재귀로 계속 돌린다. 한 자리 -> 그때까지의 홀수의 개수를 리스트에 추가하고 리턴! (나중에 최대 홀수의 개수, 최소 홀수의 개수를 출력한다.) 두 자리 -> 그 수를 두 개로 나눠서 합을 구해서 새로운 수로 생각한다. (12면 1과 2로 나눈다. -> 1+2를 해서 3을 새로운 수로 생각하기) => 새로운 수, 그때까지 홀수의 합 + 이 새로운 수에 들어간 홀수의 개수를 인자로 주어서, 또 함수에 넣는다. 세 자리 이..

흑흑 ㅠㅠㅠㅠ 드디어 맞았습니다.!! 이 문제는 무슨 알고리즘을 써야할까? 이런 고민보다는.. 아 이거 맞겠지 ? ? 이러고 돌렸는데 자꾸 틀렸다..ㅠㅠ 그러다가 이 분의 포스팅을 보고 어디에서 문제가 있었는지 알게 되었다 !! 아.. 이걸 설명하기 전에 아이디어를 쓰겠다! 아이디어 ✨ '입구에서 출구 방향으로 걸어갈 때 동쪽에서 서쪽으로 이동을 전혀 하지 않아도, 즉, 보행자의 현재 위치를 나타내는 좌표의 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='') #..