[BOJ #1449] 수리공 항승 BOJ #1449, 수리공 항승 문제입니다. 간단하게 그리디 알고리즘을 이용하는 문제입니다. 테이프의 길이와, 파이프에서 물이 새는 위치가 주어지면 물이 새는 모든 위치를 막으려면 최소 몇 개의 테이프를 이용해야 하는지를 출력하는 문제입니다. 단, 테이프는 자를 수 없으며 무한 개 가진 것으로 간주합니다. 추가적으로 물이 새는 지점의 좌우로 0.5cm까지 테이핑해야 물을 막은 것으로 간주합니다. 따라서 가령 1과 3에서 물이 새고 있고 이것을 하나의 테이프로 막고자 하면 1의 왼쪽 0.5, 사이 거리 3 - 1 == 2, 3의 오른쪽 0.5로 길이 3 이상의 테이프가 필요한 것이죠. 즉 길이 n의 테이프로는 최대 간격이 n - 1인 구멍까지만 막을 수 있습니다. 그리고 이 문제 한참 헤맸던 것이... t.. 2020. 7. 29. [BOJ #10816] 숫자 카드 2 BOJ #10816, 숫자 카드 문제입니다. 기본적으로 이진 탐색을 이용하는 문제이고 다른 기초적인 이진 탐색 문제와 다르게 이진 탐색을 여러 번 해야 하는 문제입니다. 그래서인지 시간 초과로 틀리는 케이스가 많으며 정답률도 낮은 편입니다. 1. 숫자가 있는지 판단하기 기본적인 이진 탐색 알고리즘을 이용하면 되므로 쉽게 짤 수 있습니다. int M; scanf("%d", &M); int *toFind = (int *)malloc(sizeof(int) * M); for (int i = 0; i < M; i++) { scanf("%d", &toFind[i]); idx = findIdx(card, N, toFind[i]); if (idx == -1) printf("0 "); else printf("%d ", .. 2020. 7. 27. [BOJ #13417] 카드 문자열 BOJ #13417, 카드 문자열 문제입니다. 처음에 C로 짜다가 입력 버퍼 관련 문제가 발생해서 한참 헤맸습니다만 Python으로 짜니까 바로 해결했습니다. 입력 버퍼 비우는 테크닉을 알고 있었는데 왜인지 잘 기억이 안 났었네요. 그리고 아직도 왜 안 되는지 모르겠습니다. 구글링도 열심히 하면서 해결하려고 해 보았으나 나중에 다시 시도해보기로 했습니다. 이 문제의 예제에서는 너무나 쉬운 testcase만을 제시하기 때문에, 혼자서 여러 가지 testcase를 만들어서 시험해봐야 합니다. 그리고 bit mask를 이용한 brute force도 문제의 입력 조건 상 시간이 부족하기 때문에 불가능하며 따라서 연역적인 과정을 통해 답을 도출할 수 있어야 합니다. (brute force의 범위를 좁히는 것이 권.. 2020. 7. 25. [BOJ #11659] 구간 합 구하기 4 BOJ #11659, 구간 합 구하기 4 문제입니다. 원소 수 N개의 정수 배열이 주어졌을 때 입력된 구간의 합을 출력하면 됩니다. 프로그램 자체가 간단하지만, 일반적인 방법으로는 시간복잡도가 너무 높아 시간 내에 풀 수 없습니다. 이를 해결하기 위해서는 '누적합'을 이용하면 됩니다. 수학에서 수열을 다룰 때 급수를 이용해 a_n = s_n - s_(n - 1)과 같이 나타내는 것과 동일한 원리를 이용합니다. 이것을 알면 코드 구현은 어렵지 않게 할 수 있겠습니다! 추가적으로 더 효율적인 방식도 있고 다양한 방식이 있으니 검색을 통해 찾아보시거나 직접 떠올려 보시면 큰 도움이 될 것이라고 생각합니다. 간단한 코드이나 제 코드를 첨부하도록 하겠습니다. 더보기 #include #include int main.. 2020. 7. 19. [BOJ #11728] 배열 합치기 BOJ #11728, 배열 합치기 문제입니다. 문제의 내용 자체는 간단합니다만 입력 데이터의 크기가 크고 시간 제한이 체감되는 문제입니다. 입력으로 정렬된 두 개의 배열이 주어지면 출력으로는 두 배열을 합쳐서 정렬한 배열을 출력하면 됩니다. 여러 개의 인덱스 변수를 동시에 다루는 방법으로 해결했습니다. 코드는 다음과 같습니다. 더보기 #include #include int main(void) { int N, M; scanf("%d %d", &N, &M); int *A = (int *)malloc(sizeof(int) * N); int *B = (int *)malloc(sizeof(int) * M); for (int i = 0; i < N; i++) scanf("%d", &A[i]); for (int i .. 2020. 7. 18. [BOJ #2231] 분해합 BOJ #2231, 분해합 문제입니다. 크게 어렵진 않은 문제이나, 새로운 접근 방법을 찾아내 공유할 겸 작성하게 되었습니다. 문제의 정의를 살펴 봅시다. a + a의 각 자릿수의 합 == b이면 a는 b의 생성자입니다. 처음에 이 관계가 잘 와닿지 않는데, a를 조작해서 b를 생성하므로 a가 b의 생성자라고 이해했습니다. 이런 사실들로부터 생각을 이끌어 보면, a에서 b를 구하는 것은 정말 쉽다는 것을 알 수 있습니다. 문제가 아무런 의미가 없게 되겠죠. 그렇지만 이 문제는 b에서 a를 구해야 하기 때문에 살짝 복잡해집니다. 왜냐하면 a == b이면서 동시에 a' == b일 수 있기 때문입니다. 이런 상황에서 가장 만만하게 써볼 수 있는 녀석이 완전탐색(Brute-Force)입니다. 멋있는 영어 이름도.. 2020. 7. 15. 이전 1 2 3 4 다음