본문 바로가기

알고리즘

 (6)
2812 크게 만들기 백준 2812 크게 만들기 문제이다. https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 그리디 알고리즘으로 풀 수 있는 문제이다. 나는 생각해보다가 전혀 감이 안 잡혀서 풀이도 많이 참고하였다. 내가 생각한 풀이 ) 앞에서부터 읽으면서 가장 작은 숫자를 k번만큼 반복하면서 지운다. -> 백준 예제 3이 반례이다. 앞에서부터 지우면 1,2,2,1을 지우게 되서 477584가 나오고, 이는 775841보다 작다. 여기서 부터 아무 생각이 안 났다... 마음을 다 잡고 더 생각해봤어야 했는데 무작정 여기서부터 풀이를 참고하였다...
11053 가장 긴 증가하는 부분 수열 dp 문제가 어려워서 계속 공부하고 있는데, 내 발목을 잡았던 문제다. 풀이를 읽어도 뭔가 사악 자연스럽게 안 들어와서 며칠 동안 보고 있었는데 이제야 좀 들어오는 것 같아서 안 까먹기 위해 블로그를 쓴다. 이 문제는 LIS 알고리즘으로 검색하면 여러 가지 방법이 나오지만, 난 현재 dp방법만 알고 있으므로 이것만 소개하겠다. 이후 된다면 계속 추가하도록 한다. 문제 사이트는 다음과 같다. 말 그대로 수열에서 가장 긴 증가하는 부분 수열의 길이를 찾으면 된다. https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 3..
11726 2xn 타일링 www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net dp 문제이다. 1x2 와 2x1 직사각형을 2xn에 타일링하는 경우를 세면 된다. 처음에 굉장히 막막했다. 이런 dp문제들을 사람들은 어떻게 푸는 건지 싶고.. 답지를 볼까 말까 고민을 많이 했지만 막상 답을 알고 풀고 나니까 dp 중에서는 나름 할만한 문제였다는 생각이 든다. 가장 처음 떠올린 생각은 1) 1/n-1, 2/n-2, 3/n-3 ... n-1/1 로 타일을 쪼개서 더한다. 이 생각이었다. 이렇게 코드를 짜게 되면 f..
char string 인풋받는거 string : #include 해줘야함 char은 항상 크기를 지정해 주어야함. cin.getline(배열이름, 최대길이(숫자), '\n') - 띄어쓰기 무시할수있음 cin.getline은 for문안에서 안먹음 cin.getline은 약간 이상한거같다,, 앞에 cin 많이 쓰면 getline에서 앞 cin이랑 중복으로 같이 막 받는 거 같다,, 예를 들어 cin>>a>>b; cin.getline(s, 1000, '\n\); 이렇게 하면 막 b에 친게 s에도 또 들어가는 것 같다, , cin>>a>>b 랑 scanf("%d%d", &a, &b); 랑 똑같다
17608 막대기 이 문제를 처음 봤을 때에는 단순히 최댓값 구하는 문제인 줄 알고 후다닥 적었다가 당연히 틀렸다. 그럴 리가 없었는데... 아무튼 내가 생각한 풀이와 스택을 이용해서 푸는 거 두개를 적을려고 한다. 1. 내가 생각한 풀이 0~n-1까지 입력을 받으면서 가장 긴 막대기의 위치를 구한다. 가장 긴 막대기와 마지막 막대 사이에 있는 막대기(i번째 막대기라고 하자)를 하나하나 보면서 i번째 막대기가 가장 긴 막대기보다는 작고 마지막 막대보다는 크면 조건을 만족하는 막대기라고 생각했다. (count++해주었다) 여기서 고려했던 점은 가장 긴 막대기와 마지막 막대의 길이가 같을 때(가장 긴 막대가 마지막 막대가 되어도 상관없다)에는 count를 1만 더해주고, (사실 이 경우에는 조건을 만족하는 막대기가 그냥 1개..
시간복잡도 공간복잡도 *시간복잡도 공간복잡도를 다 까먹어서 간략하게 정리하기 위한 글이다. 기억 환기를 위한 글이므로 꼼꼼한 개념 설명보다는 문제에 맞닥뜨렸을 때 기억해내고 사용해내는데 목적이 맞추어져 있음 . . . . 시간복잡도 : 알고리즘에서 연산이 몇번이나 진행되는가 공간복잡도 : 알고리즘에서 필요한 메모리가 얼마나 되는가 - 그리고 프로그래밍 문제를 보면 O(n), O(n^2) 등등 뭐 이렇게 짜라는 문제를 가끔 맞닥뜨린다. 이 표기법이 바로 빅오 표기법이다. 1. 시간복잡도 - 시간복잡도는 보통 n을 통해 나타낸다. n을 통해 나타나지 않는 건 O(1) 처럼 어떤 값을 넣든 걸리는 시간이 똑같은 프로그램이라고 생각하면 된다. 정확하지는 않지만 반복문이 몇번 돌아가게 되는가를 생각하면 편할 듯. - n에 비례하기만 ..

티스토리툴바