전체 카테고리
[백준] 8958번 : OX퀴즈 - [C++]
[백준] 8958번 : OX퀴즈 - [C++]
2021.12.09https://www.acmicpc.net/problem/8958 8958번: OX퀴즈 "OOXXOXXOOO"와 같은 OX퀴즈의 결과가 있다. O는 문제를 맞은 것이고, X는 문제를 틀린 것이다. 문제를 맞은 경우 그 문제의 점수는 그 문제까지 연속된 O의 개수가 된다. 예를 들어, 10번 문제의 점수 www.acmicpc.net 문제 이 번 문제도 그리 어렵지는 않을 것이다. 필자가 보기엔 입력받은 문자열을 어떻게 다루느냐를 이해하고자 하는 의도가 아닐까 싶다. 알고리즘 [접근 방법] 문제를 이해하는 것은 그리 어렵지 않을 것이다. 우리는 두 가지 규칙만 따르면 된다. 각 케이스마다 점수를 출력한다. O 의 연속 개수 만큼 점수를 누적하여 합산하고 X가 나오면 누적값은 0으로 초기화 된다. 즉, X혹은..
[백준] 2110번 : 공유기 설치 - JAVA [자바]
[백준] 2110번 : 공유기 설치 - JAVA [자바]
2021.12.08https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 문제 문제를 정확히 파악만 한다면 매우 쉬운 문제다. 알고리즘 [접근 방법] 그동안 숫자 카드, 랜선 자르기, 나무 자르기를 순서대로 풀어왔다면, 이 번 문제는 그리 어렵지는 않았을 것이다. 그럼에도 정답률이 낮은 이유라 한다면, 아마 이분탐색 구현을 제대로 하지 않았기 때문일 가능성이 매우 높지 않을까 생각을 해본다만.. 그렇기 때문에 필자가 ..
자바 [JAVA] - 팀 정렬 (Tim Sort)
자바 [JAVA] - 팀 정렬 (Tim Sort)
2021.11.02[정렬 알고리즘 모음] 더보기 1. 계수 정렬 (Counting Sort) 2. 선택 정렬 (Selection Sort) 3. 삽입 정렬 (Insertion Sort) 4. 거품 정렬 (Bubble Sort) 5. 셸 정렬 (Shell Sort) 6. 힙 정렬 (Heap Sort) 7. 합병(병합) 정렬 (Merge sort) 8. 퀵 정렬 (Quick Sort) 9.이진 삽입 정렬 (Binary Insertion Sort) 10. 팀 정렬 (Tim sort) - [현재 페이지] Tim Sort [팀 정렬] 이번 포스팅의 경우 병합 정렬과 삽입 정렬(그 중 이진 삽입 정렬) 메커니즘을 토대로 하기에 반드시 병합(합병) 정렬과 이진 삽입 정렬을 먼저 보고 오시기를 바란다. (참고로 여기서 다룰 병합 정렬은..
[백준] 1546번 : 평균 - [C++]
[백준] 1546번 : 평균 - [C++]
2021.10.20https://www.acmicpc.net/problem/1546 1546번: 평균 첫째 줄에 시험 본 과목의 개수 N이 주어진다. 이 값은 1000보다 작거나 같다. 둘째 줄에 세준이의 현재 성적이 주어진다. 이 값은 100보다 작거나 같은 음이 아닌 정수이고, 적어도 하나의 값은 0보 www.acmicpc.net 문제 이 번에는 평균을 구하는 문제다. 다만, 약간 특수한 성적 조작 평균을 구하는... 알고리즘 [접근 방법] 문제 자체는 그리 어렵지 않을 것이다. 약간의 특수한 수식이 필요한데, 일단 요구되는 조건은 주어지는 값들 중 가장 큰 값을 찾는 것. (이를 M이라고 함) 그리고 조작 된 성적을 구하는 수식은 다음과 같다. 조작 된 성적 = ( 단일 과목 / M ) * 100 그러면 평균은 다음..
[백준] 3052번 : 나머지 - [C++]
[백준] 3052번 : 나머지 - [C++]
2021.10.06https://www.acmicpc.net/problem/3052 3052번: 나머지 각 수를 42로 나눈 나머지는 39, 40, 41, 0, 1, 2, 40, 41, 0, 1이다. 서로 다른 값은 6개가 있다. www.acmicpc.net 문제 알고리즘 [접근 방법] 직전 문제인 숫자의 개수 문제를 푼다면 그리 어렵지 않게 풀 수 있는 문제다. 사실 문제 자체는 숫자의 개수와 거의 다르지 않고, 다만 나머지를 구해줄 뿐이니.. 그리 어렵지 않게 풀 수 있을 것이다. 혹시 해당 문제를 풀고오지 않았다면 아래 링크를 통해 먼저 풀어 보고 오시는 것을 추천한다. https://st-lab.tistory.com/271 [백준] 2577번 : 숫자의 개수 - [C++] https://www.acmicpc.net..
[백준] 2577번 : 숫자의 개수 - [C++]
[백준] 2577번 : 숫자의 개수 - [C++]
2021.09.27https://www.acmicpc.net/problem/2577 2577번: 숫자의 개수 첫째 줄에 A, 둘째 줄에 B, 셋째 줄에 C가 주어진다. A, B, C는 모두 100보다 크거나 같고, 1,000보다 작은 자연수이다. www.acmicpc.net 문제 이 번 문제는 그리 어렵지 않은 문제다. 다양한 풀이 법을 통해 접근해보도록 하자. 알고리즘 [접근 방법] 워낙 풀이 방법이야 다양하기 때문에 앞으로 다른 문제들을 풀어나가면서 많이 쓰게 될 방법들을 미리 터득할 겸 크게 두 가지 방식으로 접근해보고자 한다. 문제 본문은 길지만, 핵심은 하나다. 3개의 수를 곱한 수에 대해 각 자릿수들이 0~9까지 각각 몇 번 나왔는지를 출력하면 되는 문제다. 그러면 어떻게 풀이해야 할까? 바로 배열의 인덱스를 ..
[백준] 2805번 : 나무 자르기 - JAVA [자바]
[백준] 2805번 : 나무 자르기 - JAVA [자바]
2021.09.12https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 이 전의 랜선 자르기 문제와 매우 유사한 문제다. 만약 직전 문제를 안풀어보셨다면 먼저 풀고오는 것을 추천한다. 그러면 이 문제도 자연스럽게 바로 풀릴 것이다. 알고리즘 [접근 방법] 이 번 문제는 앞서 언급했듯 랜선 자르기 문제와 풀이 방식이 거의 같은 문제다. 이 문제를 풀기 전에 되도록이면 아래 글을 먼저 보고 오시는 것을 추천한다. 모두 다 연계..
[백준] 1654번 : 랜선 자르기 - JAVA [자바]
[백준] 1654번 : 랜선 자르기 - JAVA [자바]
2021.08.31https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 이분 탐색의 응용 문제다. 알고리즘 [접근 방법] 일단, 이 번 문제를 풀기 전에 이분 탐색 중 Upper Bound 에 대해 이해하고 있어야 한다. 그러니, 해당 원리를 이해하기 위해 아래 포스팅을 먼저 보시고 오시기를 바란다. https://st-lab.tistory.com/267 [백준] 10816번 : 숫자 카드 2 - JAVA [자바] https://ww..
[백준] 2562번 : 최댓값 - [C++]
[백준] 2562번 : 최댓값 - [C++]
2021.08.17https://www.acmicpc.net/problem/2562 2562번: 최댓값 9개의 서로 다른 자연수가 주어질 때, 이들 중 최댓값을 찾고 그 최댓값이 몇 번째 수인지를 구하는 프로그램을 작성하시오. 예를 들어, 서로 다른 9개의 자연수 3, 29, 38, 12, 57, 74, 40, 85, 61 이 주어 www.acmicpc.net 문제 그리 어려운 문제는 아니다. 아마 많은 분들은 쉽게 풀었을 것 같다. 알고리즘 [접근 방법] 이 문제 자체는 어렵지 않다. 총 9개의 서로 다른 자연수가 주어지면, 주어진 수에서 최댓값과 그 최댓값이 몇 번째로 주어졌는지를 출력하면 되는 문제다. 다만, 유의해야 할 점이라면 배열을 정렬을 시켜버리면 안된다. 우리가 출력해야 하는 건, 최댓값과 최댓값이 몇 번째..
[백준] 10816번 : 숫자 카드 2 - JAVA [자바]
[백준] 10816번 : 숫자 카드 2 - JAVA [자바]
2021.08.06https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제 직전 문제랑 비슷하지만, 이분 탐색을 활용해야 할 경우 조금 고려해야 할 부분이 있는 문제다. 알고리즘 [접근 방법] 이 문제 자체는 그리 어렵지 않다. 사실 이분 탐색을 쓰지 않고도 카운팅 정렬 형식을 사용하여 풀 수도 있다만, 그래도 이분 탐색 카테고리에 있는 만큼 한 번 이분 탐색 풀이 방식을 통해 풀이를 해보도록 하자. 일단, 이분 탐색의 경우 구간의..