출처

Koreatech OnlineJudge (링크)




문제이해

소수 719333은 큰 자리부터 순서대로 붙여 나간 각각의 수

7, 71, 719, 7193, 71933이 모두 소수이다.

문제에서 이러한 수를 '접두 소수'라고 정의한다.

수의 길이 n이 주어졌을 때 n자리인 접두 소수를 출력하는 문제이다.

 



문제접근

우선 소수를 판별하는 함수를 작성해야 한다.

n이 소수인지 판별할 때 2부터 n까지 나눠봐서

나누어 떨어지는 경우가 있으면 소수가 아니고, 없으면 소수이다.

그런데 이렇게 하면 n이 커지는 경우 연산량이 비례해서 늘어나므로 연산량을 줄여야 한다.

약수는 대칭성이 있기 때문에 sqrt(n)까지만 나눠봐도 소수를 판별할 수 있다.


다음은 n자리의 접두소수를 백트래킹(Backtracking)으로 구해야 하는데, 

한 자리 소수인 2, 3, 5, 7부터 시작하여 다음 자리수를 검사한다.




3부터 시작하는 경우 다음 자리는 짝수와 5의 배수를 제외한

31, 33, 37, 39를 소수판별하면 되는 것이다.




구현

재귀함수나 스택, 큐 등을 사용하여 구현할 수 있다.


main()함수 내에서 다음과 같이 2, 3, 5, 7와 전체 자리수를 주어 시작하고,

print(2, digit);

print(3, digit);

print(5, digit);

print(7, digit); 


print()함수 내에서는 digit이 1이 되었을 때 탈출하면서 출력을 하도록 조건을 주었다.


그리고 아래와 같이 다음 자리에 해당하는 재귀호출을 한다.

n *= 10;

