전체 글

난이도: Lv.3유형: 그리디해결 여부: 오답내가 생각했던 아이디어/큰 가닥-#다익스트란가? 근데 최단거리가 문제가 아니라 최소 비용으로 모두 연결시키는게 문제 잘몰루겠다. 일단은 비싼다리순으로 하나씩 빼보고, 다리가 유지되는지 하는식으로 확인해보자말이 안될듯, 차라리 모든 다리 있는지 없는지에 따라 2^n 배열 만들고, 그 때의 가중치 다 더한다음에 최소비용부터 시작해 답나오면 바로 return근데 큰거 빼면서 하든, 2^n으로 모든 경우 다하든 차피 오답일것 같긴했음 오답 이유크루스칼 or 프림 알고리즘을 써야 했다. 그냥 이걸 몰라서 틀림 해답전형적인 MST 문제. 즉 최소 신장트리 문제다. 최소의 비용으로 사이클이 없이 모두 연결하는 트리 만들기. 이걸 구하는 대표적인 알고리즘 2개가 크루스칼, ..

난이도: Lv.3유형: 백트래킹해결 여부: 틀림내가 생각했던 아이디어/큰 가닥처음에는 굉장히 간단해보였다. 그런데, 가능한 경우의 수가 여러개 라는점. 그런데 항상 가능은 하기에 그걸 찾아야 한다는 것. 그래서 서순이나 이런거에 따라 달라질 수 있으며, 모든 경로를 사용해야 한다는 한붓그리기 같은 조건이 있지만, 단방향 화살표라 한붓그리기 로직을 그대로 활용 할 수 없다는 점은 어렵게 만들었다.그래서 일단 정렬 후에 완성 경로 하나 찾으면 바로 return 하는 식으로 DFS를 짜서 경로를 마무리하도록 해야겠다. 고 생각해서 짰고 틀렸다. 오답 이유copy 과정에서의 파이썬 특유의 얕은 복사 문제. copy 해서 복사본 써도 막힌다.백트래킹 고려 안함. DFS 인 동시에 백트래킹 문제여서 dfs 거치고 ..

난이도: Lv.3유형: 그래프 , 다익스트라, bfs해결 여부: 정답내가 생각했던 아이디어/큰 가닥bfs로 풀어야 겠다고 생각했고, 계산을 편하게 하기 위해서 따로 total이라는 딕셔너리 만들었다.오답 이유처음에 변수명이랑, -1 관리 헷갈려서 몇번 디버깅떄 틀리긴했는데 이후 정답 받았다. 해답뭐 해답코드에서 언급한 개선점은 굳이 inf 말고 -1 써도 된다는 점for a,b in x 이런식으로 바로 풀어서 for문 처리할 수도 있다는 점그냥 인덱스 오류 막기 위해 n+1 로 배열 잡는게 좀더 좋다는 점 변수명으로 graph랑 queue 는 예약어 아니어서 그냥 써도 될듯이경우는 bfs 이지만 만약에 노드마다 거리가중치가 있다면 다익스트라 써야한다#기억할 문법 #2차원 배열 빨리좀 만들자total=..

난이도: Lv.3유형: 그래프, 최단경로해결 여부: 틀림내가 생각했던 아이디어/큰 가닥으악 내가 약한 그래프 문제다. 어려워 보인다.그런데 가만 보니 일단 그래프 최단경로 for문 3번 돌아서 구해놓고, 그 걸로 특정 경로 최단으로 구하면 되지 않을까? 싶었다알고리즘 이름은 생각 안나는데 일단 했다. 오답 이유나중에 이를 알고보니 워셜-플로이드 알고리즘이라고 한다.거의 근접했다.틀린 이유는 단 하나, 워셜 플로이드에서는 경유지가 for문에 가장 바깥쪽에 있어야 한다. 그것만 고치니 맞았다.해답경유지를 가장 바깥으로 빼기 #기억할 문법 sum()은 인자가 최대 2개다.#내 오답코드# 일단 각 출발지-> 도착지 까지의 최소값 2차원 배열을 만들어야 하나?def shortestpath(n,fares): ..

