'▷전체글보기' 카테고리의 글 목록 (3 Page)

▷전체글보기

[알고리즘 문제] 순환 소수 2016.11.20 (1)
[알고리즘 문제] 걸기 쉬운 전화번호 2016.11.17
Django에서 MySQL/MariaDB 사용시 Strict Mode Warning 2016.11.14
[알고리즘 문제] 0을 만들자 - Large 2016.11.09
안드로이드 스튜디오 NDK에서 C++11, STL 사용하기 2016.11.08
[알고리즘 문제] 구간 나누기 2016.11.05
C언어 숏코딩(코드골프) 몇 가지 2016.11.01 (3)
[알고리즘 문제] 판 채우기 2016.10.31
[알고리즘 문제] 단색이 좋아좋아 HARD 2016.10.28
[알고리즘 문제] 징검다리 2016.10.27

[알고리즘 문제] 순환 소수

2016. 11. 20. 21:32

알고리즘, 프로그래밍

출처

Koreatech OnlineJudge(링크)

문제이해

입력으로 두 수 A, B가 주어지고 A/B를 순환마디를 표시하여 출력하는 문제이다.

예를 들어 0.123579579579... 를 출력한다고 하면 0.123(579)와 같이 출력하는 것이다.

만약 입력이 1, 4로 계산결과가 0.25가 되어 나누어 떨어진다면 0.25(0)처럼 표현한다.

문제접근

출력해야 할 수가 그림과 같이 0.123579579579... 라면

순환마디 시작점인 a와 끝점인 b를 구해야 한다.

그렇다면 순환마디가 어디까지인지는 어떻게 구해야 할까?

나눗셈을 할 때 매 과정마다 몫과 나머지가 나오고 나머지를 다시 나누는 과정을 반복하는데, 매 과정마다 이 나머지 값을 저장해 두고, 저장됐던 나머지와 같은 값이 나올 때 반복을 종료한다. 이 때 해당 나머지 값이 처음 나온 부분이 순환마디의 시작이며, 다시 나온 부분이 순환마디의 끝이다.

구현

매 과정마다 나머지 값이 이미 저장되어 있는지 검사해야 하므로 STL map을 사용하면 적절하다. STL map은 레드-블랙 트리를 사용하고, map::find()는 O(logn)으로 어떤 원소가 존재하고 있는지 검사할 수 있다.

반복문의 종료조건은 아래와 같이 두 가지이다.

- 나머지가 0이 되었을 때 (유한소수)

- map::find()값이 map::end()와 다를 때 (나머지값이 중복하여 등장했을 때)

printf()함수를 사용하여 출력할 때

printf("%.*s", length, str);

의 형태로 사용하면 str이라는 char배열을 length길이만큼 출력할 수 있다.

실행결과

코드

