[C] 백준 | 1010번 코드 - 다리 놓기
>문제 www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 핵심 조합 (nCr) >풀이과정 DP 문제라길래 풀어봤는데 막상 풀고나니까 DP보다는 조합 문제인 것 같다. 처음에는 DP처럼 풀려고 팩토리얼을 dp 배열에 저장해놓고 nCr 계산할 때 꺼내쓰려고 했었는데, 문제의 조건에 따르면 최대 30! 까지 구해야 할 수 있는데 이 30!은 unsigned long long 자료형을 사용해도 다 담을 수가 없는 범위이기 때문에 그렇게 할 수가 없다..! 그래서 ..
[C] 백준 | 13301번 코드 - 타일 장식물
>문제 www.acmicpc.net/problem/13301 13301번: 타일 장식물 대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개 www.acmicpc.net > 핵심 피보나치 수열 DP long long형 >풀이과정 피보나치 수열을 이용해서 풀 수 있다. n = 5일때 길이는 (5 * 2) + ((3+5) * 2) 다시말해 dp[n] = (dp[n] * 2) + ((dp[n-1] + dp[n]) * 2) (배열 인덱스가 0부터 시작하므로 아래 코드에는 n-1, n-2로 이용함.) 근데 이게 초등부 문제라는데 경악을 금치못했다 요즘 초등학생들은 천재들밖에 없나...
[C] 백준 | 12037번 코드 - Polynesiaglot
>문제 www.acmicpc.net/problem/12037 12037번: Polynesiaglot (Small1) In Case #1, suppose that the only vowel is a and the only consonant is h. Then the possible valid words of length 4 are: aaaa, aaha, ahaa, haaa, haha. In Case #2 (which would not appear in the Small dataset 1), suppose that the two vowels are a a www.acmicpc.net > 핵심 DP 자음 앞에는 모음만 올 수 있다 >풀이과정 와 어렵다 다이나믹 프로그래밍 기법을 사용하지만 내 머리는 다이나믹하..
[C] 백준 | 9625번 코드 - BABBA
>문제 www.acmicpc.net/problem/9625 9625번: BABBA 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했 www.acmicpc.net > 핵심 피보나치 수열 DP >풀이과정 DP 문제라길래 DP스럽게 풀어보려고 했다. 맞게 푸는건지 모르겠네 메모이제이션을 하기 위한 배열을 int형이 아니라 구조체 배열로 만들어서 A와 B의 개수를 따로따로 세기 편하도록 했다. 꼭 구조체가 아니더라도 A, B 두가지 경우밖에 없기 때문에 이차원배열을 통해서 구분해도 될 것 같다. 크게 어렵지는 않았다! >깨달은점 모르겠다 BABA! >코드 #define _..
[C] 백준 | 11723번 코드 - 집합
>문제 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net > 핵심 배열 >풀이과정 쉽다. 처음엔 연결리스트로 할까 생각하다가 시간이 오래걸릴 것 같아서 그냥 배열로 때려박았다. >깨달은점 쉽다. >코드 #define _CRT_SECURE_NO_WARNINGS #include #include int main() { int i, m, e; char op[10]; int numset[21] = { 0 }; scanf("%d", &m); for (i = 0; i < m; i++) { scanf(" %s", op); if (strcmp(op, "add") ..
[C] 백준 | 1929번 코드 - *소수 구하기
>문제 > 핵심 에라토스테네스의 체 >풀이과정 소수 구하기 문제. 이거 어디서 본 것 같은데?? 백준 1978번 문제 >> sedangdang.tistory.com/18?category=969000 [C] 백준 | 1978번 코드 - 소수찾기 >문제 > 핵심 반복문 돌기. 효율적인 알고리즘을 강구해보자. >풀이과정 [소수 : 1과 자기 자신만으로 나누어 떨어지는 1보다 큰 양의 정수. ] 소수 찾기 알고리즘 기본서에 꼭 나오는 내용으로 기 sedangdang.tistory.com 이미 풀어본 문제다! 다만 저 문제는 1000 이하의 소수를 찾는 것이고 이 문제는 백만까지의 소수를 구해야 하는 것이라는 큰 차이가 있다.. 그래서 이 문제는 넓은 범위에서 소수를 찾을때 유용하게 쓰이는 알고리즘인 를 이용했다..
[C] 백준 | 18111번 코드 - *마인크래프트
>문제 > 핵심 브루트포스 알고리즘 (모든 경우를 다 따져보는 방법) >풀이과정 아.. 어렵다 혼자 끙끙 생각하다가 도저히 생각이 안나서 다른사람이 쓴 아이디어를 보고나서야 풀었다.. 풀고나서야 그렇게 어려운 문제가 아니었다는걸 깨달았다.. 코딩은 나의 길이 아닌가 내가 생각한 방법 1. 블록의 높이를 입력받으면서 가장 높은 max, 가장 낮은 min 값을 찾는다. 2. max층부터 min층까지 층층이 탐색하면서, 2-1. 현재 높이에서 구멍이 몇칸 뚫려있는지 구하고 2-2. 인벤토리에 있는 블럭으로 그 구멍을 다 메꿀 수 있으면 메꾸고 break. 2-3. 메꿀 수 없으면 한층 더 파고 내려가기 3. 그렇게 돌면서 모든 블럭이 평평하게 맞춰진다면 break 후 총 걸린시간 출력.. 하는 구조를 생각했었..
[C] 백준 | 2805번 코드 - 나무 자르기
>문제 > 핵심 이분탐색 long long형 >풀이과정 이 문제,, 어딘가 낯이 익다 했더니 1654번 문제 "랜선 자르기" 랑 구조가 거의 똑같다!! 그래서 나무의 최대 길이가 2,000,000,000이라는 점에서 int형이 아니라 long long 형을 사용해야 한다는 점을 잊지 않고 사용해서 어렵지 않게 문제를 풀 수 있었다. 우선 나무의 길이를 입력받으면서 가장 긴 나무의 길이를 max에 저장한다. 그리고 이분탐색을 위해 left = 0, right = max (left 깨달은점 한번 풀어본 유형은 어떻게 풀어야겠다는 감이 빨리 온다는걸 이 문제로 느꼈다. 클래스 2는 이제 거의 다 풀어가는데 앞으로도 계속 다양한 유형의 문제를 접해봐야겠다. >코드 #define _CRT_SECURE_NO_WAR..