PS
프로그래머스 코딩테스트 연습 - K번째 수 (Level 1)
문제 프로그래머스 코딩테스트 연습 - K번째 수 (Level 1) https://programmers.co.kr/learn/courses/30/lessons/42748 코딩테스트 연습 - K번째수 [1, 5, 2, 6, 3, 7, 4] [[2, 5, 3], [4, 4, 1], [1, 7, 3]] [5, 6, 3] programmers.co.kr 사용 알고리즘 - 정렬 풀이 각 벡터(예제)마다 원본 array벡터를 카피한 temp벡터를 만들어 정렬시키고 k번째로 큰 수를 구함. 나의 코드 #include #include #include using namespace std; vector solution(vector array, vector commands) { vector answer; int i, j, k..
프로그래머스 코딩테스트 연습 - 수포자(Level 1)
문제 프로그래머스 코딩테스트 연습 - 수포자(Level 1) https://programmers.co.kr/learn/courses/30/lessons/42840 코딩테스트 연습 - 모의고사 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 programmers.co.kr 사용 알고리즘 - 완전탐색 풀이 각 수포자의 문제 찍는 방식이 일정한 주기로 반복되므로 나머지 연산을 이용해 answer마다 정답 여부를 확인. 직접 세보고 max값 찾아 출력. 코드 #include #include #include #include using namespace std; vector so..
백준 BOJ 2109 순회강연
문제 백준 BOJ 2109 순회강연 https://www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 사용 알고리즘 Data structures Greedy Sorting Priority queue 풀이 d(마감일) 기준으로 오름차순 정렬 후 차례대로 우선순위큐에 넣을지 말지를 판단. 우선순위큐의 size
백준 BOJ 2616 소형기관차
문제 백준 BOJ 2616 소형기관차 https://www.acmicpc.net/problem/2616 2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있 www.acmicpc.net 사용 알고리즘 Dynamic programming Prefix sum 풀이 누적합 + DP. 우선 소형 기관차가 최대로 끌 수 있는 객차의 수에 해당하는 길이의 구간마다 합을 구해 놓고 2차원 DP를 돌림. dp[i][j]=max(dp[i-1][j],dp[i-m][j-1]+b[i]); dp[i][j] = i번째 객차까지 j개의 소형기관차를 썼을 때 최댓값.
백준 BOJ 10800 컬러볼
문제 백준 BOJ 10800 컬러볼 https://www.acmicpc.net/problem/10800 10800번: 컬러볼 첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N www.acmicpc.net 사용 알고리즘 Implementation Sorting Prefix sum 풀이 {크기, 색깔, index} 를 원소로 하는 3진 pair를 만들어 크기를 기준으로 정렬. 누적 합을 구하면서 색깔별 누적 합도 따로 구해줌. 같은 색깔 + 같은 크기일 경우에도 따로 처리. 아이디어 구상은 쉬우나 예외 처리 부분이 신경 쓸 게 많았음.
백준 BOJ 11683
문제 백준 BOJ https://www.acmicpc.net/problem/11663 11663번: 선분 위의 점 첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 www.acmicpc.net 사용 알고리즘 Binary search 풀이 n^2이면 시간 초과가 나기 때문에 brute force는 안되고 이분 탐색을 써야 한다. 선분의 왼쪽 지점은 std:: lower_bound, 오른쪽은 std::upper_bound 사용하여 index를 각각 찾은 후 차이를 구해주면 된다. 점이 선분들 범위 밖을 아예 벗어났을 때 예외 처리를 따로 해주어야..
백준 BOJ 5582 공통 부분 문자열
문제 백준 BOJ https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 사용 알고리즘 Dynamic programming String 풀이 2차원 DP. dp[i][j] = 첫번재 문자열 i까지, 두번째 문자열 j까지 봤을 때 최대 길이 if(s1[i]==s2[j]){ dd[i+1][j+1]=dd[i][j]+1;
백준 BOJ 20003 거스름돈이 싫어요
문제 백준 BOJ 20003 https://www.acmicpc.net/problem/20003 20003번: 거스름돈이 싫어요 프로불편러 지수는 딱 떨어지지 않는 수는 질색이다. 거스름돈이 남는 것도 딱 질색이다. 지수가 아이템을 사려 하는데, 아이템의 가격은 다 분수로 이루어져 있다. 지금은 가령, 3/2코인을 사려 www.acmicpc.net 사용 알고리즘 Mathematics Number theory Euclidean algorithm 풀이 우선 입력받은 값들을 모두 기약분수로 바꾸고 모든 분모들의 LCM을 구해 분모를 먼저 찾는다. 분모들을 LCM으로 통일시켜주면서 분자를 적절한 값을 곱해 수정한다. 분자들의 GCD를 구하면 출력해야 할 답의 분자가 된다. 답의 분자가 항상 1이 나올 것이라고 ..