본문 바로가기

202011

[백준 20188] 등산 마니아 등산 마니아(20188)문제 출처 : https://www.acmicpc.net/problem/20188 이 문제는 2020년 정보올림피아드 2차 대회 초등부 3번, 중등부 2번 문제 입니다.문제 이해하기한 번만 읽어서는 잘 이해하기 힘든 문제 입니다. 특히나 다양성이라는 용어가 중요한데 이 말의 뜻이 어렵습니다.다양성은 길에 포함된 오솔길의 개수로 정의된다.이렇게 정의 되어 있습니다. 문제를 제대로 읽지 않으면 다양한 경로의 개수로 잘못 이해하기 쉽습니다. 문제를 잘 읽어보면 이 문제에서 원하는 다양성은 두 지점을 지나는 간선의 개수 입니다. 이 간선의 개수는 최단 경로를 뜻하는 것이 아니라 정상 즉 루트를 지나는 경로입니다.위와 같이 6, 7을 연결하는 다양성은 루트 부터 각 번호까지 간선의 개수 3.. 2024. 11. 22.

[백준 20186] 수 고르기 수 고르기(20186)문제 출처 : https://www.acmicpc.net/problem/20186 이 문제는 2020년 정보올림피아드 2차 대회 초등부 1번 문제 입니다.문제 이해하기문제를 읽어보면 상당히 복잡해 보입니다. 하지만 조금만 잘 생각해보면 규칙을 쉽게 찾을 수 있습니다.2 3 1 2 1, K = 3문제의 예제처럼 위와 같이 숫자가 있고 3개의 숫자를 선택해야 합니다. 그리고 점수는 자신의 왼쪽에 있는 선택된 수 입니다. 3개의 숫자를 어떻게 고를지 모르겠지만 K값이 3이기 때문에 숫자 3개를 골라야 합니다. 이 숫자들을 a, b, c라고 하겠습니다. a, b, c의 점수는 각각 a - 0, b - 1, c - 2 입니다. 이 숫자들의 합은 a + b + c - 0 - 1 - 2로 나타낼.. 2024. 11. 19.

[백준 20187] 종이접기 2020년 정보 올림피아드 2차 대회에서 초등부 2번, 중등부 1번 문제였던 종이접기, 백준 온라인 저지에서 20187번을 풀어 보도록 하겠습니다.문제 출처 : https://www.acmicpc.net/problem/20187문제 이해하기어릴적에 종이를 얼마나 접을 수 있을지 꼬깃꼬깃 접었던 기억이 있습니다. 그렇게 종이를 접고 접다보면 최종적으로 1 X 1 크기의 정사각형이 됩니다. 여기에 4등분 하여 하나의 위치에 구멍을 뚫고 접었던 반대로 풀기 시작하면서 구멍이 뚫린 위치를 출력해주면 됩니다.마지막 1 X 1 정사각형의 위치는 어떻게 잡으면 될까요? 규칙적으로 접고 접었다가 다시 펼치는 알고리즘을 생각해보면 분할 정복으로 문제를 해결할 수 있습니다. 전체크기를 하나하나 줄여 나가다보면 제일 마지막.. 2024. 10. 15.

2020년 정보올림피아드 필기 중등부(2-4 ~ 2-8) 2020년도 정보올림피아드 1차 대회 중등부 필기 2 - 4번부터 2 - 8번까지 문제 풀이 입니다. 이전 문제는 아래 링크 확인 바랍니다. 2024.04.09 - [알고리즘 설명/정보올림피아드 필기] - 2020년 정보올림피아드 필기 중등부(1 ~ 5) 2024.04.11 - [알고리즘 설명/정보올림피아드 필기] - 2020년 정보올림피아드 필기 중등부(6 ~ 10) 2024.04.12 - [알고리즘 설명/정보올림피아드 필기] - 2020년 정보올림피아드 필기 중등부(11 ~ 2 - 3) 2 - 4번 5의 배수로 물건을 저장하다가 6의 배수로 물건을 저장할 때 위치가 변하지 않는 물건의 개수를 묻는 문제 입니다. 문제에서 보면 알 수 있듯이 1부터 5번까지는 움직이지 않습니다. 6번부터 하나씩 앞으로.. 2024. 4. 14.

