본문 바로가기

박기완 코딩교육/정보올림피아드 대비

정올 초등 1998 KOI 자동차경주대회. 1차 도전 실패 오늘 도전해본 문제는 정올초등 1998 KOI 자동차경주대회 문제였다. codeup.kr/problem.php?id=4442 자동차 경주대회 문제2) 전국 자동차 경주 대회가 매년 열리고 있다. 이 대회에서는 출발지점부터 도착지점까지 거리가 워낙 멀기 때문에 경주 도중에 각 자동차는 정비소를 방문하여 정비를 받아야 한다. 정비�� codeup.kr 정비를 받지않고 갈 수 있는 거리가 주어졌을때, 출발지에서 목적지까지 도달하려면 최소 몇군데의 정비소를 들려야하는가 를 해결해야했던 문제다. 결과부터 말하면 첫도전은 실패했다. 경우의수를 똑바로 계산해내서 전체탐색방식은 피했어야했는데 그러질 못했다. 경우의수를 잘못계산했다. 해당 정비소를 들리냐 안들리냐로 생각후, 2^n 라는 경우의수를 얻었어야했는데, 정비소.. 더보기
정보올림피아드 초등 _ 지역본선 2014. 4번문제 저울 안녕하세요! 오늘은 정올 초등 2014년에 지역본선으로 나왔던 4번문제 '저울'을 풀어보았습니다. codeup.kr/problem.php?id=4805 저울 문제4) 저울 (초등4, 중등3, 고등2) 무게가 서로 다른 N개의 물건이 있다. 각 물건은 1부터 N 까지 번호가 매겨져 있다. 우리는 일부 물건 쌍에 대해서 양팔 저울로 어떤 것이 무거운 것인지를 측정�� codeup.kr 처음엔 물건 비교결과를 어떤식으로 나열해야할지 감이 안와서 고민해봤는데, "물건 비교결과를 알수없는 갯수"를 출력해야한다는 문장을 보고선 그래프 형태로 표현하고 탐색할 수 있냐 없냐갖고 따지면 쉽게 풀릴거같단 느낌이 와서 그래프로 표현하게 되었습니다. 위 사진처럼 연결관계그래프라는걸 사용했고 문제 해결 소스와 문제풀이과정 영상.. 더보기
정올 초등_ 회장뽑기 KOI 1997 이번에 풀어본 문제는 초등부 정올 회장뽑기 문제입니다. 처음엔 문제 내용부터 이해가 잘 안가서 고생했는데, 입력예시랑 결과 보고 다시 문제보니까 이해했습니다. 단순 BFS문제였고 각 회원마다 점수들 저장시켜서 최종적으로 가장 적은 점수 가진사람들 출력하면 끝나는 쉬운 문제였습니다. codeup.kr/problem.php?id=4433 회장뽑기 문제3) 월드컵 축구의 응원을 위한 모임에서 회장을 선출하려고 한다. 이 모음은 만들어진지 얼마 되지 않았기 때문에 회원 사이에 서로 모르는 사람도 있지만, 몇 사람을 통하면 모두가 서로 알 codeup.kr #include #include #include using namespace std; struct info{ int number; int score; }; b.. 더보기
코드업 4432 십자카드 초등 정올 이번 십자카드 문제는 시계방향이란 컨셉에 어느 점을 시작점으로 하냐에따라 숫자가 달라지다보니 뭔가 어렵다란 느낌이 들 수 도 있다. 하지만 실제론 1차원배열에 넣고 숫자읽기만 하면 쉽게 해결되는 문제다. 단순히 십자카드가 주어지고 시계수 찾아라하면 레벨1정도로해서 간단하게 끝날 수준인데 난이도가 하나 더 올라갔다. 모든 시계수들 중에서 입력된 카드의 시계수가 몇번째로 작냐라는 조건. 그래서 모든 시계수를 어떻게 구해야할지 고민해봤다. 십자카드 숫자들에대해 시계수를 만들어내는 원리를 좀더 생각해봤지만 결국엔 나올 수 있는 숫자 경우수가 9*9*9*9 즉 6561개밖에 없어서 그냥 일일이 다 따져도 시간초과가 안뜰거란 생각이 들었다. 이렇게까지 생각후 코드구현 시작 #include #include using.. 더보기
코드업 4562 숫자의 개수 초등부 정올 이 문제도 굉장히 기본기를 묻는 문제다. 글 읽자마자 1차원배열의 인덱스를 활용할 줄 아는가를 테스트 하는구나 싶었다. 1차원배열 10칸짜리를 만들어 0번째부터 9번째 인덱스까지를 0부터 9까지의 숫자 갯수를 담을 공간으로 바라보면 풀린다. 정수형 데이터를 0이될때까지 10으로 나눠가면서 나오는값들 카운팅해보자 #include int main() { int datas[10]={}; int num1,num2,num3; scanf("%d",&num1); scanf("%d",&num2); scanf("%d",&num3); int res = num1*num2*num3; while(res>0){ //해당 숫자를 바로 배열 인덱스이용해서 숫자갯수 세기 datas[res%10]++; res/=10; } for(int.. 더보기
코드업 4532 곱셈 [ 정보올림피아드 초등] 디게 신선한 문제다. 어떤 능력을 요구해서 낸 문제일까? 내가 생각하기엔 딱히 특유의 알고리즘없이 기본 코딩실력보는 문제랄까. 문제 해결의 키는 두번째 값에대해 자리별 숫자를 어떻게 얻어낼것인가 이다. 문자열 형태로 입력받아서 처리할수도 있지만 세자릿수라는게 명확히 정해져있는 상황이여서 나머지 연산자를 이용해 자리별 숫자들을 얻어냈다. **자리별 숫자 구하는 과정에서 연산자 우선순위 문제로 잘못될수있으니 괄호로 명확히 표현 이 둘의 차이랄까? int n1 = first* (second%10); int n1 = first* second%10; #include int main() { int first; int second; scanf("%d",&first); scanf("%d",&second); /* 접근방.. 더보기
코드업 4423 직사각형 네 개의 합집합 면적 구하기 [초등부 정올] 이건 굉장히 쉬운문제다. 사실 어렵게 들어가면 x축 y축 영역들 다 나눠가며 계산해내는건데 초등부 정올이라그런지 그정도 난이돈 아니다. 단순히 100x100짜리 2차원짜리 배열에 해당영역들을 숫자 1로 채워넣는다 생각하면 쉽게 풀린다. #include int main() { //100*100 크기 영역만들어서 1로 채워넣을예정 int maps[101][101]={}; for(int i=1;i 더보기
코드업 4422 숫자고르기 해설. 정보올림피아드 초등 (정올 초등) 4번의 시도끝에 맞춘 재미있는 문제다. 해당 숫자가 있는지 없는지를 DFS로 탐색해서 판단했다. 항상 어떤 문제를 풀든 직접 따져봐야한다. 내 머릿속이 이 결과를 어떻게 만들어내는지 분석해서 번호를 메기고 그 순서대로 구현해야한다. 그렇지않으면 뻘짓하다가 시간만 날린다. #include using namespace std; bool solve(int nowNum, int startNum, int *data, int *result, int n){ if(nowNum == startNum){ result[nowNum]=1; return true; } for(int i=1;i 더보기