코드에서 for(;~scanf.... 와 같이 되어 있는 부분은 문제를 빨리 풀기 위해 작성한 것으로, 데이터를 입력할 때 EOF를 입력해 주어야 프로그램이 제대로 완료된다.

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

ㅎㅎ 2018.11.13 15:09

생각해보다가 안풀려서 왔는데 어떻게 이런생각을 하셔서 푸신건지 내공에 감탄합니다...

# Delete Reply

[알고리즘 문제] 걸기 쉬운 전화번호

2016. 11. 17. 00:14

알고리즘, 프로그래밍

출처

Koreatech OnlineJudge(링크)

문제이해

전화번호를 누를 때 연속된 각 번호가 상하좌우로 한 칸씩만 떨어져 있는 번호를 '걸기 쉬운 전화번호'라고 한다. 예를 들어 1236987412는 '걸기 쉬운 전화번호'이다.

999와 같이 같은 숫자가 연속하여 나오면 이에 해당하지 않는다.

길이가 N인 '걸기 쉬운 전화번호'를 구하는 문제이다.

문제접근

DP(동적 프로그래밍)로 해결할 수 있는 문제이다.

길이가 n이고, m으로 끝나는 '걸기 쉬운 전화번호'를 f(n, m)으로 정의한다.

그러면 길이가 n인 '걸기 쉬운 전화번호'의 개수는

이다.

그리고 길이가 n일 때의 경우의 수는 길이가 n-1일 때를 사용하여 구할 수 있다.

예를 들어, f(n, 2)는 f(n-1, 1) + f(n-1, 3) + f(n-1, 5)로 나타낼 수 있는데, 2와 인접해 있는 숫자가 1, 3, 5이기 때문이다.

다시 말하면 끝자리가 1이나 3, 또는 5인 전화번호 다음에만 2가 붙을 수 있다는 것이다.

이런 방법으로 0부터 9까지의 숫자에 대해 점화식을 세워 보면 다음과 같다.

f(n, 0) = f(n-1, 8)

f(n, 1) = f(n-1, 2) + f(n-1, 4)

f(n, 2) = f(n-1, 1) + f(n-1, 3) + f(n-1, 5)

f(n, 3) = f(n-1, 2) + f(n-1, 6)

f(n, 4) = f(n-1, 1) + f(n-1, 5) + f(n-1, 7)

f(n, 5) = f(n-1, 2) + f(n-1, 4) + f(n-1, 6) + f(n-1, 8)

f(n, 6) = f(n-1, 3) + f(n-1, 5) + f(n-1, 9)

f(n, 7) = f(n-1, 4) + f(n-1, 8)

f(n, 8) = f(n-1, 0) + f(n-1, 5) + f(n-1, 7) + f(n-1, 9)

f(n, 9) = f(n-1, 6) + f(n-1, 8)

bottom-up 방식으로 메모이제이션을 하면 답을 구할 수 있다.

구현

각 번호에 대해, 길이가 1일 때의 초기값은 1로 한다.

f(1, 0) = f(1, 1) = f(1, 2) = ... = f(1, 8) = f(1, 9) = 1

이기 때문이다. (이 경우에 답은 10이 된다.)

길이가 2일때 위 0~9에 대해 점화식을 한 번 시행하면 되고,

길이가 3일때는 두 번 시행하면 된다.

주의할 점은 mod 1,000,000,007을 연산해야 한다는 것인데,

점화식에서 최대 4개의 항을 더하므로 32비트 unsigned int이상의 자료형을 사용하면 편하게 구현할 수 있다.

코드

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

Django에서 MySQL/MariaDB 사용시 Strict Mode Warning

2016. 11. 14. 12:53

Django, sql

Django에서 MySQL이나 MariaDB를 사용할 때 해당 데이터베이스가 Strict Mode가 아니면

"MySQL Strict Mode is not set for database connection 'default'" 라는 경고가 발생한다.

프로젝트명/settings.py의 DATABASES 설정 부분에서 OPTIONS에

'init_command': "SET sql_mode='STRICT_TRANS_TABLES'",

를 추가하면 된다.

참고 : http://dev.mysql.com/doc/refman/5.7/en/sql-mode.html#sql-mode-strict

[알고리즘 문제] 0을 만들자 - Large

2016. 11. 9. 23:48

알고리즘, 프로그래밍

출처

Koreatech OnlineJudge(링크)

문제이해

수열에서 수를 3개 뽑아서 합이 0이 되는 경우의 수를 구한다. 중복되는 경우는 계산하지 않는다.

문제접근

단순히 3중 for문으로 반복하여 찾으면 시간복잡도는 O(n^3)으로, 시간초과가 나서 통과하지 못한다.

세 수 i, j, k가 있을 때 i를 처음부터 한 칸씩 증가시키면서 각 i에 대해 j와 k를 찾으면 빠른데,

이 방법을 사용하려면 먼저 수열을 정렬해야 한다.

i+j+k > 0이면

k를 감소시키고,

i+j+k < 0이면,

j를 증가시킨다.

i+j+k = 0이면,

경우의 수를 한 번 카운트하고, k를 감소시키고 j를 증가시킨다.

그리고 반복문의 종료조건은 j와 k가 서로 교차했을 때이므로 아래 그림과 같은 경우까지 반복하게 된다.

시간복잡도는 O(n^2)이다.

이 부분을 코드로 보면 아래와 같다.

prv 변수는 중복되는 순서쌍을 제외하기위해 만든 변수이다.

(전체 코드는 맨 아래에 있음.)

while(j<k) {

if(arr[i]+arr[j]+arr[k] > 0)

--k;

else if(arr[i]+arr[j]+arr[k] < 0)

++j;

else {

if(prv != arr[j]) {

++cnt;

prv = arr[j];

}

--k;

++j;

}

구현

수열을 정렬할 때 std::sort()를 사용하면 간단하다.

위에서 중복을 제거하는 부분이 있었는데, 바깥쪽 반복문에서 i, j, k 중 i가 중복되는 경우 또한 제거한다.

실행결과

코드
https://github.com/tibyte/algorithm-problems/blob/master/koreatech/1005/1005.cpp

안드로이드 스튜디오 NDK에서 C++11, STL 사용하기

2016. 11. 8. 01:16

NDK, 안드로이드, 프로그래밍

메모형식으로 작성한 글입니다..

안드로이드 스튜디오에서 NDK로 C++11과 STL을 사용한 소스를 빌드하는 법.

C++가 아닌 C를 사용할 때는 makefile과 소스코드에서 약간의 차이가 있다. (본문 내에서 설명)

테스트 환경

Android Studio : 2.2.2

Gradle : 2.2.2

buildToolsVersion : 24.0.0

테스트 소스 코드

https://github.com/tibyte/practice-unclassified/tree/master/Android/NDKTest3

NDK 설치

File - Settings - Appearance & Behavior - System Settings - Android SDK

에서 SDK Tools로 들어가면 NDK를 설치할 수 있다.

javah 추가

File - Settings - Tools - External Tools에서 추가를 눌러 javah를 추가한다.

하단의 Tool settings에 들어갈 내용은 아래와 같다.

Program : jdk에 포함되어 있는 javah의 경로

Parameters : -v -jni -d $ModuleFileDir$/src/main/jni $FileClass$

Working directory : $SourcepathEntry$

java코드에서 네이티브 함수 사용

System.loadLibrary()로 사용할 라이브러리를 로드한다. 라이브러리 이름은 임의로 정해도 되는데, 이 글에서는 main.cpp를 만들 것이므로 여기에서는 main으로 정한다.

그리고 사용할 네이티브 함수명을 native키워드를 통해 선언한다.

package kr.tibyte.ndktest3;

import android.app.Activity;
import android.os.Bundle;
import android.widget.TextView;

public class MainActivity extends Activity {

    static {
        System.loadLibrary("main");
    }
    public native String getNativeText();


    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);

        TextView tv = (TextView)findViewById(R.id.text_view);

        tv.setText(getNativeText());
    }

}