2020년 정보올림피아드 필기 중등부(11 ~ 2 - 3) 2020년도 정보올림피아드 1차 대회 중등부 필기 11번부터 2 - 3번까지 문제 풀이 입니다. 이전 문제는 아래 링크 확인 바랍니다. 2024.04.09 - [알고리즘 설명/정보올림피아드 필기] - 2020년 정보올림피아드 필기 중등부(1 ~ 5) 2024.04.11 - [알고리즘 설명/정보올림피아드 필기] - 2020년 정보올림피아드 필기 중등부(6 ~ 10) 11번 이렇게 초기 경우의 수가 나오는 문제는 DP로 출제되는 경우가 있습니다. 문제를 보면 피보나치 수열이 떠오르는 문제 입니다. 4를 만드는 경우를 생각해 보겠습니다. 4는 1을 만드는 경우에 3을 더해 만들 수 있습니다. 2에는 2를 더하고, 3에는 1을 더해주면 됩니다. 즉 4를 만드는 경우의 수는 1, 2, 3을 만드는 경우의 수의 .. 2024. 4. 13.

2020년 정보올림피아드 필기 중등부(6 ~ 10) 2020년 정보올림피아드 1차대회 중등부 필기 6번부터 10번까지 문제풀이 입니다. 이전 문제는 아래 링크 확인 바랍니다. 2024.04.09 - [알고리즘 설명/정보올림피아드 필기] - 2020년 정보올림피아드 필기 중등부(1 ~ 5) 6번 먼저 두 사람이 1부터 20까지의 자연수 중 임의로 하나씩 고를 경우의 수를 알아보겠습니다. A와 B 모두 20개를 고를 수 있기 때문에 20 * 20으로 400의 경우의 수를 가집니다. 다음으로 A가 B보다 큰 수를 고를 경우의 수 입니다. B가 1을 선택하면 A는 2부터 20까지중 아무거나 선택했을 때 A가 더 큽니다. B가 2를 선택했다면 A는 3부터 20까지 고를 수 있습니다. 마지막으로 B가 20을 선택했다면 A는 아무것도 선택할 수 없습니다. 즉 처음에는.. 2024. 4. 11.

2020년 정보올림피아드 필기 중등부(1 ~ 5) 2020년 정보올림피아드 1차대회 중등부 필기 1번부터 5번까지 문제풀이 입니다. 1번 페르마의 소정리를 알아야 이해하기 쉽습니다. https://davincicoding.tistory.com/12 페르마의 소정리 다빈치코딩 알고리즘에 나머지 정리에 대해 설명하다 분배 법칙에 대해 글을 쓰다보니 나눗셈에 대해서는 왜 분배 법칙이 적용이 안되는지를 설명하게 되었습니다. 그러면서 페르마의 소정리 davincicoding.co.kr 페르마의 소정리를 몰라도 a^(p-1) 을 p로 나눈 나머지가 1이라는 사실을 알려주었기 때문에 이를 이용해서 문제를 풀 수 있습니다. 7^(4 * 505) 를 5로 나눈 나머지는 결국 1이라는 것을 알 수 있습니다. 2번 초등부 3번과 같은 문제 입니다. 아래 링크를 통해 초등부.. 2024. 4. 11.

