Python에서 리스트를 슬라이싱해서 이용하는 방법을 알아보자


환경 및 선수조건

  • Python(3.X)


파이썬 슬라이싱(slicing)이란?

  • 슬라이싱(slicing) or 슬라이스(slice) : 연속적인 객체들에(예 : 리스트, 튜플, 문자열) 범위를 지정해 선택해서 객체들을 가져오는 방법 및 표기법을 의미합니다.
  • 슬라이싱을 하면 새로운 객체를 생성하게 됩니다. 즉, 일부분을 복사해서 가져온다고 생각하면 됩니다.


기본 사용법과 형태


기본 형태

  • a라는 연속적인 객체들의 자료구조(예 : 리스트, 튜플, 문자열)가 있다고 가정을 했을 때 기본 형태는 아래와 같습니다.

a[start : end : step]

  • 각각 start, end, step 모두 양수와 음수를 가질 수 있습니다.
  • start : 슬라이싱을 시작할 시작위치입니다.
  • end : 슬라이싱을 끝낼 위치로 end는 포함하지 않습니다!
  • step : stride라고도 하며 몇개씩 끊어서 가져올지를 정합니다. (옵션)


인덱스 값들의 위치

  • 위에 설명한 대로 값들을 양수 혹은 음수를 가질 수 있습니다.
  • 양수 : 연속적인 객체들의 제일 앞에서부터 0을 시작으로 번호를 매깁니다.
  • 음수 : 연속적인 객체들의 제일 뒤에서부터 -1을 시작으로 번호를 매깁니다.
  • 아래는 ['a', 'b', 'c', 'd', 'e']라는 리스트가 있을 때 인덱스를 의미합니다.
a = ['a', 'b', 'c', 'd', 'e']

// Index References
-------------------------------
|  a  |  b  |  c  |  d  |  e  |
-------------------------------
|  0  |  1  |  2  |  3  |  4  |          // 양수의 경우
-------------------------------
| -5  | -4  | -3  | -2  | -1  |          // 음수의 경우
-------------------------------


예제

  • 기본적으로 모든 예제들은 a = ['a', 'b', 'c', 'd', 'e']의 리스트를 통해서 작성하겠습니다.


특정 시작위치부터 끝까지 가져오기

  • a[ start : ]

>>> a = ['a', 'b', 'c', 'd', 'e']
>>> a[ 1 :  ]
['b', 'c', 'd', 'e']


>>> a = ['a', 'b', 'c', 'd', 'e']
>>> a[ -3 :  ]
['c', 'd', 'e']


시작점부터 특정 위치까지 모두 가져오기

  • a[ : end ]

>>> a = ['a', 'b', 'c', 'd', 'e']
>>> a[  : 2 ]
['a', 'b']


>>> a = ['a', 'b', 'c', 'd', 'e']
>>> a[  : -1 ]
['a', 'b', 'c', 'd']


특정 위치부터 특정 위치까지 모두 가져오기

  • a[ start : end ]

>>> a = ['a', 'b', 'c', 'd', 'e']
>>> a[ 2 : 4 ]
['c', 'd']


>>> a = ['a', 'b', 'c', 'd', 'e']
>>> a[ -4 : -2 ]
['b', 'c']


>>> a = ['a', 'b', 'c', 'd', 'e']
# 인덱스 1 ~ 3까지를 거꾸로 가져오기
>>> a[ 3 : 0 : -1]
['d', 'c', 'b']


step의 예제

  • a[ start : end : step ]
  • step이 양수일 때 : 오른쪽으로 step만큼 이동하면서 가져옵니다.
  • step이 음수일 때 : 왼쪽으로 step만큼 이동하면서 가져옵니다.

>>> a = ['a', 'b', 'c', 'd', 'e']
# 2칸씩 이동하면서 가져옵니다.
>>> a[ : : 2 ]
['a', 'c', 'e']


>>> a = ['a', 'b', 'c', 'd', 'e']
# 3칸씩 이동하면서 가져옵니다.
>>> a[ -5 : : 3 ]
['a', 'd']


>>> a = ['a', 'b', 'c', 'd', 'e']
# 전체를 거꾸로 가져옵니다.
>>> a[ : : -1 ]
['e', 'd', 'c', 'b', 'a']


>>> a = ['a', 'b', 'c', 'd', 'e']
>>> a[ 3 : : -1 ]
['d', 'c', 'b', 'a']


참고자료

Python에서 리스트에 있는 튜플이나 만든 클래스를 통해서 생성한 객체를 정렬하는 방법을 알아보자.


환경 및 선수조건

  • Python(3.X)


