반응형 분류 전체보기163 한 붓 그리기 가능한 경우 정보 올림피아드 필기에 한 붓 그리기 문제는 매년 출제되는 단골 문제 입니다. 따라서 한 붓 그리기가 언제 가능한지 꼭 기억하고 있어야 합니다. 한 붓 그리기는 오일러 경로(Euler trail)라고도 합니다. 한 붓 그리기는 이미 1736년에 오일러가 증명 했습니다. 한 붓 그리기가 가능한 도형에 대해 알아보겠습니다. 꼭지점의 차수가 모두 짝수 일때 차수란 꼭지점에 인접한 선분이 몇 개인지를 나타냅니다. 위 그림처럼 모든 쪽지점의 차수가 짝수일 때 어느 지점으로 시작해도 다시 출발점으로 돌아오는 한 붓 그리기가 가능합니다. 차수가 모두 짝수인 경우 어느 지점에서 시작해도 한 붓 그리기가 가능하고 출발점으로 돌아옵니다. 꼭지점의 홀수 차수가 2개 일 때 먼저 꼭지점의 홀수 차수가 1개인 경우는 없습니다... 2024. 3. 15. 2019년 정보올림피아드 필기 초등부(6~10) 2019년 정보올림피아드 필기 초등부 6번부터 10번까지 문제 풀이 입니다. 1번부터 5번까지는 아래 링크 확인 바랍니다. 2024.03.12 - [알고리즘 설명] - 2019년 정보올림피아드 필기 초등부(1~5) 2019년 정보올림피아드 필기 초등부(1~5) 2019년 정보 올림피아드 1차 필기 초등부 문제 풀이 입니다. 1번 (a, b), (b, c), (c, a) 총 3번 비교하면 됩니다. 조합을 구하는 문제로 초등부 문제에서는 3개중 2개를 비교하지만 중등부, 고등부에서는 davincicoding.co.kr 6번 이 문제는 시뮬레이션을 직접하여 첫 번째 개미가 떨어진 시간과 마지막 개미가 떨어진 시간의 차이를 구해야 합니다. 먼저 첫 번째 개미가 떨어질 때까지 시뮬레이션 해보겠습니다. 먼저 시작 .. 2024. 3. 14. [백준 30090] 백신 개발 문제 출처 : https://www.acmicpc.net/problem/30090 30090번: 백신 개발 평소 정보 보안에 관심이 많은 진흥이는 최근 들어 유행하고 있는 컴퓨터 바이러스에 대한 백신을 개발하려고 한다. 바이러스는 $N$개의 문자열로 이루어져 있다고 한다. 진흥이가 열심히 연구 www.acmicpc.net 이 문제는 제 1회 청소년 IT 경시대회 초등부 B번, 고등부 A번 문제 입니다. 겹치는 문자열을 이어 붙여 가장 짧은 문자열을 만드는 문제 입니다. 예제를 확인해보면 3개의 입력이 주어집니다. RUST, VIRUS, STAND 입니다. 이 3개의 문자를 겹치는 부분을 하나로 만들어 잘 이어주면 VIRUSTAND 라는 문자열이 가장 짧은 문자열이 되고 이 문자열의 길이인 9를 출력하는 .. 2024. 3. 13. [백준 30089] 새로운 문자열 만들기 문제 출처 : https://www.acmicpc.net/problem/30089 30089번: 새로운 문자열 만들기 $T$개의 줄마다 영어 대문자로만 이루어진 문자열 $S$가 주어질 때, 각 줄마다 아래 조건을 모두 만족하는 문자열 $X$를 출력하여라. $X$는 $S$로 시작하여야 한다. $X$를 뒤에서부터 읽은 문자열 $X'$ www.acmicpc.net 이 문제는 제 1회 청소년 IT 경시대회 초등부 A번, 중등부 A번으로 출제되었습니다. 문자열 S가 주어졌을 때 뒤집어도 문자열 S가 나오는 가장 짧은 문자열 X를 출력하는 문제 입니다. 테스트 케이스가 100개 이하이고, 문자열 길이가 20 이하이기 때문에 시간 복잡도에 구애받지 않고 어렵게 생각하지 않고 풀어도 됩니다. 문제 이해하기 이렇게 앞으.. 2024. 3. 12. 2019년 정보올림피아드 필기 초등부(1~5) 2019년 정보 올림피아드 1차 필기 초등부 문제 풀이 입니다. 1번 (a, b), (b, c), (c, a) 총 3번 비교하면 됩니다. 조합을 구하는 문제로 초등부 문제에서는 3개중 2개를 비교하지만 중등부, 고등부에서는 계산을 직접 해야 합니다. $$ nC_r = _3C_2 = \frac{3 * 2}{2} = 3 $$ 2번 5명의 친구들을 2명씩 묶는 문제 입니다. 즉 조합을 이용하여 2명씩 묶는 것은 쉽게 구할 수 있습니다. 5 * 4 / 2 = 10이 됩니다. 10개의 조합이 나오니까 한쌍씩 악수를 한다면 10분이 걸립니다. 여기서는 5명이기 때문에 한 번에 두 쌍이 악수를 하고 한 명이 남습니다. 즉 2쌍씩 악수할 수 있으므로 총 5분이 걸립니다. 3번 5개의 원을 흰색 또는 회색으로 칠해야 합.. 2024. 3. 12. 파이썬 음수의 나머지 연산 나머지 연산은 프로그래밍에서 정말 많이 사용하는 연산자 입니다. 나머지 연산자(%)에 대해서 아직 잘 모른다면 아래 링크를 통해 확인 바랍니다. https://wikidocs.net/214915 08. 나머지 연산 [TOC] 실생활에서는 잘 사용하지 않지만 프로그래밍에서 많이 사용하는 연산중 하나가 나머지 연산 입니다. 나머지 연산은 모듈로(Modulo) 연산 이라고도 합니다. 나머지 연… wikidocs.net 음수를 양수로 나머지 연산하기 나머지 연산자를 활용하지만 아마도 음수의 나머지 연산은 어떻게 동작하는지 생각해 보지 않았을 것입니다. -21이라는 숫자를 5로 나눈 나머지를 구한다고 하겠습니다. 답이 무엇일지 생각해 보시기 바랍니다. a = -21 b = 5 print(a % b) a라는 숫자를.. 2024. 3. 11. [백준 17619]2019 정올 2차 중등부 "개구리 점프" 문제 출처 : https://www.acmicpc.net/problem/17619 17619번: 개구리 점프 첫 번째 줄에 통나무 개수 N과 질문의 개수 Q가 주어진다. 다음 N개의 줄에 각 통나무에 x1, x2, y의 세 정수 좌표가 주어진다. 주어진 통나무는 두 점 (x1, y)와 (x2, y)를 잇는 형태이다. (x1 < x2) 모든 www.acmicpc.net 이 문제는 2019년 정보올림피아드 2차 대회 중등부 2번 문제 입니다. 문제 이해하기 이 문제는 점프를 얼마나 해서 이동할 수 있는지 묻는 문제가 아닙니다. 오직 이동이 가능한지, 불가능한지 묻는 문제 입니다. 즉 높이는 아무 상관 없이 길이가 겹쳐지는지를 따져서 연결 여부만 알 수 있으면 됩니다. 문제에서는 이렇게 길이와 높이가 나와 있.. 2024. 3. 7. [백준 17615] 2019 정올 2차 초등부 "볼 모으기" 문제 출처 : https://www.acmicpc.net/problem/17615 17615번: 볼 모으기 첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주 www.acmicpc.net 이 문제는 2019년 정보 올림피아드 2차 대회 초등부 2번 문제 입니다. 알고리즘 이해하기 문제에는 제약 조건이 많기 때문에 잘 읽어봐야 합니다. 한가지 색깔만 옮길 수 있습니다. 처음에 빨간색을 옮기면 계속 빨간색만 옮겨야 합니다. 하나씩 옮기되, 최대한 멀리 옮겨야 최소 값을 얻을 수 있습니다. 이 두가지를 생각하면서 시뮬레이션 해보면 결국 우리가 .. 2024. 3. 6. [백준 17618] 2019 정올 2차 중등부 "신기한 수" 문제 출처 : https://www.acmicpc.net/problem/17618 17618번: 신기한 수 평소에 수에 대한 관심이 많은 아이인 민철이는 오늘도 노트에 연필로 수를 더하거나 빼거나 곱하거나 나눠보면서 시간을 보내고 있다. 그러다가 18이라는 수는 신기한 성질을 가진다는 것을 알 www.acmicpc.net 이 문제는 2019년 정보올림피아드 2차 대회 중등부 1번 문제 입니다. 문제 난이도가 높지 않아 다빈치코딩 알고리즘에도 똑같이 작성해 놓았습니다. https://wikidocs.net/232738 02. 신기한 수(정올 2019)[백준 17618] 문제 출처 : [신기한 수](https://www.acmicpc.net/problem/17618) 이 문제는 2019년 정보올림피아드 2차.. 2024. 3. 5. 이전 1 ··· 4 5 6 7 8 9 10 ··· 19 다음 반응형