JNI용 헤더파일 생성

프로젝트 탭에서 보기 설정을 Project로 한다.

네이티브 함수를 사용한 Java파일을 우클릭하여 External Tools - javah를 클릭한다.

그러면 src/main/jni 경로에 프로젝트_경로.h파일이 생성된다.

C++ 소스코드 작성

JNI디렉토리 내에 cpp파일을 만들고 소스코드를 작성하는데,

함수 이름에 패키지 경로가 들어있어야 한다. 이 부분이 실제 패키지 경로와 다르면 빌드가 되지 않는다. 아래 예제에서는 테스트 목적으로 STL과 C++11 기능을 사용했다.

#include <jni.h>

#include <vector>

#include <string>

#include "kr_tibyte_ndktest3_MainActivity.h"

using namespace std;

extern "C" {

JNIEXPORT jstring JNICALL Java_kr_tibyte_ndktest3_MainActivity_getNativeText(JNIEnv *env, jobject obj)

{

string str = "";

vector<char> vec;

vec.push_back('a');

vec.push_back('b');

vec.push_back('c');

for(auto& x : vec) {

x ^= 32;

str += x;

}

return env->NewStringUTF(str.c_str());

}

이 부분에서 C와 C++의 차이는 다음과 같다.

- 소스코드 확장자 (.c, .cpp)

- C++문법 사용여부

- C++에서는 함수 형식이 JNIEXPORT jstring JNICALL이지만, C에서는 jstring

- JNI함수를 호출할 때 C++에서는 env->NewStringUTF("string") 형식을 사용하지만,

C에서는 (*env)->NewStringUTF(env, "string"); 형식으로 리턴.

- C++에서 extern으로 네임 맹글링을 어떤 규칙으로 할 것인지 지정(참고링크)

Makefile 설정

jni디렉토리 안에 Android.mk와 Application.mk 파일을 생성하고 각각 아래와 같은 내용을 적는다.

Android.mk

LOCAL_PATH := $(call my-dir)

include $(CLEAR_VARS)

LOCAL_DEFAULT_CPP_EXTENSION := cpp

LOCAL_MODULE := main

LOCAL_SRC_FILES := main.cpp

LOCAL_LDLIBS := -llog -latomic

LOCAL_C_INCLUDES := $(LOCAL_PATH)/include-all

include $(BUILD_STATIC_LIBRARY)

C로 빌드할 때에는 LOCAL_DEFAULT_CPP_EXTENSION := cpp가 필요하지 않다.

LOCAL_MODULE과 LOCAL_SRC_FILES는 작성한 C/C++네이티브 소스파일과 관련된 내용을 적는다.

Application.mk

NDK_TOOLCHAIN_VERSION := 4.9

APP_STL := gnustl_static

APP_MODULED := main

APP_ABI := armeabi-v7a

APP_CPPFLAGS += -std=c++11

LOCAL_C_INCLUDES += ${ANDROID_NDK}/sources/cxx-stl/gnu-libstdc++/4.9/include

NDK_TOOLCHAIN_VERSION : NDK설치경로/sources/cxx-stl/gnu-libstdc++ 에 있는 툴체인 버전을 적는다.

APP_STL : 정적 라이브러리를 사용하고 싶을 경우 gnustl_static를, 공유라이브러리를 쓸 대는 gnustl_shared를 적을 수 있다.

APP_ABI : 빌드할 대상 아키텍쳐를 적는다. all로 적으면 모든 대상으로 빌드할 수 있다.

APP_CPPFLAGS : C++11로 빌드하려면 -std=c++11 플래그를 넣는다.

LOCAL_C_INCLUDES : 자신이 가진 버전에 맞는 경로를 적는다. (NDK설치경로 확인)

build.gradle ndk 정보 추가

src디렉토리 내에 있는 defaultConfig안에 다음과 같은 내용을 추가한다.

ndk {

stl "gnustl_static"

moduleName "main"

}

stl에서 gnustl_static은 Application.mk에서 설정했던 것과 같은 것이고,

moduleName은 Android.mk, Application.mk, java파일에서 썼던 것과 같다.

만약 STL을 사용하지 않을 것이면 stl은 작성하지 않아도 된다..

실행화면

STL vector와 C++11의 auto를 사용한 코드가 정상적으로 빌드된다.

[알고리즘 문제] 구간 나누기

2016. 11. 5. 23:55

알고리즘, 프로그래밍

출처

Koreatech OnlineJudge(링크)

문제이해

수열을 각 부분당 2개 이상의 원소를 가지는 구간으로 나눌 때,

각 구간의 최댓값-최솟값 값의 합이 최대가 되도록 하려면

구간을 어떻게 나누어야 하는지 구하는 문제이다.

문제접근

동적 프로그래밍(DP)으로 풀 수 있는 대표적인 유형이다.

문제 푸는 과정을 보면 다음과 같다.

j부터 j+i까지의 구간 S가 있을 때

이 구간을 j부터 k까지, k+1부터 j+i까지

두 개의 구간 Sa와 Sb로 나누는 것이 더 이득일 수 있다.

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)을 생각해 보면 이해가 쉽다.

