본문 바로가기

전체 글

(13)
혼공머신 1주차
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에 비례하기만 ..