[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. [BOJ #1252] 이진수 덧셈 BOJ #1252, 이진수 덧셈 문제입니다. 정답률은 28.3%로 상당히 낮습니다. 저 또한 문제의 세부 조건을 발견하지 못해 잠깐 헤맸습니다. 우선 이 문제는 크게 두 가지 방법이 있습니다. 첫 번째로 입력받은 이진수를 십진수로 변환하여 더하고, 다시 이진수로 변환하여 출력하는 방법이 있습니다. 두 번째로는 변환 없이 이진수 덧셈 자체를 구현하는 것이 되겠습니다. 첫 번째 방법은 어떻게 보면 더 효율적이고 더 빠른 방법일 수는 있겠으나, 문제의 의도는 아닐 것이라고 생각됩니다. 그리고 두 번째 방법으로 만들어보는 것이 실력적으로 더 큰 도움이 될 것입니다. 알고리즘은 동일하나, 이번 문제의 특성 상 C보단 Python으로 푸는 게 편리합니다. 저는 연습을 위해 일부러 C로 풀었지만 여기선 Python을.. 2020. 7. 14. 이전 1 2 3 다음