즉, 수열 인덱스 j부터 j+i까지의 최대이득을 D[a][b]라고 하면,

D[j][j+i] 보다 큰 D[j][k]+D[k+1][j+i]를 찾는 것이다.

큰 크기의 문제(D[j][j+i])를 풀기 위해 작은 크기의 문제(D[j][k]+D[k+1][j+i])

의 값이 필요하므로, 구간 길이가 2일 때부터 계산해야 한다.

수열의 길이가 5라고 가정하여 이 과정을 보면,

아래 그림과 같이 구간 길이가 2일때를 계산한다.

그 다음 구간의 길이가 3인 경우,

4인 경우,

마지막으로 5인 경우를 계산한다.

이 글 맨 마지막에 있는 코드를 보면 이해가 쉬울 것이다.

구현

문제 조건에서는 구간 길이는 2보다 같거나 크지만, 실제 구현할 때에는 구간 길이가 1인 경우도 계산해야 규칙성 있는 반복문을 작성할 수 있다.

구간 길이가 1일 때의 해는 그 원소 자신의 값이 된다.

코드
https://github.com/tibyte/algorithm-problems/blob/master/koreatech/1059/1059.c

C언어 숏코딩(코드골프) 몇 가지

2016. 11. 1. 23:59

프로그래밍 문제풀이 사이트에서 재미로 해 볼 만한 숏코딩 기법들.

소스코드의 바이트 수를 최대한 줄여보는 것이다.

특정 컴파일러에서만 되는 부분이 있기 때문에 문제풀이 사이트의 컴파일러 종류와 버전을 고려해서 해야 한다...

1. 컴파일러의 특성에 따라 코드를 최대한 생략한다.

