10주 완성 알고리즘 코딩테스트 [기초편]
    • 01
      튜토리얼 & 가이드
    • A. 강의 이용 규칙
      B. 문제 모범 답안집
      알고리즘과 자료구조
      알고리즘이 어려운 이유 1
      문제 해결하기
      문제의 구성
      채점 방식 이해하기
      공부하는 방법
      문제0A-출력해보기
      문제0B-입력받아보기
      문제0C-반복해보기
      문제0D-저장해보기
      문제0E-테스트케이스
    • 02
      챕터1. 선형 알고리즘 기초
    • 반복 알고리즘 이해하기
      문제1A-최대값 함수
      문제1B-원소의 합 구하기
      문제1C-배열의 최대값
      문제1D-카운팅하기
      문제1E-합 구하기2
      문제1F-탐색하기1
      문제1G-탐색하기2
      문제1H-탐색하기3
      문제1I-선택정렬 구현하기
      문제1J-합 구하기3
      단원 되짚어보기 & 해설
    • 03
      챕터2. 알고리즘의 연산량
    • 연산량과 시간복잡도
      실제 연산량 줄이기
      문제2A-도토리 키재기
      문제2B-오름차순인가?
      문제2C-다양성
      문제2D-문자열의 비교 (revised)
      문제2E-소수의 판별
      문제2F-데스티니
      문제2G-버블정렬 구현하기
      문제2H-픽셀 수 세기
      문제2I-정주행
      문제2J-승부 조작
      단원 되짚어보기
    • 04
      챕터3. 공간 활용하기
    • 공간과 배열
      문제3A-전화번호
      문제3B-페인트
      문제3C-응모
      문제3D-피보나치 나머지
      문제3E-색종이
      문제3F-과유불급
      문제3G-팬미팅
      문제3H-두 카드
      문제3I-세 카드
      문제3J-네 카드
      문제3K - 배열 합치기
    • 05
      챕터4. 자주 사용되는 수학 알고리즘
    • 정수와나머지에 대한 성질
      문제4A-스도쿠 보드
      문제4B-Probing
      문제4C-최대공약수와 최소공배수
      문제4D-수열의 순환
      문제4E-소인수 분해
      문제4F-소수 세기
      문제4G-배열 흔들기
      문제4H-카잉 달력
      문제4I-골드바흐의 추측
      문제4J-공약수 게임
    • 06
      챕터5. 자료구조 활용하기
    • Stack 자료구조 이해하기
      문제5A-괄호 문자열
      문제5B-탑
      문제5C-히스토그램
      Queue 자료구조 이해하기
      문제5D-조세퍼스 문제
      문제5E-폭탄 제거
      PriorityQueue 이해하기
      문제5F-폭탄 제거 순서 정하기
      문제5G-불안정 지역
      Map/Set 자료구조 이해하기
      문제5H-중복 제거하기
      문제5I-정사각형
      문제5J-빈도수 세기
      문제5K-시장 추천하기
      문제5L-배열합치기
      문제5M-이중 우선순위 큐
      문제5N-중앙값 큐
    문제2H-픽셀 수 세기
    배우기
    03 챕터2. 알고리즘의 연산량
    문제2H-픽셀 수 세기
    실습 내용

     컴퓨터는 이미지 정보를 2차원 배열 형태로 저장한다. 하지만 현실의 사물들의 모양을 그대로 저장하는 것은 불가능하다. 정밀한 이미지를 저장할수록 더 많은 공간과 연산량을 필요로 하기 때문이다. 영상을 구성하는 하나의 픽셀은 정사각형 형태로 존재하며 이 픽셀들이 모여 2차원 배열의 모양을 구성하게 된다.


    <반지름이 5픽셀인 원을 비트맵에 그렸을 때>


     반지름이 5픽셀인 원을 비트맵 형태로 저장하면 위와 같다. 그림에서 알 수 있는 것 처럼 실제로 원에 포함되는 픽셀들은 아래와 같은 특징을 가진다.

    • 네 점이 모두 원 안에 존재하거나
    • 원과 겹치는 영역이 존재하면서 두개 이상의 변이 원의 외곽선과 교차한다.


     그렇다면 반지름이 임의의 R픽셀인 원이 포함하는 픽셀의 수를 계산하는 프로그램을 작성해보자.


    입력 형식

     이 문제는 여러 개의 테스트케이스로 구성되어있다. 첫 줄에는 테스트케이스의 수를 나타내는 1이상 10이하의 자연수 T가 주어진다.

     각 테스트 케이스는 한 줄로 구성되며 계산하고자 하는 원의 반지름의 픽셀 수 R이 주어진다. R은 1이상 10만 이하의 자연수이다.


    출력 형식

     각 테스트케이스를 두 줄에 걸쳐서 출력한다. 

    • 테스트케이스의 첫 줄에는 테스트 케이스의 번호를 #1, #2, #3, ... 형태로 출력한다
    • 테스트케이스의 두 번째 줄에는 반지름이 R픽셀인 원이 포함하는 픽셀의 수를 출력한다.


    문제 출처

    • 中南大学第五届大学生程序设计竞赛
    입/출력 예시
    :
    공백
    :
    줄바꿈
    :
    예시 1
    입력
    2
    1
    5
    출력
    #1
    4
    #2
    88
    예시 2
    입력
    10
    100000
    99999
    99998
    99997
    99996
    99995
    99994
    99993
    99992
    99991
    출력
    #1
    31416325412
    #2
    31415696920
    #3
    31415069480
    #4
    31414441300
    #5
    31413811792
    #6
    31413184112
    #7
    31412555868
    #8
    31411927608
    #9
    31411299368
    #10
    31410671260
    ⋇ 입출력 형식을 잘 지켜주세요
    질문하기