본문 바로가기

전체 글145

행렬 #1080 c++ 풀이 https://www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 내가좋아하는 행렬 문제 근데, 왜 Greedy알고리즘인지 모르고 풀었다. 검사해서 3개씩 바꿀건데 바꾸기전과 바꾼후가 다르면 결국 변환시킬수 없는 것이다. 따라서, 우선 변환시키고 다르면, 변환했을때를 비교해서 검사했다. #include using namespace std; int arr[51][51]; int answer[51][51]; int N, M; int cnt; void change(int y, in.. 2023. 11. 22.
신입사원 #1946 c++ 풀이 https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net dp를 어느정도 감을잡고 greedy를 푸는 중이다. 1 4 2 3 3 2 4 1 5 5 로 sort후, 뽑힌 사람들을 확인하니 두번째 요소에 대해 내림차순인 것들만 count 해주면 된다. 솔직히 이게 왜 greedy인지 모르겠다. #include #include #include #include using namespace std; int main() { int T; cin.. 2023. 11. 22.
잃어버린 괄호 #1541 c++ 문제풀이 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 처음에는 문제조건을 잘못보고, 한번만 괄호를 쳐야하는줄알고 애를 먹었는데 곰곰히 생각해보니 그럴필요가 있나하고 맞춘 문제이다. 결국 가장 작은 수를 만들려면 - 에서 -가 나올때까지 괄호를 씌워서 음수로 만들어주면 된다. ex) + - + - + + => + - - - - - 2023. 11. 22.
DP 다이나믹 프로그래밍 Dynamic Programming Dynamic Programming이란? 큰 문제를 작은문제로 나누어 푸는 문제를 일컫는 말. Dynamic Programming이란 말 때문에 어떤 부분에서 동적으로 프로그래밍이 이루어지는 찾아볼 필요는 없다. 바로 동적프로그래밍이란 말을 창조한 사람도 이것이 단지 멋있어서 부여한 이름이라고 한다. 메모이제이션 기법을 사용한다. 그것이 핵심이다. Dynamic Programming 방법 모든 작은 문제들은 한번만 풀어야 한다. 따라서 정답을 구한 작은 문제를 어딘가에 저장해 두어야 한다. 다시 그보다 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 앞서 저장한 작은 문제의 결과값을 이용한다. Dynamic Programming의 조건 작은 문제가 반복이 일어나는 경우. 같은 문제는 구할 때마다 정답.. 2023. 11. 22.

티스토리툴바