알고리즘, 문제해결/알고리즘 문제풀이80 [백준 2042번] 구간 합 구하기 난이도: 골드 I 문제 링크: https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 이 문제는 세그먼트 트리라는 알고리즘을 알아야 풀 수 있는 문제입니다. 기본적인 설명은 여기를 참고해 주세요. 세그먼트 트리의 기본적인 문제입니다. 한 가지 유의할 점이 있다면, 값을 수정할 때입니다. b의 값을 c만큼 수정하는 것이 아니라, b의 값을 c로 수정하는 것입니다. 따라서 차이값 differenc.. 2021. 9. 25. [백준 16438번] 원숭이 스포츠 난이도: 골드 III 문제 링크: https://www.acmicpc.net/problem/16438 16438번: 원숭이 스포츠 승민이는 동물원의 원숭이들을 관리하는 사육사입니다. 이 동물원에는 N마리의 원숭이들이 있고 원숭이들에게 1번부터 N번까지 번호를 붙였습니다. 7일간 동물원에서 원숭이들끼리 스포츠 경기 www.acmicpc.net 문제의 설명이 조금 어려운데, 요약하면 다음과 같습니다. N개의 원소에 대해, 총 7번의 기회 이내에 배열 내의 원소 i가 원소 j (i != j)와 다른 경우가 적어도 한 번 이상 존재해야 합니다. 문제의 조건을 유심히 살펴보고 분석해 보면 다음과 같은 사실을 알 수 있습니다. N은 최대 99인데, 주어진 주는 7주입니다. 전체 원숭이를 재귀적으로 반씩 나누어 팀을.. 2021. 9. 18. [백준 1517번] 버블 소트 난이도: 플래티넘 V 문제 링크: https://www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다. www.acmicpc.net 분할-정복 (divide & conquer) 문제입니다. n은 최대 50만이므로, 모든 원소에 대해 모든 다른 원소와 비교해 보는 식으로 하면 시간 초과가 납니다 (O(N^2)). 재귀 방식으로 배열을 구간별로 나누어 접근하도록 합니다. 나눈 구간에 대해 정렬하기 전 swap 횟수를 세고, 정렬되는 값을 별도의 배열에 기록한 후 (arr2).. 2021. 9. 17. [백준 1300번] K번째 수 난이도: 골드 III 문제 링크: https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net N의 최대 크기가 10만이므로, 배열에 들어갈 모든 수를 계산하기에도 벅찹니다 (10만 x 10만 번의 연산). 따라서 이 문제는 모든 숫자를 계산하지 않고 풀 수 있어야 합니다. K번째 수를 구한다는 것은, 이보다 작은 수가 K-1개 존재한다는 뜻입니다. 이러한 상황에서 비교 연산을 훨씬 덜 하면서 원하는 수를 탐색하는 방법 중 하.. 2021. 9. 17. [프로그래머스] 입실 퇴실 문제 링크: https://programmers.co.kr/learn/courses/30/lessons/86048 코딩테스트 연습 - 7주차 사회적 거리두기를 위해 회의실에 출입할 때 명부에 이름을 적어야 합니다. 입실과 퇴실이 동시에 이뤄지는 경우는 없으며, 입실 시각과 퇴실 시각은 따로 기록하지 않습니다. 오늘 회의실에는 programmers.co.kr 굉장히 좋은 문제라고 생각합니다! 저는 처음에는 약간 단순한 방법으로 풀었는데... 1. 들어온 시간 기준 a > b, 나간 시간 기준 a < b이거나 그 반대이면 반드시 만난다. 2. 그렇지 않은 경우, 들어온 두 사람의 시간 사이에 들어오지 않은 사람이 먼저 나간 사람보다 더 먼저 나간 경우, 두 사람은 반드시 만난다. 위 조건을 매번 확인하는 식.. 2021. 9. 17. [백준 3687번] 성냥개비 난이도: 골드 II 문제 링크: https://www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net 제가 느끼기에 이 문제는 DP와 그리디를 이용하는 부분으로 나뉩니다. 그리디를 이용하는 부분은 최댓값을 구하는 부분으로, 상대적으로 더 쉽습니다. 성냥개비가 짝수개 있을 때는, 모두 1을 만들면 됩니다 (자릿수를 크게 함). 1을 만드는 데 성냥개비가 2개 소모되므로, 총 (성냥개비 개수 / 2)개의 1을 출력합니다. 성냥개비가 홀수개 있을 때는, 맨 앞자리에 7을 출력하.. 2021. 9. 9. 이전 1 ··· 4 5 6 7 8 9 10 ··· 14 다음
