baekjoon18 [정렬] 백준 2108 통계학 C++ https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 풀이 : 예전에 풀었던 문제인데 재채점 되면서 틀렸다고 나와서 다시 풀어 봄 사실 틀렸다고 나온 이유는 산술 평균 구할 때 -0.xxxx 이런수를 반올림 할 때 -0으로 출력하는 문제 때문에 틀렸던 거였다. 근데 다시 보니 코드가 너무 지저분해서 첨부터 다시 풀었다. 사실 평균값, 중앙값, 범위 값 구하는 것 자체는 그리 어렵지 않다. 입력 받은 수 들을 vector에 push_back 해서 sort 함수로 정.. 2022. 4. 9. [DP] 백준 9251 LCS C++ https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 : LCS의 개념에 대해선 다음 글로 확인할 수 있습니다. https://hoime.tistory.com/59?category=500438 최장 공통 부분 수열(LCS) 최장 공통 부분 수열은 Longest Common Subsequence의 약자로 줄여서 LCS라고 한다. 우선 Subsequence와 Substring의 차이에 대해 알아야 한다... 2022. 2. 15. [DFS]백준 2644 촌수계산 C++ https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 풀이 : 기본적인 dfs 문제 입니다. 사람의 번호가 1,2,3,..n명 중 서로 다른 두 사람 x, y가 주어졌을 때 두사람의 촌수를 구하는 문제 입니다. 두 사람 씩 부모-자식 관계가 주어지므로 graph 형식으로 데이터를 표현한 다음에 촌수를 구해야하는 두사람을 시작점 - 끝점으로 깊이 탐색으로 깊이 검색을 해주면 된다! 그래프 내부에서 관계가 없을 때는 -1을 출력해야하.. 2022. 2. 6. [DP] 백준 1699 제곱수의 합 C++ https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 풀이 : 간단한 문제자체는 간단한데 나만 어려웠나..? 생각보다 잘 안풀렸다. 솔루션 자체는 간단한데 생각보다 제곱수 빼고 하는 걸 구현하는데 삽질을 좀 했다. 해결하는 아이디어 자체는 조금 생각해보면 금방 떠올릴 수 있는 정도 내가 어려웠던 점은 반복문 한번으로 구할 수 있을 것 같아서 고민하다가 결국 솔루션을 봤는데 이중 반복문으로 j * j > N; f.. 2022. 1. 26. [DP] 백준 2294 동전2 C++ https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 풀이 : n 가지 동전으로 합이 k원이 되는 동전의 최소갯수를 구하는 문제 비슷한 문제로는 유명한 배낭문제랑 비슷하다. coins배열 : n개의 동전 종류 1원부터 시작하기위해 0번인덱스는 0으로두고 1부터 n까지 동전 설정 dp 배열 : dp[n] = 가치가 n원일 때 동전의 최소 갯수 예를 들어 설명하면 동전이 n원일때(coin[] 에서 가져오면 됨) 가치가 k면.. 2022. 1. 25. [문자열] 백준 5430 AC C++ https://www.acmicpc.net/problem/5430 [5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net](https://www.acmicpc.net/problem/5430) 풀이 : 문제만 읽었을 때 쉬워보여서 금방 풀었는데 에러가 나서 고친부분이 많음 조금 디테일하게 생각해야할 부분이 조금 있다. 문제의 핵심을 크게 나누어 보면 [1,2,3,4] 이런 식으로 입력되는 배열을 다루기 쉽게 파싱하는 부분 R -> 해당 배열을 뒤집는 부분 D -> 첫번째 원소를 삭제하는 부분 이렇게 3가지 정도로 나눌 수 있는데 가장 큰 핵심은 2번 뒤집는 부분이였다. 각.. 2022. 1. 24. 이전 1 2 3 다음