gcc컴파일러에서는 #include <stdio.h>를 생략해도 되고,

main함수의 반환형이나 리턴을 생략해도 된다.

main(){printf("Hello Wolrd!");}

2. 문자열 출력만 있는 경우 printf()대신 puts()함수를 사용한다.

2바이트를 더 줄일 수 있다.

main(){puts("Hello Wolrd!");}

3. 반복문을 쓸 때 scanf()함수의 반환값을 이용한다.

scanf()함수는 EOF(end of file)가 입력되었을 때 0을 반환하므로

이것을 이용하여 for문을 작성한다.

for(;~scanf("%d",n);)

4. 배열 입력을 받을 때 포인터를 사용한다.

첨자(subscript)연산자를 사용하는 것보다 1바이트를 더 줄일 수 있다.

경우에 따라 i를 0으로 초기화하는 구문이 필요할 수도 있다.

a[100],i;

main(){

for(;~scanf("%d",a+i++););

}

5. 배열을 전역변수로 선언한다.

이렇게 선언된 배열은 0으로 초기화되어 있어서 초기화하는 구문을 줄일 수 있다.

a[100];main(){}

6. 변수를 main()함수 안에서 선언하는 대신 매개변수 자리에 쓴다.

세미콜론과 데이터형을 생략할 수 있다.

main(a,b,c,d){}

7. 테스트 케이스 입력을 버린다.

3번에서처럼 scanf()의 반환값을 이용하면 테스트 케이스 입력을 버려도 되는 경우가 있다.

이 코드는 다른 메모리를 침범할 수 있는 위험이 있지만 Judge사이트에서 채점만 통과하면 그만이다...

main(T){

gets(&T);

for(;~scanf("%d",n);){

//n처리

}}

8. 문자열을 선형탐색할 때 널문자의 값이 0인 것을 이용한다.

널 문자('\0')는 정수로 0이기 때문에 for문 조건식에서 조건을 끝내는 데 사용할 수 있다.

char s[100];

gets(s);

for(i=0;s+i++;){

//처리

}

9. 한 테스트 케이스에 대한 결과출력을 for문 증감식에서 한다.

세미콜론을 생략함으로써 1바이트를 더 줄일 수 있다.

for문 안의 구문을 1행으로 만들 수 있으면 2바이트를 추가로 줄일 수 있다.

for(;~scanf("%d",a);printf("%d",b)){

//처리

}

10. 3항 연산자(?:)를 사용한다.

가독성을 희생하여 짧은 코드를 얻을 수 있다.

puts(a%3?"Fizz":"Buzz");

min=d1<d2?(d1<d3?d1:d3):(d2<d3?d2:d3);

11. 홀짝 판별과 동등비교시 비트 연산자를 사용한다.

홀수/짝수 판별을 할 때 &(AND)연산자를 사용하여 2바이트를 줄일 수 있고,

동등비교를 할 때 != 대신 ^(XOR)연산자를 사용하여 1바이트를 줄일 수 있다.

전자는 연산자우선순위가 아래 예시와 같을 때 해당한다.

if(a&1) //a가 홀수일 때 참이 됨

if(a^b) //a!=b일때 참이 됨

12. 특정 컴파일러에 의존적인 함수를 찾는다.

예를 들어 엔디안을 변환하는 POSIX 라이브러리 함수로 이런 문제를 63바이트 이내로 코딩할 수 있다.

13. 효율적인 알고리즘으로 문제를 푼다.

이 방법이 근본적으로 코드 길이를 줄일 수 있는 방법이다.

1부터 n까지의 정수를 모두 더하는 코드를 작성할 때 반복문을 사용하는 대신 n*(n+1)/2 로 계산하면 더 짧다.

한 원소만 제외하고 같은 원소가 2개씩 들어있는 배열 ex) {5, 3, 2, 4, 1, 4, 5, 1, 3} 에서 단독으로만 존재하는 원소가 무엇인지 찾으려면, 반복문을 돌릴 필요 없이 모든 원소를 XOR로 누적하면 된다.

이 밖에도 기계어를 사용하는 등 여러 가지 재미있는 방법들이 많다..

익명 2018.08.04 00:57

비밀댓글입니다

# Delete Reply
- 티바이트 2018.08.20 01:47 신고
  
  scanf() 함수의 반환값에 대해 비트NOT연산을 한 것입니다.
  
  # Delete
익명 2022.04.16 17:06

비밀댓글입니다

# Delete Reply