짱구 굴리기 (Q) - 52 [백준 1011] Fly me to the Alpha Centauri 오랜만에 문제 몇개 풀다가 올려봐용. 일단 이 문제를 풀기 위해서 저는 그냥 그림을 그려봤습니다. x y 가 0 11 인 상황의 그림을 봐볼게요 (x는 start로, y는 end로 하겠습니다) 처음 출발은 1칸으로 출발시킨다고 문제 그림에 나와있고, 도착도 1칸으로 도착해야된다 써있습니당 그래서 1. start와 end부터 번갈아가며 점프를 1칸, 2. 점프 후 사이에 거리가 있다면 점프를 1칸 늘려서 다시 start와 end에 번갈아서 해줍니다. ( 점프 횟수가 최소이여야 하기 때문에 최대한 뛸수있는 만큼 뛰어야함) 이렇게 진행하면 그림처럼 두개의 위치가 겹쳐버리는 곳이 생깁니다. 그럼 다시 그림의 맨 밑 박스상황에서 남은 점프거리가 2일 경우로 가서, 남은 2칸은 앞에서 3칸을 뛰었기 때문에 2로 정.. 2019. 7. 31. [백준 11047] 동전 0 그리디 알고리즘으로 해결하는 문제입니다... 사용할수 있는 동전 중 제일 큰 동전을 하나씩 쓰면 됩니다. 2019. 4. 23. [백준 1753] 최단경로 다익스트라 알고리즘 문제입니다. 일단 그래프를 인접행렬로 구현하게 되면 메모리 초과가 발생할거 같아 ( 정점 최대 갯수 20000 ) 인접 리스트로 구현했습니다. 처음에는 그냥 우선순위큐에 다음 위치 ( Integer로) 를 저장해 쓰다가 시간초과를 바로 먹었습니다. (원래 매 루프마다 방문하지 않은 정점 중 시작점으로 부터 가장 가까운 정점을 뽑는게 당연함. 안해서 빠꾸먹음) Comparator를 하나 만들어 거리가 가장 가까운 녀석이 높은 우선순위를 가질 수 있도록 합니다. while문의 변수 이름들이 상당히 지저분한데 우선순위 큐의 제너릭이 Integer에서 NextNode로 변했기 때문에 대충 고쳐서 통과만 시켰지만 보기엔 좀... 2019. 4. 22. [백준 2252] 줄 세우기 그래프의 위상 정렬 문제입니다. 위상정렬의 자세한 내용은 추후에 따로 올리도록 하고 일단 과정은 1. 자신을 가리키는 간선이 없는 정점을 찾아 큐에 넣음 2. 큐에서 빼어 (current) current에서 가리키는 정점(next)를 찾아 그 정점의 간선 카운트를 줄이고 이게 0이라면 큐에 넣음. 2019. 4. 19. 이전 1 2 3 4 5 6 ··· 13 다음