sort()함수와 sorted()함수

  • Python에서 제공하는 정렬함수는 기본적으로 stable을 보장한다. (관련문서)


sort()

  • sort() : 현재 리스트를 정렬

a = [3,5,7,8,2,6]
a.sort()

sorted()

  • sorted() : 함수의 인자로 들어온 리스트를 정렬해서 반환

a = [3,5,7,8,2,6]
b = sorted(a) # b에 정렬된 리스트가 새로 생성됨


key 매개변수 이용하기

  • key매개변수를 이용하여 비교하기전에 함수를 정의 할 수 있다.
  • key매개변수는 하나의 인자를 갖는 함수여야하며 정렬에 사용할 key를 반환해야한다.


튜플(tuple)을 사용하는 경우


example_tuples = [ ('A', 3, 'a'), ('B', 1, 'b'), ('C', 2, 'c') ]

# 정렬
example_tuples.sort(key = lambda element : element[1])


객체(Object)를 사용하는 경우


class Example:
	def __init__(self, big, number, small):
		self.big = big
		self.number = number
		self.small = small

example_objects = [ Example('A', 3, 'a'), Example('B', 1, 'b'), Example('C', 2, 'c') ]

# 정렬
example_objects.sort(key = lambda object : object.number)


정렬 관련 기타

내림차순 정렬

  • sort( reverse=True ) : 현재 리스트를 내림차순으로 정렬

a = [3,5,7,8,2,6]
a.sort(reverse=True)


참고자료

Python에서 is와 ==의 차이를 알아보자


환경 및 선수조건

  • Python


is와 ==의 차이

  • is는 변수가 같은 Object(객체)를 가리키면 True
  • ==는 변수가 같은 Value(값)을 가지면 True


‘is’의 예시

  • a와 b는 같은 리스트 객체를 가리킨다.
  • a와 b는 같은 객체이기 때문에 True
  • a와 c는 값은 같지만 다른 객체이기 때문에 False

>>> a = [1,2,3]
>>> b = a
>>> c = [1,2,3]
>>> a is b
True
>>> a is c
False

is

’==’의 예시

  • a와 b는 같은 리스트 객체를 가리킨다.
  • a와 b는 값들을 가진 리스트이기 때문에 True
  • a와 c는 값들을 가진 리스트이기 때문에 True

>>> a = [1,2,3]
>>> b = a
>>> c = [1,2,3]
>>> a == b
True
>>> a == c
True

double-equal


참고자료

해시 테이블에서 문자열을 받았을 때 해싱하는 방법을 알아보자


환경 및 선수조건


String을 Key값으로 받았을 때

  • 1번의 방식은 단순하나 중복이 될 가능성이 크며 2~3번의 방식이 분포를 더 크게 만들 수 있다.
  • 만약 연산중에 혹은 결과 값이 해시 테이블의 크기보다 크다면 해시 테이블의 크기만큼 나누어서 나머지의 값을 취하면 된다.


1. 문자열에 있는 문자들을 모두 더하기

  • 문자열에 있는 문자들을 다 더해서 계산하는 방식
  • 단, 아래와 같은 경우에는 “abc”, “acb” 그리고 “cba”의 결과가 모두 같다는 단점이 있다. 즉 hashCode("abc")==hashCode("acb")==hashCode("cba")

int hashCode(String s){
	int r = 0;

	for(int i = 0; i < s.length(); i++){             
		 r += s[i];
	}

	return r;
}


2. 다항식을 이용해서 구하기

  • h(s) = xk-1 × ak-1 + xk-2 × ak-2 + ... + x0 × a0와 같은 다항식을 바탕으로 만드는 방식
  • 특정한 값 a(일반적으로 소수가 좋다고 한다.)를 곱하고 문자열에 있는 문자를 더하면서 완성해가는 방식

int hashCode(String s){
	int i;
	int r = 0;

	// Special Prime Number
	int a = 33;

	for(i = 0; i < s.length(); i++){
		 r += r*a + s[i];   
	}

	return r;
}


3. 시프트(Shift) 연산자를 이용해서 구하기

  • 위에 2번에 있는 다항식의 방법과 똑같은데 시프트(Shift)연산을 이용해서 값을 곱하는 방식

int hashCode(String s){
	int i;
	int r = 0;

	for(i = 0; i < s.length(); i++){
		 r += (r<<4) + s[i];   
	}

	return r;
}


참고자료

집합을 표현할 때 사용하는 유니온 파인드(Union Find)와 서로소 집합(Disjoint Set)에 대해서 알아보자