for (int i = 1; i < 10; i += 2) {

if (i == 5) continue;

if (isPrime(n + i)) {

print(n + i, digit-1);

}





실행결과





코드

https://github.com/tibyte/algorithm-problems/blob/master/koreatech/1010/1010.cpp





출처

Koreatech OnlineJudge (링크)



문제이해

10진수 숫자 A와 진법을 나타내는 수 B가 주어질 때

A를 B진법으로 표현하여 출력하는 문제이다. 



문제접근

수학 교과과정에 나오는 것과 같이 A를 B로 계속 나누면서

매 과정마다 나머지를 기록하면 변환할 수 있다.

자세한 과정과 코드는 이전에 쓴 글(http://tibyte.kr/261) 참고.



구현

재미로 숏코딩을 해 보면, gets()를 사용하여 케이스 수를 버리고, scanf()의 EOF반환값을 이용하여 120B까지 줄일 수 있다. 

숏코딩 정리 : http://tibyte.kr/270



입출력 예시



코드

https://github.com/tibyte/algorithm-problems/blob/master/koreatech/1031/1031.c



- 웹폰트 설치

- 블로그 메인화면 추가

- center태그 css로 변경

- 사용하지 않는 JS 제거

- 레이아웃 변경(글자크기 등)





공부목적으로 Koreatech OnlineJudge 문제를 정리해봅니다.
간단한 문제는 제외하고 시간나는대로 한 문제씩 포스팅 예정입니다.
난이도는 주관적 판단입니다...
(2016년 12월 8일 현재 12문제 작성)


번호

문제명

분류

난이도

1005

0을 만들자 - Large


★★

1007

유일한 수

비트연산

1008

순환 소수

수학

★★★

1010

접두 소수

백트래킹

1011

징검다리

DP

1014

다이얼 자물쇠

MST

★★★

1016

소수로 만들어진 숫자

DP

★★

1017

돈을 줍자

DP

1018

문자열 거리 최소화 하기

문자열 검색

1019

숫자 바꿔치기

반복문

★★★

1027

인접한 문자 제거하기 HARD

스택

1028

단색이 좋아좋아 HARD

반복문

1030

한번 주식 거래하기


1031

다양한 진법 변환

수학

1042

두번 주식 거래하기


★★★

1043

위성 사진

그래프

★★

1046

빠른 길 찾기

그래프

1048

AP 배분

수학

★★★

1055

판 채우기

DP

★★

1057

걸기 쉬운 전화번호

DP

1058

동전 거슬러 주기

DP

★★

1059

구간 나누기

DP

★★

1060

팰린드롬 만들기

DP

★★

1067

펠린드롬 길게 만들기

 

 

1068

숫자 이어 붙이기


★★

1073

물 주기

수학

★★★

1074

유일한 수 두개

비트연산

★★



  1. 익명 2016.10.29 01:48

    비밀댓글입니다


십진수 11을 이진수로 바꾸려면 

아래와 같은 과정을 거치면 된다.

ⓛ 11을 2로 나누면 몫은 5, 나머지는 1이다.
② 5를  2로 나누면 몫은 2, 나머지는 1이다.
③ 2를 2로 나누면 몫은 1, 나머지는 0이다.
④ 1을 2로 나누면 몫은 0, 나머지는 1이다.

나머지가 순서대로 1, 1, 0, 1로 나오는데 이것을 뒤집으면
1, 0, 1, 1이 나오게 되고 이것이 십진수 11의 이진수 표현 1011이다.






십진수 m을 n진법으로 나타내는 과정도 이와 같다.

 m을 n으로 나누어 m을 몫으로 갱신하고 나머지 b1를 얻는다.

 m을 n으로 나누어 m을 몫으로 갱신하고 나머지 b2를 얻는다.

...

...


이같은 과정을 m이 0보다 작아질 때까지 반복하고,

얻은 b수열을 뒤집으면 n진법 표현을 얻을 수 있다.




아래는 C++로 구현한 코드이다. (예외처리는 하지 않음)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <string>
#include <algorithm>
 
int main()
{
    std::string marks = "0123456789ABCDEF";
    std::string str;
    int num, base;
 
    std::cin >> num >> base;
    
    for(;num>0;) {
        str += marks[num%base];
        num /= base;
    }
    
    std::reverse(str.begin(), str.end());
    
    std::cout << str << std::endl;
    
    return 0;
}
cs




C++의 string를 사용하는 대신, 배열의 뒤쪽에서부터 값을 채워나가면

뒤집는 동작을 하는 코드를 사용하지 않아도 된다.

대신 출력할 때 시작 위치 주소를 맞게 설정해야 한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
 
int main()
{
    int num, base;
    char res[32];
    int i = 30;
 
    scanf("%d%d"&num, &base);
    
    for(;num>0;) {
        res[i--= "0123456789ABCDEF"[num%base];
        num /= base;
    }
    res[31= '\0';
    
    printf("%s\n", res+i+1);
    
    return 0;
}
cs









g++ 컴파일러에서 (C++언어)

아래와 같은 헤더를 인클루드하여 사용할 수 있다.


#include <bits/stdc++.h>



해당 헤더파일을 확인해 보면(링크),

cstdio, cstdlib, cmath 등 C언어 표준헤더들과

stack, queue, vector 등과 같은 STL관련 헤더들을 포함하고 있는 것을 볼 수 있다.


프로그래밍 대회 등에서 이 헤더를 사용하여 코딩시간을 단축할 수 있다.

C언어 표준헤더가 아니므로 Visual Studio에서는 사용할 수 없다.



ex)


#include <bits/stdc++.h>


int main()

{

    std::stack<int> s;

    std::queue<int> q;

    std::vector<int> v;


    printf("abc\n");

    printf("%d\n", (int)sqrt(100));

   

    return 0;

}


http://tibyte.kr/258

에서 이어지는 글입니다.


라즈베리파이나 VPS에 putty로 연결하면 다음과 같이 색상이 제대로 표시되지 않는 경우가 있다.





TERM 환경변수를 확인해 보면 컬러를 지원하지 않는 터미널 에뮬레이터로 설정이 되어 있을 것이다.





export로 TERM환경변수를 재설정한다.


$export TERM=xterm-256color





그러면 이제 색상이 정상적으로 표시된다.






그러나 리눅스를 재부팅하면 설정이 다시 초기화되기 때문에

home 경로에 있는 .profile 파일을 편집하여  맨 마지막줄에


export TERM=xterm-256color를 추가해야 한다.




Windows 기준으로 작성된 포스트입니다.




USB to TTL Serial Cable을 이용하여 모니터나 LAN케이블 없이

PC와 라즈베리파이 콘솔을 연결할 수 있다.

(이 글에서 사용한 제품은 http://www.devicemart.co.kr/1164522 에서 구입함.)


흰색 선(RXD)을 라즈베리파이의 TXD핀에 연결하고

초록 선(TXD)을 라즈베리파이의 RXD핀에 연결한다.


그리고 빨간 선(Vcc)와 검정 선(GND)를 연결하는데, 이 때 외부전원이 있으면 안 된다. 


(주의 : 맨 끝에 핀 하나 비워져 있습니다.)



그리고 해당제품에 맞는 드라이버를 구글 등에서 검색하여 설치한다.

많은 제품에서 Prolific PL2303을 사용하고 있다.. 





드라이버 설치 후 USB 포트에 연결을 하면 

Windows 장치 관리자에서 COM포트번호를 확인할 수 있다.





PuTTY를 사용하여 해당 포트를 입력하는데,

이 때 Connection Type은 'Serial'로 하고,

Speed(Baudrate)는 115200으로 맞춘다.






Open을 눌러보면 아무것도 안 뜨는 경우가 있는데,

LAN으로 SSH연결할 때와는 달리 새로 터미널을 여는 것이 아니므로

이 상태에서 id를 치고 enter를 누르면 된다.






※연결이 되지 않을 때

Raspbian버전에 따라 시리얼 설정이 안 되어 있어서 초기에 연결이 되지 않을 수도 있다.


1. Raspbian 운영체제가 설치되어 있는 Micro SD 카드를 PC에 연결한다.


2. config.txt 파일을 열고 맨 아랫줄에 있는

 enable_uart=0

 enable_uart=1

로 수정하고 저장한다.


3. cmdline.txt 파일을 열고 

 console=tty1

 console=serial0,115200 console=tty1

으로 수정하고 저장한다.


4. Micro SD카드를 다시 라즈베리파이에 넣고 부팅한다.


나중에 UART를 이용하여 다른 것을 만들고자 할 때는 부팅된 상태에서 별도의 명령으로 이것을 해제할 수 있다.





터미널 색상이 모니터로 볼 때와는 다르게 흑백으로 나오는데

이것에 관해서는 다음 포스트에서 다룬다.

http://tibyte.kr/259








[](Array subscripting 연산자) 가 *(indirection)보다 우선순위가 높으므로


int *arr2[3]은 배열이며 int * 타입을 3개 담을 수 있는 배열이고

int (*arr2)[3]은 포인터이며, int[3]타입을 가리킬 수 있는 포인터이다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
 
int main()
{
    int arr1[] = {102030405060708090};
    int (*arr2)[3= (int(*)[3])arr1;
    
    for(int i=0; i<3; i++) {
        for(int j=0; j<3; j++) {
            printf("%d ", arr2[i][j]);
        }
    }
    
    return 0;
}
cs



링크 : http://codeforces.com/contest/723


A : The New Year: Meeting Friends

 세 사람이 있는 수직선 위의 세 지점이 주어지고, 모두의 이동거리의 합이 최소가 되는 약속지점을 찾는 문제이다. 교내대회에서 유사한 문제를 풀어본 적이 있어서 금방 해결할 수 있었다. 위치를 정렬했을 때 중간값이 되는 지점을 찾아야 하는데,  입력이 항상 3개라 조건문으로도 찾을 수 있겠지만 코드를 빨리 작성하려고 std::sort()를 사용하여 해결했다.


B : Text Document Analysis

 주어지는 문자열에서 괄호 밖에 있는 단어 중 가장 긴 단어와, 괄호 안에 있는 단어의 개수를 구하는 문제. 

괄호 안에 있는 단어 수를 셀 때, 언더스코어 또는 여는 소괄호 다음에 나오는 단어를 카운팅하는 것으로 간단하게 짤 수 있었다.


C : Polycarp at the Radio

 문제를 이해하지 못해서 시간만 소비하고 포기...


D : Lakes in Berland

 물과 육지를 나타내는 2차원 배열이 입력으로 주어지고, 호수의 개수를 주어진 수로 줄일 때 메워야 하는 영역의 최소 수를 구하는 문제이다.

  먼저 호수와 바다를 구분하기 위해 바깥쪽에 있는 물을 따로 표시했다. 최대 입력의 크기인 50x50보다 더 큰 52x52 배열을 만들고 바깥의 물을 BFS하여 바다로 표시했다.

 그리고 안쪽의 물 역시 BFS를 사용하여 영역의 개수를 세고, 각 영역의 크기와 시작점을 구조체로 저장해 두었다. 그리고 영역크기 순으로 소팅하여 작은 것부터 채우는 것으로 코드를 작성하였다.


A, B, D를 풀고 C도 풀어보려다가 시간이 다 되어 E, F번 문제는 못 풀어보았다..



Rank : 640

Rating : 1456 -> 1531 (+75)

 

  1. 익명 2016.10.08 22:03

    비밀댓글입니다

+ Recent posts