알고리즘/문제풀이 - 백준

백준 11053 가장 긴 증가하는 부분 수열

문제 : https://www.acmicpc.net/problem/11053 혼자 풀어내지 못한 문제. 이중 for문을 쓰는것 외에는 푸는 방법이 떠오르지 않았는데, 시간복잡도에 중점을 두는 DP문제라서 이중 for문이 쓰이진 않을것 같았고, LIS문제라고 하니 처음 들어보지만 정형화된 알고리즘이 있을것 같아서 오래 고민 안하고 다른 풀이를 봤다. 풀이 LIS문제. 현재수가 이전의 수보다 크면 이전의 수의 길이값을 +1 해준다. 현재수보다 작은 이전의 수가 여러개라면 이전의 수의 길이값들 중 가장 큰것을 선택하고 +1해준다. seq[0] = 0, seq는 입력받은 수, dp는 현재까지 수열의 최대 길이 1 2 3 4 5 6 seq 10 20 10 30 20 50 dp 1 0 0 0 0 0 seq[1] 1..

2019. 7. 8. 17:44
알고리즘/문제풀이 - 백준

백준 1904 01타일

문제 : https://www.acmicpc.net/problem/1904 풀이 n=1 1 n=2 00 11 n=3 100 111 001 n=4 0000 0011 1100 1111 1001 n=5 00100 00111 00001 10000 10011 11100 11111 11001 개수 : 1 개수 : 2 개수 : 3 개수 : 5 개수 : 8 n이 3일때는 n이 1일때의 1에 00을 앞에 붙인 001, n이 2일때의 00, 11에 앞에 1을 붙인 100, 111 총 3개가 올 수 있다. 앞에 01, 10, 0은 못붙인다. 이를 확장하면 n = n-1 + n-2의 점화식이 나온다. dp의 bottom-up으로 구현한다. 구현 %15746을 해주지 않으면 약 n이 90에서 long long 자료형을 초과한다..

2019. 7. 8. 14:04
알고리즘/문제풀이 - 백준

백준 10814 나이순 정렬

문제 : https://www.acmicpc.net/problem/10814 서론 벡터에 문자열 입력하는데 다수의 시행착오를 겪었다. char 자료형으로는 포인터로 문자열의 주소를 넣는 방법 말고는 모두 실패했다. 포인터로 넣으려면 라인을 입력받을때마다 새로운 변수명으로 동적할당을 해야하는데, 가능한지도 모르겠고 그냥 쉽게 string 자료형을 썼다. 또한 scanf로 string을 받아올 수 있는것 같긴 한데 정상적인 방법은 아닌것 같다. 아이디어 정렬 방법 : https://hydroponicglass.tistory.com/33 가입한 순서는 입력받은 순서를 저장하면 된다. 구현 그냥 cin, cout을 쓰면 시간초과가 뜬다. ios_base::sync_with_stdio(0); cin.tie(0);..

2019. 7. 7. 20:52
알고리즘/문제풀이 - 백준

백준 11650 좌표 정렬하기

문제 : https://www.acmicpc.net/problem/11650 풀이 vector를 정렬하는 방법이 필요하다. https://hydroponicglass.tistory.com/33 [STL] c++ sort 활용 sort 활용시마다 추가될 문서 vector 1차, 2차 정렬하기 정렬 전 3 4 1 1 1 -1 2 2 3 3 정렬 후 1 -1 1 1 2 2 3 3 3 4 벡터 정의 #include #include vector.. n; for (int i = 0; i < n; i++) { int a, b; scanf("%d %d", &a, &b); v.push_back({ a,b }); } sort(v.begin(), v.end(), compare); for (int i = 0; i < n; i..

2019. 7. 7. 17:56
알고리즘/문제풀이 - 백준

백준 1436 영화감독 숌

문제 : https://www.acmicpc.net/problem/1436 서론 아이디어는 간단했지만, 구현 실수로 반례찾는데 시간 다 보낸 문제. 반례는 66066이 출력되는 문제가 발생. 원인은 6이 연속으로 3개 이상 포함되는지 확인하기 위한 코드에서 문제가 있었다. 아이디어 브루트포스 문제. 1부터 아주 큰 수까지 6이 연속으로 3번 들어가는지 확인하는 코드에 전부 집어넣는다. 6이 연속으로 3번 이상 들어가는지 확인하는 코드는 - 들어온 숫자의 자릿수를 분해 각 자리가 6이고 이전 자릿수도 6이면 카운트 증가 카운트가 2 이상이면 6이 3개이상이므로 true - 구현 34번째 줄 2666799는 n이 10000일때의 수 //c++ #include #include #include using nam..

2019. 7. 6. 23:45
알고리즘/문제풀이 - 백준

백준 1018 체스판 다시 칠하기

문제 : https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 서론 풀이 결과에 반례가 발생. 접근방식에 문제가 있었다. 좌측 상단 글자를 기준으로 다른 글자들이 바르게 위치해있는지 검사했는데, BBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW 이런 예제에서 {0,0}의 B가 맞다고 가정하고 검사를 하기 때문에, {0,0}을 제외한 모든 글자를 수정하여 답이 63이..

2019. 7. 6. 20:06