해당 내용은 코드플러스 알고리즘 중급 강의의 내용을 기본으로 작성하였습니다.


환경 및 선수조건

  • C++


유니온 파인드(Union Find)란?

정의

  • 유니온 파인드(Union Find) : 서로소 집합(Disjoint Set) 그리고 병합 찾기 집합(Merge Find Set)이라고도 불리며 여러 서로소 집합의 정보를 저장하고 있는 자료구조를 의미합니다.

예시

  • 다음 아래와 같이 원소들이 있다고 가정을 했을 때


  • 각각의 원소들이 어떤 원소들과 연결이 되어있는지 입력을 받는다고 가정하면(1-2, 2-5, 5-6, 5-8, 3-4 이런 방식으로) 아래와 같이 3개의 서로소 집합이 나올 수 있다.


구현

원리

  • 배열을 이용해서 Tree 자료구조를 만들어 구현하며 위에 나와 있는 {1, 2, 5, 6, 8}, {3, 4}, {7}의 경우에는 아래처럼 표현 및 구현이 가능합니다.
  • 즉, 최상단 노드인 Root노드를 집합을 구분하는 ID처럼 생각하면 이해가 더 편합니다.

Tree

  • 주어진 두 원소 또는 집합을 합하는 Union부분과 원소가 어떤 집합에 있는지 찾는 Find함수로 이루어져있다.
  • parent[i] : 원소 i의 부모 노드를 가지고 있는 배열, parent[i]i의 부모 노드

초기화

  • 처음에 각각의 원소들은 연결된 정보가 없기 때문에 부모로 자기 자신을 가지고 있다.
  • 즉, parent[i] = i;

for(int i=1; i<=n; i++){
    parent[i] = i;
}

Find 함수

  • Find(x) 함수 : x로 들어온 원소의 Root노드를 반환

int Find(int x){

    // Root인 경우 x를 반환
    if(x == parent[x]){
        return x;
    }
    else{
        // 아니면 Root를 찾아감
        int p = Find(parent[x]);
        parent[x] = p;
        return p;
    }

}

Union 함수

  • Union(x,y) 함수 : x원소와 y원소를 합치는 함수로 y의 Root노드를 x로 한다.

// x와 y의 원소가 들어오면
// 각각 x에는 들어온 x의 Root 노드 y에는 들어온 y의 Root 노드를 저장해서 비교하고
// x에 y를 붙이는 방식 -> y의 Root 노드를 x로 설정

void Union(int x, int y){

    x = Find(x);
    y = Find(y);

    if(x!=y){
        parent[y] = x;
    }
}


관련 문제 및 예제


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

using namespace std;

int parent[1000001];

int Find(int x){

	if(x == parent[x]){
		return x;
	}
	else{
		int y = Find(parent[x]);
		parent[x] = y;
		return y;
	}

}

void Union(int x, int y){

	x = Find(x);
	y = Find(y);

	parent[y] = x;

}

int main(){

	int n,m;

	scanf("%d %d", &n, &m);

	// 배열 생성 및 초기화
	// 처음에는 자기 자신이 부모이다 -> 모두 떨어져있기 때문
	for(int i=0; i<=n; i++){
		parent[i] = i;
	}

	int op, a, b;
	while(m--){
		scanf("%d %d %d", &op, &a, &b);

		if(op == 0){
			Union(a,b);
		}

		else if(op == 1){
			int a_parent = Find(a);
			int b_parent = Find(b);

			if(a_parent == b_parent){
				printf("YES\n");
			}
			else{
				printf("NO\n");
			}
		}
	}
	return 0;
}


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

using namespace std;

int computers;
int connections;

int parent[101];

int Find(int x){

	if(x == parent[x]){
		return x;
	}
	else{
		int y = Find(parent[x]);
		parent[x] = y;
		return y;
	}

}

void Union(int x, int y){

	x = Find(x);
	y = Find(y);

	if(x!=y){
		parent[y] = x;
	}


}

int main() {

	scanf("%d", &computers);
	scanf("%d", &connections);

	// 초기화
	// 처음에는 각각 노드가 부모노드가 자기자신
	for(int i=0; i<=computers; i++){
		parent[i] = i;
	}

	int u,v;
	while(connections--){
		scanf("%d %d", &u, &v);

		Union(u,v);
	}

	// Root 노드가 1인 노드를 검색해서 cnt에 더해줌
	int cnt = 0;
	for(int i=2; i<=computers; i++){
		if(Find(1) == Find(i)) cnt++;
	}

	printf("%d\n", cnt);

	return 0;
}


참고자료

  • 코드플러스 알고리즘 중급 강의