난이도: Lv.3유형: DP해결 여부: 틀림내가 생각했던 아이디어/큰 가닥행렬 곱은 순서에 따라서 연산횟수가 달라지는데 그 연산횟수를 최소화 하는 방법에 대한 문제였다. 사실 행렬 곱 자체에 대한 이해가 없어서 한번 gemini한테 물어봤다. 그러고 나서, 일단 행렬곱을 가능하게 만드는 열을 찾고, 그게 큰 수부터 계산해서 제거해나가면 되지 않을까 싶었다. A * B 행렬과 B * C 행렬을 곱하면 A * C 가 되어서 B가 사라지니까... 커다란 B 부터 없애면 되지 않을까 싶었다. 즉 greedy로 푸나 싶었다. 하다가 이건 아닌거 같아서 중단하고 답을 봤다. 오답 이유근데 접근 방법 자체가 그게 아니었다. DP로 푸는거였는데 애초에 나는 큰 오해를 하고 있었다.주어진 행렬끼리 가능만 하다면 순서를 ..

난이도: Lv.3유형: 이분 탐색해결 여부: 포기내가 생각했던 아이디어/큰 가닥큰 가닥은 대충 이분탐색으로 적당한 완료시간을 먼저 구한다음에, 이후부터 스케쥴링 이미 올라간거랑 앞으로 될것들해서 마무리 작업 해주는걸로 구하는것일것 같았다.근데 그게 아닌것 같아서 시간도 다 되었고 해서 그냥 답 봤다. 오답 이유해답근데 그게 맞았다.적당한 시간을 잡은 이후에 스케쥴링 이미 되어 있는건 어카는지가 문제였는데, 그냥 신경을 안쓰면 되었다. 우리는 그냥 들어가는 순간만 포착하면 된다. % 연산으로 이를 해낼 수 있다. #기억할 문법 #내 오답코드#정답코드def solution(n, cores): # 1. n이 코어 개수보다 작거나 같으면 바로 n 반환 if n = n: target..

난이도: Lv.3유형: DP해결 여부: 오답내가 생각했던 아이디어/큰 가닥전형적이고 쉬운 문제라고 생각했다. DP를 사용해서 풀면 될거 같았고, 주된 식으로는 거스름돈 종류만큼 이전 dp 배열에다가 다 합하고, 같은 종류 예방을 위해 1을 빼주는 복잡한 점화식을 생각했다. 오답 이유근데 이러면 재귀도 너무 깊어지고, 점화식도 복잡하다. 훨씬 간단한 해법이 있었다. 해답그냥 화폐 종류별로 하나씩 꺼내서 이전 만큼 더해주는 거였다. 생각보다 훨씬 간단했다.잘못된 사고 (Top-down의 위험): "n원을 만들기 위해 화폐들을 조합해보자." (중복 발생 위험↑)올바른 사고 (Bottom-up): "지금까지 1원짜리로만 만들 수 있는 경우의 수를 다 구해놨어. 이제 여기에 2원짜리 동전을 쓸 수 있다는 허락이 ..

난이도: Lv.3유형: 그리디해결 여부: 정답내가 생각했던 아이디어/큰 가닥그 뭉텅이로 간격의 길이들만 기록하는 배열이 필요하다는 건 캐치했다.그 배열을 만들기 위해 보조로 범위를 표시하는 리스트나 visited 배열을 만들어야 하나 생각했다.근데 복잡한 visited나 배열 연산 없이 그냥 바로 연산해서 나올 수 있다는 걸 깨닫고 그렇게 했다.오답 이유정답임해답다듬는 다면 이런것들을 다듬을 수 있다고 한다.지금처럼 temp 에 추가 한후 다시 temp를 순회하며 처리하는게 아니라 바로 처리해버리기if- else로 나머지에 따른 올림 처리 하지말고 (a + b - 1) // b 하는 식으로 천장을 구현하기#기억할 문법 #내 정답코드def solution(n, stations, w): answer =..