문제를 요약하면..if distancenow < dict: continue 이 조건문의 의미는현재 노드가 이미 처리된 노드인지 check하는 조건문으로, 방문한적이 있다면 거리비용을 바꿀 필요가 없으므로 반복문을 skip (continue) 한다.\-나는 dij
최소신장트리를 구하는 문제로 최소의 비용으로 우주신을 연결시키면된다.단, 이 문제의 포인트이자 다른 문제와의 차이점은 문제에서 일부 간선 edge가 주어진다.다시말해 일반적으로 최소 신장 트리문제는 크루스칼을 이용해서 최소의 비용의 합계를 구하면된다.여기서는 최소가 아
최소 신장 트리 (=최소 스패닝 트리 = Minimum Spanning Tree) 중에서 사용된 간선들의 가중치 합이 최소인 트리를 찾아간선의 가중치 합 최솟값 찾기!해결하기 위해서는 "크루스칼 알고리즘" 사용최소 비용 신장 트리 찾는 알고리즘가장 적은 비용으로 모든
흔한 DFS, BFS의 문제인 연결요소 개수를 구하는 것이다.단, 상하좌우 뿐만 아니라 대각선 경우도 연결되어있다!무한 재귀호출 방지를 위해 sys.setrecursionlimit(10000)을 꼭 써줘야 한다.코드가 맞더라도 이것 때문에 런타임에러 걸린다..백준 문제
입력한 문자 N을 3과 5로 나눌 수 있는 최소의 개수를 구하는 그리디 문제이다.코테 그리디 문제 중 가장 기본인 최소 동전의 개수로 거슬러주는 문제가 있다.그 문제에서 사용했던 방법을 사용했지만..실패..최소 동전의 개수로 거슬러주는 문제의 경우 항상 나누어 떨어지
전형적으로 쉬운 그리디 알고리즘 문제이다가장 최소의 동전개수로 거스름돈을 거슬러주기!Point!1) 가장 큰 동전부터 거슬러 주는 방법이 최소의 동전으로 거슬러주는 방법이다.2) 각 동전에 근접한 배수를 구하고 -> 뺀 나머지에서 또 다른 동전의 근접한 배수를 구하고
서롭 접두어가 겹치면 안된다!겹칠경우 False, 안겹칠 경우 True 반환해시는 사용할 필요가 없어 사용하지 않았다.정렬하면 무조건 접두어 겹치는 것끼리 연속적으로 위치할 것이다.for문을 이용해 차례대로 순회하며다음 요소와 접두어를 비교한다.단,다음 요소와 비교할
투 포이트이 기본을 충실히 사용해서 풀어보았다.정답start를 차례대로 순회하며 합계에 따라 end 값을 늘리는게 포인트!!
시간초과로 실패..defaultdict 사용해보기검색해서 참고해보았다..정답!원형이기 때문에 리스트 뒤에 추가적으로 붙여준다.
삽입정렬 이런거 써야하나 했는데..그냥 파이썬 리스트의 sort() 함수를 쓰면되는아주 간단간단한 문제였다..이 기능은 리스트의 요소가 모두 문자열일 때만 사용 가능하다!!위 리스트는 모두 int형이므로map을 이용해 형변환을 해준후 사용가능하다!!map(변환할 자료형
N 이하의 소수 중연속되는 소수의 합=N 이 되는 경우의 수 합 구하기1) N 이하의 소수 구하기 --> 에라토스테네스의 체 이용2) 합이 N이 되는 경우 찾기 --> 투 포인트 사용두 종류의 코드로 작성해봤다.첫 번째 코드는 매번 루프를 돌때마다 sum 함수를
이진트리 - 전위순회, 중위순회, 후위순회
이분탐색을 이용해 특정 수가 배열에 있는지 찾아내자!정렬되어 있다는 가정하에 사용 가능!반씩 나누며 특정 수를 찾아가는 알고리즘으로"정중앙 값"과 "찾고자 하는 값"의 계속되는 대소비교를 통해 위치를 찾아간다.숫자 갯수가 짝수 / 홀수 일 때 중앙값의 위치는 다음과 같
답은 맞지만 효율성 0...그 이유는 participat의 마지막 요소가 return 값일 때 인것 같다.for문을 다 돌아야 하는데 리스트 길이가 최대일 경우 연산 속도가 느려질 것이다.그렇다면..!해쉬를 공부해서 다시 풀어보자!hash 사용기존 답변들을 보며 참고했
나는 heapq 안쓰고 deque로 사용했다.heapq를 써서 정렬해야 하는 필요가 없고명령어 순서대로 "FIFO" 로직을 갖기 때문에 deque를 사용했다.처음에 걸린 에러는 ValueError: max() arg is an empty sequence 이게 무엇인가
쉽다 생각했는데..이렇게 했더니 시간초과 걸렸다..그렇다면..sys.stdin.readline()을 이용해보자!시간초과 해결!!기본 제공하는 input() 과 sys.stdin.readline()의 성능차이를 느낄 수 있는 문제였다.
\-scoville 리스트에서 최소값이 K (스코빌 지수) 이상이어야한다.\-scovile 리스트 모든 요소가 K 이상이 될 때 까지, 파이썬 heapq 사용heaqp 사용한 이유는? \-파이썬은 최소힙을 제공한다. \-min(scoville) <= K 대소비교
큰 문제를 작은 문제로 나누어 작은 문제의 답을 모아 큰 문제를 해결 동일한 작은 문제를 반복적으로 해결해야 할 때1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...점화식 사용 :인접한 항들 사이의 관계식 사용f(100)을 하면..엄청난 계산
요소개수 구하는 문제와 동일하다!2-1) 방문 여부 True/False를 저장하는 visited 리스트에서 True로 저장2-2) 별도 visited 리스트 없이 그래프에서 바로 1->0으로 바꾸기2-3) 2-1 & 2-2 둘다 쓰기 --다른 풀이보면 가끔 보이
1- 노드 수, 엣지 수, 탐색 시작노드 번호 입력받기2- DFS, BFS 구현하고3- DFS, BFS 별 탐색한 노드 순서 출력sys를 사용하면 좀더 빠르고 성능이 좋아진다고 한다.sys.stdin.readline 추가만 해주기!!혹시 풀다가 성능문제가 있다면 sys
자바 코테를 풀며 기본적으로 꼭 알아둬야 할것들을 정리해봤다. 기본적이지만 풀다보면 헷갈리는 부분이 많다.length배열의 길이를 알고자 할 때int\[] intArr = new int7; → intArr.length = 7 이다. → 요소를 7개 이하로 추가해도 길이