2020년 정보올림피아드 필기 초등부(2 - 4 ~ 2 - 8) 2020년도 정보올림피아드 1차 초등부 필기 문제 풀이 입니다. 2024.03.24 - [알고리즘 설명] - 2020년 정보올림피아드 필기 초등부(1 ~ 5) 2024.03.25 - [알고리즘 설명] - 2020년 정보올림피아드 필기 초등부(6 ~ 10) 2024.03.26 - [알고리즘 설명] - 2020년 정보올림피아드 필기 초등부(11 ~ 2 - 3) 2 - 4번 짧은 경로를 선택하다보면 쉽게 경로를 그릴 수 있습니다. 우선 이런 최단경로를 구하는 알고리즘은 다익스트라 알고리즘입니다. 하지만 다익스트라 알고리즘은 출발점과 도착점이 정해져 있습니다. 이렇게 출발점과 도착점이 정해지지 않았다면 플로이드 와샬 알고리즘을 사용합니다. 플로이드 와샬 알고리즘에 대해서는 아래 링크 확인 바랍니다. https:.. 2024. 3. 27.

2020년 정보올림피아드 필기 초등부(11 ~ 2 - 3) 2020년도 정보올림피아드 1차 대회 초등부 필기 11번부터 2 - 3번까지 문제 풀이 입니다. 이전 문제는 아래 링크 확인 바랍니다. 2024.03.24 - [알고리즘 설명] - 2020년 정보올림피아드 필기 초등부(1 ~ 5) 2024.03.25 - [알고리즘 설명] - 2020년 정보올림피아드 필기 초등부(6 ~ 10) 11번 A부터 Z까지 모든 경우를 생각하면 1부터 26까지 나타낼 수 있습니다. 따라서 숫자가 26보다 크다면 문자로 나타낼 수 없습니다. 즉 1234123의 중간에 있는 4는 앞에있는 숫자 3이랑 합쳐 34를 만들거나 뒤에 있는 1과 합쳐 41을 만들 수 없습니다. 4는 D 하나밖에 나타낼 수 없습니다. 그럼 123D123으로 나타낼 수 있습니다. 문제에서 123은 3개로 나타낼 .. 2024. 3. 26.

2020년 정보올림피아드 필기 초등부(6 ~ 10) 2020년도 정보올림피아드 1차 대회 초등부 필기 6번부터 10번까지 문제 풀이 입니다. 1번부터 5번까지는 아래 링크 확인 바랍니다. 2024.03.24 - [알고리즘 설명] - 2020년 정보올림피아드 필기 초등부(1 ~ 5) 2020년 정보올림피아드 필기 초등부(1 ~ 5) 2020년 정보올림피아드 1차 필기 시험 초등부 1번부터 5번까지 풀이 진행하겠습니다. 1번 나머지 연산을 이해하는지 묻는 문제 입니다. (A * B) % C 연산은 ((A % C) * (B % C)) % C로 나타낼 수 있습니다. davincicoding.co.kr 6번 이런 문제는 시뮬레이션을 통해 해결할 수 있습니다. 1번 상자부터 금화가 있다고 가정하고 사실 여부를 따져보면 문제가 해결 됩니다. 1번 상자 금화 참 참 거.. 2024. 3. 25.

2020년 정보올림피아드 필기 초등부(1 ~ 5) 2020년 정보올림피아드 1차 필기 시험 초등부 1번부터 5번까지 풀이 진행하겠습니다. 1번 나머지 연산을 이해하는지 묻는 문제 입니다. (A * B) % C 연산은 ((A % C) * (B % C)) % C로 나타낼 수 있습니다. 예를 들어 보겠습니다. (7 * 5) % 3 은 35 % 3 으로 2입니다. 이것을 분배하면 ((7 % 3) * (5 % 3)) % 3으로 (1 * 2) % 3으로 아까와 같이 2가 되는 것을 알 수 있습니다. 3^2020은 2020을 4로 나누면 505가 되고, 3^4를 505번 곱한것과 같습니다. 따라서 이 문제를 풀어보면 다음과 같습니다. ((3^4 % 5) * (3^4 % 5) … (3^4 % 5)) % 5로 나타낼 수 있습니다. 3 ^ 4 % 5는 1이기 때문에 결국.. 2024. 3. 24.

이전 1 다음

티스토리툴바