전체 글
-
1976번 여행 가자 / BOJ백준 2020. 4. 6. 08:08
문제링크 : https://www.acmicpc.net/problem/1976 제출링크 : https://www.acmicpc.net/source/18943097 자바코드 : https://github.com/skysign/WSAPT/blob/master/BOJ/1976번 여행 가자/src/Main.java 1717번과 비슷하게 풀 수 있는 문제로, union find 를 사용해서 풀 수 있습니다. 문제의 아래 문장을 통해서, union find 로 풀 수 있다는 것을 유추할 수 있습니다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다. 길은 B-C..
-
[후기] 2019 카카오 인턴십 코딩 테스트, 실전 모의고사카테고리 없음 2020. 3. 29. 08:15
https://programmers.co.kr/competitions/145/kakao-internship-test 2019 카카오 겨울 인턴십 기출문제를 풀어보는 모의고사입니다. 어제 3월 28일 오후에 모의고사가 있었어요. 결과는... 반은 넘게 맞췄네요 ^^a 아쉽게도 문제풀이에 대한 포스팅은 작성할 수 없네요. ( * 작성할 수 없는 이유는 오른쪽 링크 참고하세요. https://blog.niceb5y.net/2019-kakao-developer-winter-internship-solution/ ) 그래도 좀 테스트 내용이 궁금하다. 아래 링크를 참고하세요. https://zoomkoding.github.io/codingtest/2019/11/09/2019-kakao-winter-intern-1...
-
고대어 사전 / ALGOSPOT / V2 풀이 O(N)ALGOSPOT 2020. 3. 27. 18:06
이전 포스팅에서 그래프를 어떻게 코딩할 것인지? 에 대해서 알아 보았습니다. 이번에는 만든 클래스들(Vertex, DirectedEdge)을 가지고 문제를 풀어 보겠습니다. 고대어 사전 / ALGOSPOT / V2 풀이 O(N) 문제링크 : https://algospot.com/judge/problem/read/DICTIONARY 제출링크 : https://algospot.com/judge/submission/detail/664902 문제해설 : https://skysign.tistory.com/197 import java.io.BufferedWriter; import java.io.IOException; import java.io.OutputStreamWriter; import java.io.DataI..
-
시간 복잡도를 보다 빠르게~ 고대어 사전 / ALGOSPOTALGOSPOT 2020. 3. 27. 17:11
문제링크 : https://algospot.com/judge/problem/read/DICTIONARY 이전 포스팅에서 답은 나오지만, 너무 느린 O(N^2) 시간 복잡도를 가진 코드로 작성해서, 이번에는 시간 복잡도를 개선하는 코딩방법에 대해서 알아 보겠습니다. DICTIONARY / ALGOSPOT 문제는 Topological sort를 사용해서 푸는 문제입니다. Topological sort는 그래프에 속해있는 vertex와 edge에 따라서 정렬하는 방식임으로, 우선 그래프(graph)를 어떻게 코딩할지를 알아 보겠습니다. 그래프 코딩 방법 크게 2가지 방법이 있구요, 리스트와 2차원 배열을 이용하는 방식입니다. HashMap과 같은 container를 사용해서, vertex와 edge를 구현하는..
-
고대어 사전 / ALGOSPOTALGOSPOT 2020. 3. 26. 17:09
문제링크 : https://algospot.com/judge/problem/read/DICTIONARY 제출링크 : https://algospot.com/judge/submission/detail/664699 자바코드 : https://github.com/skysign/WSAPT/blob/master/ALGOSPOT/DICTIONARY/src/Main.java Topological sort를 사용해서 문제를 풀 수 있습니다. 우선 Topological sort 공부하실 분들은 여기를 참고하세요. 제가 검색해서 찾은 한글 자료중에는 가장 잘 설명되어 있는 블로그 입니다. 문제를 푸는 과정은 크게 3단계 입니다. 첫번째 단계가, 알파벳 2자의 우선순위를 vertex와 directed edge로 나타 내는 것..
-
13398번 연속합 2 / BOJ백준 2020. 3. 23. 13:42
13398번 연속합 2 / BOJ 문제링크 : https://www.acmicpc.net/problem/13398 제출링크 : https://www.acmicpc.net/source/18618083 자바소스 : https://github.com/skysign/WSAPT/blob/master/BOJ/13398%EB%B2%88%20%EC%97%B0%EC%86%8D%ED%95%A9%202/src/Main.java 이 문제를 풀기 전에, 1912번 연속합 / BOJ 문제를 꼭 풀어보시고, 여기 참고하세요 → https://skysign.tistory.com/193 Dynamic Programming과 Prefix Sum을 사용해서 푸는 문제입니다. 이 문제에 대한 설명은 여기 참고하세요 → https://coo..
-
1912번 연속합 / BOJ백준 2020. 3. 22. 20:26
1912번 연속합 / BOJ 문제링크 : https://www.acmicpc.net/problem/1912 제출링크 : https://www.acmicpc.net/source/19909239 유튜브 문제풀이 : https://www.youtube.com/watch?v=dAtNiVwnTN4 자바코드 : https://bit.ly/3dWeknw 어떻게 푸는 문제인지 좀 고민하다가, 이 문제가 잘 설명된 글을 찾았습니다. 여기 참고하세요. → https://debuglog.tistory.com/79 1차원 DP로 푸는 문제입니다. $$ dt_i $$ dt_i 가 i 번째 입력 받은 값, (data를 줄여서 dt) 이라고 하고, $$ dp_i $$ i 번째 입력까지 고려했을 때, 최대 연속 부분합 코딩을 좀 쉽..
-
힙(Heap)의 2가지 코딩(루프 vs 리커전)카테고리 없음 2020. 3. 8. 21:18
알고리즘에서 힙(Heap) 이란? 바이너리 트리를 사용해서, 부모노드의 값이, 2개의 자식노드 보다 항상 크도록 유지하는 것이 힙 입니다. 따라서, 루트노드는 항상 전체 트리에서 가장 큰 값을 가지게 됩니다. (반대로 부모노드값이 자식노드 보다 항상 작게 유지하는 것도 가능하지만, 여기서는 크도록 유지하는 힙만 다루겠습니다.) 이런 힙의 성질을 활용하여 정렬하는 방식을 Heap Sort라고 하고, $$ O(N \cdot {log_2 N}) $$ 시간복잡도로 정렬이 가능한 정렬방식입니다. 여기서는 힙의 2가지 코딩방식(루프/리커전)에 대해서 알아 보겠습니다. 자바 소스 코드 : https://github.com/skysign/WSAPT/blob/master/Heap%20sort/src/com/tistory..