TWpower Reading time ~1 minute

Python에서 연산자 ‘/’와 ‘//’의 차이를 알아보자


환경

  • Python


연산자 ‘/’와 ‘//’의 차이

  • /는 나눗셈을 의미하며 결과가 float로 나타납니다.
  • //는 나눗셈을 의미하며 결과가 int로 나타납니다.


코드

  • /의 경우
>>> type(5/2)
<class 'float'>
  • //의 경우
>>> type(5//2)
<class 'int'>
TWpower Reading time ~1 minute

주어진 문자열이 palindrome(회문)인지 확인하는 코드를 작성해보자


환경 및 선수조건

  • Python
  • C++


Palindrome(회문)이란?

  • Palindrome(회문)은 문자열을 거꾸로 해도 원래의 문자열과 같은 문자열인 특징을 가지고 있는 문자열을 가리키는 말입니다.
  • 예시: 토마토, abdba, 토마토맛토마토, 1234567654321


코드

  • 시간복잡도: O(n)


C


#include <stdio.h>
#include <string.h>

int is_palindrome(char * s){

	int len = strlen(s);

	int left = 0;
	int right = len-1;


	// 왼쪽과 오른쪽을 하나씩 가운데로 향하면서 비교
	// (right - left) > 1
	// [홀수 길이의 경우] 가운데 원소만 남겨두거나
	// [짝수 길이의 경우] "left + 1==right"일 때까지!
	while ( (right - left) > 1 ) {

		if( s[right] != s[left] ){
			return 0;
		}
		left += 1;
		right -= 1;
	}

	return 1;

}


int main (){


	char * palindrome = "abcdcba";
	char * non_palindrome = "abcdefg";

	printf("%d\n", is_palindrome(palindrome));
	printf("%d\n", is_palindrome(non_palindrome));

	return 0;

}


C++


#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

bool is_palindrome(string s){

	string s_reverse = s;
	reverse(s_reverse.begin(), s_reverse.end());
	return s == s_reverse ? true : false;

}


int main (){

	string s1 = "abcde1edcba";
	string s2 = "asdlkfjaw;oefjao;iwefja;ow";

	cout << is_palindrome(s1) << '\n';
	cout << is_palindrome(s2) << '\n';

	return 0;

}


Python


def is_palindrome(s):
	return s == s[::-1]


s1 = "abcde1edcba"
s2 = "fjaw;"

print(is_palindrome(s1))
print(is_palindrome(s2))


참고자료

TWpower Reading time ~3 minutes

Update(2021.10.11): Add setting value related to pyenv

Setting Python and Node.js environment in Travis CI, build and test using Appium.


Environment and Prerequisite

  • Travis CI
  • Experience of test Android using local Appium(Server+python-client)


Process

We can use default Android environment in Travis CI. We will set up Appium(Node.js and Python) environment in yml.


  1. Android Setting
    • language and base setting
    • sdk and android related setting
  2. Python Environment Setting
    • install pyenv and virtualenv
    • set virtual environment and install packages(pytest, Appium-Python-Client etc…)
  3. Node.js Environment Setting
    • install node.js
    • install appium
  4. Run Appium
  5. Run Emulator
  6. Build and Test


1. Android Setting

Our Travis CI already serves all environment for android. Just type somethings like SDK or build-tools and others.

language and base setting

.travis.yml

language: android
sudo: required # We need sudo
jdk: oraclejdk8 # Can be changed by your preference


.travis.yml

language: android
sudo: required # We need sudo
jdk: oraclejdk8 # Can be changed by your preference

android:
    components:

        # Below codes are for using latest Android SDK Tools
        - tools
        - platform-tools

        # build-tools
        - build-tools-26.0.2

        # The SDK version used to compile your project
        - android-26
        - android-22
        - android-24

        # Additional components
        - extra-google-google_play_services
        - extra-google-m2repository
        - extra-android-m2repository
        - addon-google_apis-google-26

        # System image for your emulator
        # You need at least one system image
        - sys-img-armeabi-v7a-android-22
        - sys-img-armeabi-v7a-android-24


2. Python Environment Setting

Install pyenv and virtualenv for python environment. We need python for installing Appium-Python-Client in Appium

install pyenv and virtualenv

.travis.yml


...

# I just type install codes in before_install part
before_install:
    - sudo apt-get update

    # Install ubuntu packages for later usage
    - sudo apt-get install -y make build-essential libssl-dev zlib1g-dev libbz2-dev libreadline-dev
      libsqlite3-dev wget curl llvm libncurses5-dev libncursesw5-dev xz-utils tk-dev

    # Set up pyenv
    - git clone https://github.com/pyenv/pyenv.git ~/.pyenv
    - echo 'export PYENV_ROOT="$HOME/.pyenv"' >> ~/.bash_profile
    - echo 'export PATH="$PYENV_ROOT/bin:$PATH"' >> ~/.bash_profile
    - echo 'eval "$(pyenv init --path)"' >> ~/.bash_profile
    - echo 'eval "$(pyenv init -)"' >> ~/.bash_profile

    # Set up virtualenv
    - git clone https://github.com/yyuu/pyenv-virtualenv.git ~/.pyenv/plugins/pyenv-virtualenv
    - echo 'eval "$(pyenv virtualenv-init -)"' >> ~/.bash_profile
    - source ~/.bash_profile
    - pyenv versions


set virtual environment and install packages

Below requirements.txt is package list. You can type your packages if you want.

.travis.yml


...

    # Install python 3.6.1
    - pyenv install 3.6.1

    # Set up virtual environment (virtualenv name is undang in this case)
    - pyenv virtualenv 3.6.1 undang
    - pyenv activate undang
    - python -V

    # Install packages
    # Essential packages: Appium-Python-Client, pytest
    - pip install -r requirements.txt


3. Node.js Environment Setting

install node.js

You can check installation guide in here “[Ubuntu](EN) Install latest npm and nodejs by using ppa”

.travis.yml


...

    # Install node.js and npm
    - curl -sL https://deb.nodesource.com/setup_9.x | sudo -E bash -
    - sudo apt-get install nodejs
    - sudo apt-get install build-essential


install appium

.travis.yml


...

    # Add $JAVA_HOME/bin to PATH (for Appium executing)
    - PATH=$PATH:$JAVA_HOME/bin

    # Install appium and appium-doctor
    - npm install appium
    - npm install appium-doctor


4. Run Appium

.travis.yml


...

    # Run appium-doctor
    - "./node_modules/.bin/appium-doctor"

    # Run appium in background and logging to appium_log.txt file
    - "./node_modules/.bin/appium --log-level info > appium_log.txt &"


5. Run Emulator

.travis.yml


...


before_script:

    # Create emulator (emulator image version should be exist in previous android setting)
    - echo no | android create avd --force -n test -t android-22 --abi armeabi-v7a

    # Run emulator
    - emulator -avd test -no-skin -no-window &
    - android-wait-for-emulator
    - adb shell input keyevent 82 &


6. Build and Test

.travis.yml


script:
    - "./gradlew assemble" # Build
    - pytest # Test

after_script:
    - cat ./appium_log.txt # Check appium log


Final result of .travis.yml

.travis.yml

language: android
sudo: required
jdk: oraclejdk8
android:
    components:
        - tools
        - platform-tools
        - build-tools-26.0.2
        - android-26
        - android-22
        - android-24
        - extra-google-google_play_services
        - extra-google-m2repository
        - extra-android-m2repository
        - addon-google_apis-google-26
        - sys-img-armeabi-v7a-android-22
        - sys-img-armeabi-v7a-android-24
before_install:
    - sudo apt-get update
    - sudo apt-get install -y make build-essential libssl-dev zlib1g-dev libbz2-dev libreadline-dev
      libsqlite3-dev wget curl llvm libncurses5-dev libncursesw5-dev xz-utils tk-dev
    - git clone https://github.com/pyenv/pyenv.git ~/.pyenv
    - echo 'export PYENV_ROOT="$HOME/.pyenv"' >> ~/.bash_profile
    - echo 'export PATH="$PYENV_ROOT/bin:$PATH"' >> ~/.bash_profile
    - echo 'eval "$(pyenv init --path)"' >> ~/.bash_profile
    - echo 'eval "$(pyenv init -)"' >> ~/.bash_profile
    - git clone https://github.com/yyuu/pyenv-virtualenv.git ~/.pyenv/plugins/pyenv-virtualenv
    - echo 'eval "$(pyenv virtualenv-init -)"' >> ~/.bash_profile
    - source ~/.bash_profile
    - pyenv install 3.6.1
    - pyenv virtualenv 3.6.1 undang
    - pyenv activate undang
    - pip install -r requirements.txt
    - curl -sL https://deb.nodesource.com/setup_9.x | sudo -E bash -
    - sudo apt-get install nodejs
    - sudo apt-get install build-essential
    - PATH=$PATH:$JAVA_HOME/bin
    - npm install appium
    - npm install appium-doctor
    - "./node_modules/.bin/appium-doctor"
    - "./node_modules/.bin/appium --log-level info > appium_log.txt &"
before_script:
    - echo no | android create avd --force -n test -t android-22 --abi armeabi-v7a
    - emulator -avd test -no-skin -no-window &
    - android-wait-for-emulator
    - adb shell input keyevent 82 &
script:
    - "./gradlew assemble"
    - pytest
after_script:
    - cat ./appium_log.txt


Reference

TWpower Reading time ~2 minutes

업데이트(2018.04.19): C++ 정렬 코드 추가

Merge Sort를 구현해보자


환경

  • Python
  • C++


Merge Sort란?

원리

  • 현재 주어진 값들을 반으로 나누고 각각 나누어진 부분을 또 계속 나눈 후에 합치면서 정렬을 진행한다. 대표적인 분할정복의 예제

특징

  • Divide and Conquer이라는 분할정복 방법으로 정렬을 진행하며 자세한 부분은 다음을 참고하시면 좋습니다.
  • stable sort: 정렬 할 원소들이 튜플이나 레코드처럼 다른 원소들을 포함하고 있을 때 정렬 후에도 그 순서가 유지되는 정렬입니다.


복잡도

  • 시간복잡도: O(nlogn)
  • 공간복잡도: 이 코드에서는 O(n)이며 분할정복을 병렬로 진행하면 O(nlogn)


구현 코드(Python)


def merge_sort(A):
	if len(A) <= 1:
		return A

	# 분할 정복
	mid = int(len(A)/2)
	left_side = merge_sort(A[:mid])
	right_side = merge_sort(A[mid:])

	# left,right 각각을 위한 인덱스 l,r
	# 왼쪽과 오른쪽에서의 합병된 값을 저장할 A의 인덱스 k

	l = 0
	r = 0
	k = 0

	# 이제 왼쪽과 오른쪽을 비교하면서 merge
	while l < len(left_side) and r < len(right_side):
		if left_side[l] < right_side[r]:
			A[k] = left_side[l]
			k += 1
			l += 1
		else:
			A[k] = right_side[r]
			k += 1
			r += 1

	# 이제 남아 있는 경우만 더 확인

	# 오른쪽이 남아있다면
	while r < len(right_side):
		A[k] = right_side[r]
		r += 1
		k += 1

	# 왼쪽이 남아있다면
	while l < len(left_side):
		A[k] = left_side[l]
		l += 1
		k += 1

	return A


import random
A = [random.randint(0,100) for _ in range(0,10)]
print(A)
merge_sort(A)
print(A)


구현 코드(C++)

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <time.h>
#include <vector>

using namespace std;


void merge_sort(vector<int> &a, int left, int right) {

	if (left < right) {

		// 분할 정복
		int mid = left + (right - left) / 2;
		merge_sort(a, left, mid);
		merge_sort(a, mid + 1, right);

		//merge(a, left, mid, right);
		// i는 왼쪽, j는 오른쪽, k는 a를 채울 index
		int i, j, k;

		int left_side_size = mid - left + 1; // left ~ mid
		int right_side_size = right - mid; // mid+1 ~ right

		// 왼쪽과 오른쪽을 저장할 배열 1개씩 생성
		int * left_side = (int*)malloc(left_side_size * sizeof(int));
		int * right_side = (int*)malloc(right_side_size * sizeof(int));

		// 배열 채우고
		for (int l = 0; l < left_side_size; l++) {
			left_side[l] = a[left + l];
		}
		for (int r = 0; r < right_side_size; r++) {
			right_side[r] = a[mid + 1 + r];
		}

		// Merge
		// 이제 양 옆에서 하나씩 비교하면서 a에 추가
		i = j = 0;
		k = left;
		while (i < left_side_size && j < right_side_size) {

			if (left_side[i] <= right_side[j]) {
				a[k] = left_side[i];
				i++;
			}
			else {
				a[k] = right_side[j];
				j++;
			}
			k++;
		}

		// 오른쪽이 남아있다면
		while (j < right_side_size) {
			a[k] = right_side[j];
			j++;
			k++;
		}

		// 왼쪽이 남아있다면
		while (i < left_side_size) {
			a[k] = left_side[i];
			i++;
			k++;
		}
		free(left_side); free(right_side);
	}
}

int main() {

	vector<int> a(5);
	int len = a.size(); // 벡터길이

	// 랜덤함수를 위한 srand와 seed
	srand(time(NULL));

	// 벡터 초기화
	for (int i = 0; i < len; i++) {
		// 1 ~ 50까지의 난수 생성
		a[i] = rand() % 50 + 1;
	}

	// 정렬 전 출력
	for (int i = 0; i < len; i++) {
		cout << a[i] << ' ';
	}
	cout << '\n';

	// 합병정렬
	merge_sort(a, 0, len - 1);

	// 정렬 후 출력
	for (int i = 0; i < len; i++) {
		cout << a[i] << ' ';
	}
	cout << '\n';

	return 0;
}


참고자료

TWpower Reading time ~2 minutes

업데이트(2018.04.19): C++ 정렬 코드 추가

Quick Sort를 구현해보자


환경

  • Python
  • C++


Quick Sort란?

원리

  • pivot을 정하고 pivot보다 작은 값들을 pivot의 왼쪽 pivot보다 큰 값들은 pivot의 오른쪽으로 위치시키고 pivot의 왼쪽 값들과 오른쪽 값들을 각각 따로 또 재귀를 통해 분할정복한다.

특징

  • O(nlogn)의 성능을 보이는 정렬 알고리즘중에 하나로 최악에는 O(n^2)의 성능을 보이지만 일반적으로 빠른 성능을 나타내기에 보편적으로 많이 쓰는 알고리즘 입니다.
  • Divide and Conquer이라는 분할정복 방법으로 정렬을 진행하며 자세한 부분은 다음을 참고하시면 좋습니다.
  • in-place sorting: 정렬 할 원소들을 위한 추가적인 메모리를 사용하지 않고 현재 메모리에서 정렬을 진행


복잡도

  • 시간복잡도: 평균 O(nlogn), 최악 O(n^2)
  • 공간복잡도: O(logn)(in-place sorting의 경우!)


구현 코드(Python)

in-place sort

  • 메모리를 아낄 수 있다.
  • 하지만 코드가 조금 더 복잡하다.

def swap(A, i, j):
	tmp = A[i]
	A[i] = A[j]
	A[j] = tmp


def quick_sort(A, left, right):
	if left < right:
		p = partition(A, left, right)

		# p 기준으로 왼쪽 값들은 p보다 작고 오른쪽 값들은 p보다 큼
		quick_sort(A,left, p-1)
		quick_sort(A,p+1,right)



def partition(A, left, right):

	import random
	# 랜덤하게 pivot 생성
	pivot_index = random.randint(left, right)
	pivot_value = A[pivot_index]


	# 피벗값과 right의 값을 swap
	swap(A, pivot_index, right)

    # store_index를 기준으로
    # 왼쪽에 pivot_value보다 작은 값들 위치시킴
	store_index = left
	for i in range(left, right):
		if A[i] < pivot_value:
			swap(A, i, store_index)
			store_index += 1
	swap(A, right, store_index)
	return store_index


# 테스트 코드
import random

A = [random.randint(0,100) for _ in range(0,10)]
print(A)
quick_sort(A, 0, len(A)-1)
print(A)


not-in-place sort

  • 코드가 간결하다.
  • 하지만 추가적인 메모리를 사용한다.

def quick_sort(A):
	if(len(A)>1):
		import random
		pivot = A[random.randint(0, len(A)-1)]
		greater = [i for i in A if i > pivot]
		smaller = [i for i in A if i < pivot]
		middle = [i for i in A if i == pivot]
		return quick_sort(smaller) + middle + quick_sort(greater)
	else:
		return A

# 테스트 코드
import random

A = [random.randint(0,100) for _ in range(0,10)]
print(A)
A=quick_sort(A)
print(A)


구현 코드(C++)

in-place sort

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <time.h>

using namespace std;

void swap(int *a, int *b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int partition(int a[], int left, int right) {

	srand(time(NULL));
	// left ~ right 사이의 값을 랜덤으로 생성
	int pivot_index = rand() % (right + 1 - left) + left;
	int pivot_value = a[pivot_index];

	swap(&a[pivot_index], &a[right]);

	// store_index를 기준으로
	// 왼쪽에 pivot_value보다 작은 값들 위치시킴
	int store_index = left;
	for (int i = left; i < right; i++) {
		if (a[i] < pivot_value) {
			swap(&a[i], &a[store_index]);
			store_index += 1;
		}
	}

	swap(&a[store_index], &a[right]);

	return store_index;

}

void quick_sort(int a[], int left, int right) {

	if (left < right) {
		int p = partition(a, left, right);

		quick_sort(a, left, p - 1);
		quick_sort(a, p + 1, right);
	}
}

int main() {

	int a[5];
	int len = sizeof(a) / sizeof(int); // 배열길이

	// 랜덤함수를 위한 srand와 seed
	srand(time(NULL));

	// 배열 초기화
	for (int i = 0; i < len; i++) {
		// 1 ~ 50까지의 난수 생성
		a[i] = rand() % 50 + 1;
	}

	// 정렬 전 출력
	for (int i = 0; i < len; i++) {
		cout << a[i] << ' ';
	}
	cout << '\n';

	// 퀵정렬
	quick_sort(a, 0, len - 1);

	// 정렬 후 출력
	for (int i = 0; i < len; i++) {
		cout << a[i] << ' ';
	}
	cout << '\n';

	return 0;
}


참고자료