끄적끄적

글 전부 비공개

문제 programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr 풀이 나는 이 문제를 그냥 벡터를 이용해서 풀었다. 장르별로 노래 재생 횟수를 저장하고, 장르 내에서 노래 재생 횟수가 많고, 고유번호가 작은 것부터 출력하는 순으로 코드를 작성했다. 코드 #include #include #include using namespace std; vector solution(vector genres, vector plays) { vector..

문제 www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 점화식 숫자가 0일 때는 1만 가능하고, 9일 때는 8만 가능하다. 그래서 0인 경우, 1~8인 경우, 9인 경우를 나눠서 계산하면 된다. 코드 #include #define MOD 1000000000 using namespace std; int main(){ int n; long arr[101][10] = {0, }; scanf("%d", &n); for(int i=1;i

문제 www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 풀이 DFS로 풀었다. 나는 이 문제를 정말 직관적으로 풀었다.. 1. 빙산이 몇 조각인지 확인 2. 빙산이 두 조각 이상인지 확인. 맞으면 종료 3. 빙산 녹이기 4. 빙산이 다 녹았는지 확인하기. 다 녹았으면 종료 여기서 포인트는 visited의 활용이다. 2단계에서 visited는 해당 빙산을 방문했는지 확인하는 용도로 쓰였다면, 3단계에서는 사방에 0이 몇 개 있는지 저장하는 용도로 사용했다...

문제 www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 풀이 시간초과 안나는 코드_1에 대한 설명 이 문제를 풀려면, 우선순위 큐가 2개가 필요하다. "값이 작은 수들을 저장하는 큐"와 "값이 큰 수들을 저장하는 큐" ** 항상 중간값이 중간에 있거나 짝수라면 두 수 중에 작은 값을 출력해야 하기 때문에 항상 pqMin부터 값을 채워준다. pqMin이나 pqMax가 비어있다면, 비어있는 큐에 값을 저장하면 된다. pqMin은 내림차순으로 정렬되..

문제 www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 이 문제를 풀기 위해 이차원 배열 adj와 visited를 선언했다. adj는 입력받은 배열이고, visited는 방문했는지 확인하기 위한 배열이다. 처음에 적록색약이 아닌 사람의 구역을 계산하기 위해서 dfs를 돈다. 구역의 갯수가 몇 개인지 구하는 것이기 때문에 구역을 방문할 때마다 cnt값을 +1해주면 된다. 후에, 적록색약인 사람의 구역을 계산하기 위해 for문을 돌면서 G를 R로 다 ..

문제 www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 이 문제도 우선순위 큐를 이용해서 풀 수 있는 문제였다. 이 문제의 포인트인 ⭐️절대값⭐️이 중요하므로 우선순위 큐에 pair를 사용했다. 그래서 first에는 절대값을 저장하고, second에는 입력받은 값을 저장하였다. 코드에 대한 설명은 주석 처리를 해놓았다. 간단하게 설명하자면, 우선순위 큐는 기본적으로 내림차순으로 정렬이 된다. 즉, 5, -3, -1, 3, -5 라는 ..

문제 www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이 www.acmicpc.net 풀이 이 문제는 11279문제랑 거의 똑같다. 다만, 이 문제는 값이 오름차순으로 저장되어야 한다. 그래서 priority_queue q; 를 선언해서 문제를 풀었다. 코드 #include #include using namespace std; int main(){ priority_queue q; int n; scanf("%d", &n); for(int i=0;i

문제 www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이 www.acmicpc.net 풀이 우선순위 큐를 이용해서 푸는 문제였다. 우선순위 큐는 데이터를 저장할 때마다 정렬을 해주는 큐이다. 우선순위 큐의 시간 복잡도는 O(logn)이고, sort 함수는 O(nlogn)이다. 그래서, 이 문제의 경우 우선순위 큐를 이용하면 더 빠르게 풀 수 있었다. 코드의 구조는 정말 직관적이라서 이해하기 쉬울 것 같다. 입력받은 데이터가 0인 경우, 저장된 데이터를 출력하고 입력받은 데..

문제 programmers.co.kr/learn/courses/30/lessons/12981 코딩테스트 연습 - 영어 끝말잇기 3 [tank, kick, know, wheel, land, dream, mother, robot, tank] [3,3] 5 [hello, observe, effect, take, either, recognize, encourage, ensure, establish, hang, gather, refer, reference, estimate, executive] [0,0] programmers.co.kr 풀이 words를 쭉 돌면서 끝말잇기가 틀렸는지 확인한다. 하지만 끝말잇기가 맞을 때도 앞에 나온 단어와 중복이 없는지도 확인해야 한다. 만약 for문을 다 돌면서 이상한 점을 발..