Backjoon22

• 

  Backjoon[백준] - 버블 소트_1517 - Java 이 문제는 이름만 버블 소트이지 다른 정렬을 이용하여 풀어야한다.N의 최대 범위가 1,000,000,000의 범위이므로 O(nlogn)인 정렬을 사용해야 한다.직전에 병합 정렬을 사용했으니 병합 정렬을 사용했다.병합 정렬을 사용하여 정렬할 때 왼쪽 배열에 남아 있는 숫자만큼  체크해서 result로 알려주면 된다.단, 배열의 자료형은 long 자료형을 사용해야한다. (왜 indexoutofboundsexception이 발생했는지 한참을 찾았다...바로 코드로 보면 알 수 있다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;publi.. Backjoon 2024. 5. 6.

• 

  Backjoon[백준] - 수 정렬하기 2_2751 - Java 이번 문제는 N의 최대 범위가 1,000,000이므로 시간 복잡도는 O(nlogn)의 시간복잡도를 가진다.내가 알고있는 정렬 중 O(nlogn)의 시간복잡도를 갖고 있는 정렬은 힙정렬이나, 퀵정렬 등등이다.자바에 내장되어 있는 정렬을 사용해도 되지만, 병합정렬을 구현해볼꼄 병합정렬을 사용하여 풀었다.병합 정렬, 합병 정렬이라고 불리는 정렬은 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.합병정렬은 분할 정복(divide and conquer)방법에 바탕을 두고 있다.분할 정복 방법은 문제를 작은 2개의 문제로 분리하고 각가을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전력이다.분.. Backjoon 2024. 4. 28.

• 

  Backjoon[백준] - K번째 수_11004 - Java 이 문제는 언 뜻보면 K번째 수를 구해야하는 것에 포커스가 맞출 수 있지만, 핵심은 최대한 빠른 정렬을 사용하는 것이다. 물론 자바에 내장되어 있는 Collection.sort(TimSort)와 ArraysSort(dual-pivot quick sort)를 사용하면 정말 쉽게 해결할 수 있다. 하지만 자바에 내장되어 있는 정렬 메서드를 사용하는 것은 알고리즘 공부하는 의미가 없다. 어떤 것이 최대한 빠른 정렬일까? 그렇다 퀵정렬이다. 하지만 피벗 선택에 따라 run time이 달라진다. 실제로 왼쪽이나 오른쪽 피벗을 선택하고 해당 문제를 제출하면 시간 초과가 발생한다. 왼쪽 피벗 선택 : import java.io.BufferedReader; import java.io.IOException; import.. Backjoon 2024. 3. 21.

• 잠시 백준 풀기를 쉬면서 나는 항상 알고리즘 문제를 풀면서 내가 풀이를 찾아내면서 어떤 깨달음을 얻는건가, 아니면 내 스스로 해법을 찾아내는 건가 의문이 계속 들었다. 물론 매일 열심히 하지 않았다. 하지만 하면서 계속 근본적인 것을 잊고 그저 코딩테스트, 이직 만을 위한 알고리즘을 계속 해왔던 것 같다.(그래서 속도가 안붙고 그냥 의무적으로만 했던 것 같다.) 알고리즘은 실무에서 거의 안쓰인다. 나도 알고 있다. 하지만 내가 알고리즘을 계속 열심히 하려고 했던 이유는 개발자라는 직업이 단순히 어떤 것을 만들고 어떤 것을 유지보수만 하는 직업이 아니라는 것을 알기 때문이다. 학교에서 배웠을 때로 다시 돌아가 근본적인 알고리즘에 대해 다시 배워보려고 한다. '프로그래밍 대회에서 배우는 알고리즘 문제해결전략' 일명 종만북을 사서 공.. Backjoon 2023. 6. 11.

• 

  Backjoon[백준] - ATM_11399 - Java 해설 서론이 조금 길지만, 결국은 오름차순으로 정렬해야 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력할 수 있다. 그렇다. 정렬 문제다. N의 최댓값이 1,000이고 시간 제한이 1초이므로 시간 복잡도가 O(2^N)이하인 정렬 알고리즘 중 아무거나 사용해도 된다. ( 어떤 정렬을 사용해도 된다.) 여기서는 삽입정렬을 사용하겠다. 삽입 정렬은 밑의 사진만 봐도 바로 이해가 갈정도로 어렵지 않은 정렬이다. 정렬 대상값이 i만큼 증가하고 그 i 범위 값 안에 있는 값들을 적절한 위치에 삽입하는 것이다. (c)에서 '5'가 3~7 사이에 삽입되고 7의 index가 하나 밀려난다. 정렬이 끝나면 마지막으로 배열의 합 배열을 만들어야한다. 왜냐하면 n번째 사람은 n-1번째 사람이 ATM기기에서 돈을 .. Backjoon 2023. 5. 15.

• 

  Backjoon[백준] - 소트인사이드_1427 - Java 푸는 법 내림차순! 선택정렬을 이용하여 풉니다. 1. [2, 1, 4, 3]에서 최댓값을 찾습니다. 4를 맨앞으로 바꾸고 2. [4, 1, 2 ,3] 1번째 배열부터 n번째 배열까지 최댓값을 찾아 [4, 3, 1, 2] 3. 계속 내림차순이 될때까지 반복하면 됩니다. 너무나도 쉬운 선택정렬. import java.util.Scanner; public class P1427 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String str = sc.next(); int A[] = new int[str.length()]; for(int i=0; i Backjoon 2023. 5. 1.

• 

  Backjoon[백준] - 버블 소트_1377 - Java 풀이 방법 버블 정렬의 시간 복잡도는 (N^2)이고 N의 최대 범위가 500,000이므로 기존 버블정렬을 돌려 문제를 풀면 시간을 초과하게 됩니다. 그래서 조금 생각을 하고 풀어야 합니다. 문제의 요점은 swap이 일어나지 않는 반복문의 i값을 찾는 것이 요점이다. 위 코드를 보시면 이중 포문의 안쪽 루프에서 1에서 n-i까지, 배열의 왼쪽에서 오른쪽으로 이동하면서 Swap을 수행하는데 이는 특정 데이터가 swap으로 왼쪽으로 이동할 수 있는 최대거리가 1이라는 뜻입니다.그래서 데이터의 정렬 전 index와 정렬 후 index를 비교해 왼쪽으로 가장 많이 이동한 값을 찾으면 이 문제를 풀 수 있습니다. 근데 여기서 의문이 드는 한 가지가 떠오릅니다. 왜? 왜 왼쪽으로 가장 많이 이동한 값을 찾으면 문제의.. Backjoon 2023. 4. 24.

• 

  Backjoon[백준] - 수 정렬하기_2750 - Java 위 문제는 sort()로 쉽게 정렬할 순 있지만, 버블 정렬을 통해 문제를 풀었다. 위의 이미지 처럼 첫번째 정렬에 제일 큰 수를 뒤쪽으로 보내고 그 다음 큰 수를 2번째 수로 정렬이 끝날 때까지 계속 뒤로 보내는 것이 버블 정렬이다. 너무 쉬워서 이걸 내가 지금 공부하는게 맞나? 싶을 정도다. 바로 코드로 보겠다. import java.util.Scanner; public class P2570 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int A[] = new int[N]; for(int i=0; i Backjoon 2023. 4. 11.

• 

  Backjoon[백준] - 절댓값 힙_11286 - Java 우선 힙이라는 것을 알아보자. 내가 정리한 것 보다 이 분이 정리한 것이 정말 많이 도움이 됐다. 세상엔 참 고수가 많다. https://dy-coding.tistory.com/entry/%EB%B0%B1%EC%A4%80-11286%EB%B2%88-%EC%A0%88%EB%8C%93%EA%B0%92-%ED%9E%99-java 보통 힙은 최대 힙과 최소힙이 나뉘는데, 최소 힙은 "루트 노드가 완전 이진트리에서 가장 작은 값이고 부모 노드가 자식 노드 보다 작아야 한다." 라는 규칙을 가지고 최대 힙은 "루트 노드가 완전 이진트리에서 가장 큰 값이고 부모 노드가 자식 노드 보다 커야 한다"라는 규칙을 가지고 있다. 그 중 절댓값 힙을 구현하려면 기준을 절댓값으로 다시 잡아야 한다. 절댓값 힙을 구현하는 방법은.. Backjoon 2023. 4. 7.

• 

  Backjoon[백준] - 카드2_2164 - Java 이 문제는 큐의 구조만 알면 쉽게 풀 수 있는 문제다. poll() : 큐의 맨 앞 요소를 제거하고 반환합니다. peek() : 큐의 맨 앞 요소를 반환합니다. 요소는 제거하지 않습니다. isEmpty() : 큐가 비어 있는지 여부를 반환합니다. 앞의 있는 카드(정수 값)을 삭제하고(poll) 그 다음 똑같이 삭제한 뒤(poll) add하면 된다. 언제까지? 1장 남을 때까지... 이 문제가 왜 실버인지는 모르겠지만, 엄청 쉬운 문제였다. 코드 또한 엄청 간략하다. 이 문제를 통해 또 새로 배운 것은 큐를 구현할 때 LikedList를 쓰면 더 빠르게 처리할 수 있다는 것이다. LinkedList는 노드라는 개별적인 객체들을 연결하여 구성되어 있으며, 각 노드는 이전 노드와 다음 노드를 가리키는 포인터를.. Backjoon 2023. 3. 19.

• 

  Backjoon[백준] - 오큰수_17298 - Java *Pop은 스택에서 꺼내는 것이므로 정답 배열에 추가하는것. *push는 배열에 있는 값을 꺼내 스택에 넣는 것이므로 배열의 다음 인덱스를 본다는 것. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Stack; public class P17298 { public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new Input.. Backjoon 2023. 3. 17.

• 

  Backjoon[백준] - 스택수열_1874 - Java 일단 문제를 풀기에 앞서 스택에 대해 다시 알아가야 한다. 스택은 학교 다닐때도 배웠고, 책으로 다시 공부했을 때도 배웠다. 기본중에 기본. https://pocoding1wer.tistory.com/18 -> 이 글에도 스택을 구현한 예제가 있다. 하지만 다시 정리 해볼려고 한다. 그림으로 볼 수 있듯이 삽입 삭제가 후입선출로 이루어지는 자료구조이다. 후입선출은 Last-in First-out이라고 불리며 보통 줄임말로 LIFO라고 불린다. 비슷한 것으로 FIFO(First-in First-out)이 있다. push로 새값이 들어가면 top이라는 포인터는 새값을 가리키고, 값을 빼낼 때 pop은 top을 가리키는 값을 스택에서 뺀다. 또한 현재 가장 상단에 있는 데이터를 알고 싶을 때 peek를 호출한.. Backjoon 2023. 2. 6.