비트와 바이트

컴퓨터는 정보를 표현하기 위해 전기 신호를 주고받으며 의사소통을 한다.
전기 신호가 있으면 1, 없으면 0, 이때 0 혹은 1의 값이 데이터의 최소 단위가 되고 이를 비트(bit) 라고 표현한다.
따라서 컴퓨터에 저장된 데이터는 0 혹은 1 2진수로 표현되는 것이다.
하지만 이 비트(bit)만 가지고서는 2가지 밖에 표현하지 못하기 때문에 다른 저장 단위가 필요하게 된다.

그래서 연속된 8bit를 묶어 더 많은 값을 표현할 수 있는 바이트(byte)가 등장하게 된다.
1byte는 컴퓨터의 최소 저장 단위로서8bit를 의미한다. 00101100과 같은 방식으로 총 2^8가지 즉 256가지의 정보를 표현 가능하다.

아스키코드 (ASCII)

아스키코드는 우리가 사용하는 인간의 언어와 컴퓨터가 사용하는 언어를 매칭시킨 규칙이라고 할 수 있다. 예를 들어 A는 1000001 B는 1000010 과 같이 표현하겠다고 약속한 것이다. 이때 아스키코드는 1바이트의 데이터로 표현 가능하다.

그런데 표를 자세히 보면 1바이트 즉 8비트로 표현되는 것이 아니라 7비트만 사용되는 것처럼 보인다.
이는 패리티 비트라는 것 때문인데, 간단히 말하면 데이터의 에러를 감지하기 위해 사용되는 비트이다. (링크 : 패리티 비트란 무엇인가)

결국 이를 제외하면 아스키코드는 7비트로 표현가능하기 때문에 총 2^7개인 128개의 문자를 표현할 수 있다.
하지만 128가지로 영어는 모두 표현 가능 했지만, 전 세계의 다양한 문자를 표현하기는 부족했다.

EUC (Extended Unix code)

멀티 바이트를 사용해 한, 중, 일 등의 다양한 언어를 표현하기 위한 인코딩 방식이다.
EUC-KR, EUC-JP, EUC-CN 등 다양한 언어를 표현하기 위해 사용되었지만 한계가 있었다.

EUC-KR로 인코딩한 페이지에 한국어와 일본어가 동시에 있다면? 일본어가 깨져버린다. 반대도 마찬가지.
또한 이모티콘도 표현할 수 없었기 때문에 다른 대안이 필요했다.

유니코드

따라서 전 세계 언어의 문자를 정의하기 위한 국제 표준인 유니코드가 등장하게 되었다. (현재까지 약 14만개 문자, 약 2^18비트 필요)

그러나 유니코드 또한 단점이 있는데, 모든 문자를 표현할 수 있지만 메모리 낭비가 너무 심했다. 간단한 문자를 표현하는데도 4바이트씩 필요하게 된 것이다.

간단한 영어는 아스키코드를 사용해 효율적으로 읽고, 다른 언어는 유니코드로 사용하고 싶어서 등장한 것이 대표적으로 UTF-8등의 인코딩 방식들이다.

UTF-8 (8-bit Unicode Transformation Format)

다양한 유니코드 인코딩 방식 중 우리에게 익숙한 UTF-8 방식을 살펴보자.
UTF-8은 이름에서도 알 수 있듯이 문자열 집합과 인코딩 형태를 8bit 단위로 한다는 의미를 가지고 있다.

메모리를 효율적으로 사용하기 위해서 문자 하나당 1byte ~ 4byte까지 사용한다.

그렇다면 어떤 문자를 어떤 바이트로 읽을지 어떻게 알 수 있을까?

그것은 첫번째 바이트를 보고 판단할 수 있다.

위 표에 xxx 부분이 실제 문자를 나타내기 위한 비트값이 들어가는 부분이다. 예시를 보자면 다음과 같은 형태로 문자를 읽어들이는 것이다.

아스키 코드와도 완벽히 호환되고 UTF-16, UTF-32에서 발생하는 엔디언 문제도 없기 때문에 현재 모든 웹페이지의 93%가 UTF-8을 사용하고 있다.

엔디안 문제 : 1바이트를 초과하는 데이터를 저장할 때 메모리에 어떤 순서로 저장할 것이냐

01. 배열과 문자열

문제 1.5

하나 빼기 : 문자열을 편집하는 방법에는 세 가지 종류가 있다. 문자 삽입, 문자 삭제, 문자 교체. 문자열 두 개가 주어졌을 때, 문자열을 같게 만들기 위한 편집 횟수가 1회 이내인지 확인하는 함수를 작성하라.

풀어보기

문자열의 등장 횟수를 비교하는 방식으로 접근했지만, 생각해보니 그렇게 되면 등장횟수는 같은데 배열이 다른 문자열들을 고려할 수 없기 때문에 다른 방식으로 접근 해야한다.

1. 문자열의 길이를 비교하고, 각 케이스 별로 문자열을 순회하면서 비교하며 판단한다.

먼저 각 문자열의 길이를 비교한다.

두 문자열의 길이 차이가 2이상이면 1회의 편집으로는 절대 같아질 수 없다.

두 문자열의 길이 차이가 1이거나 0이면 서로 다른 문자가 1개만 존재해야한다.

길이가 1차이 나는 경우과 길이가 같은 경우를 나눠서 생각한다.

길이가 같은 경우는 문자열을 하나씩 순회하면서 같은 인덱스의 값을 비교하고 서로 다른 문자열의 개수를 센다.

길이가 1차이 나는 경우는 문자열을 하나씩 순회하면서 같은 인덱스의 값을 비교하고 서로 다른 문자열이 나왔을 경우

길이가 짧은 문자열의 i번째 문자와 길이가 긴 문자열의 i+1번째 문자열의 값을 비교한다. 이때 또 한번 다른 문자열이 등장하면 편집횟수가 1이상이다.

# 1.5 하나 빼기

from collections import Counter

s1 = "zale"
s2 = "plze"

def solution(s1, s2):
    longer = ""
    shorter = ""

    if len(s1) == len(s2):
        pass
    else:
        if len(s1) - len(s2) > 0:
            longer, shorter = s1, s2
        elif len(s1) - len(s2) < 0:
            longer, shorter = s2, s1

    if len(longer) - len(shorter) >= 2:
        return False
    else:
        cnt = 0
        if len(longer) == 0:
            for i in range(len(s1)):
                if s1[i] != s2[i]:
                    cnt += 1
                if cnt >=2:
                    return False
        else:

            for i in range(len(shorter)):
                if cnt == 1:
                    if longer[i+1] != shorter[i]:
                        print(longer[i+1], shorter[i])
                        return False

                if longer[i] != shorter[i]:
                    cnt += 1


    return True


solution("pale", "bake")

해답

1. 삽입과 삭제를 하나로 합치고, 교체연산을 확인한다.

한번의 교체연산으로 같게 만들 수 있다는 의미는 두 문자열이 하나의 문자열만 다르고 모두 같다는 것을 의미한다. 삽입 혹은 삭제 연산으로 같게 만들 수 있다는 의미는 짧은 문자열 특정 위치에 공백을 포함하면 나머지 문자들은 모두 같다는 것을 의미한다. 이 중 어떤 연산을 사용할 것인지는 두 문자열의 길이를 보고 판단 할 수 있다.

두 문자열의 길이가 같다면 교체 연산, 두 문자열의 길이가 다르면 삽입 혹은 삭제 연산을 통해 다른 문자가 몇번 등장하는지 확인한다.

01. 배열과 문자열

문제 1.4

회문 순열 : 주어진 문자열이 회문의 순열인지 아닌지 확인하는 함수를 작성하라. 회문이란 앞으로 읽으나 뒤로 읽으나 같은 단어 혹은 구절을 의미하며, 순열이란 문자열을 재배치하는 것을 뜻한다. 회문이 꼭 사전에 등장하는 단어로 제한될 필요는 없다.

풀어보기

1. 각 문자의 등장 횟수를 구하고 홀수 번 반복되는 문자가 2개 이상이면 회문이 아니라고 판단한다.

문제를 다시 쉽게 해석해보면 예를 들어 "토토마" 라는 문자가 주어졌을 때 이를 재배치 하여 "토마토" 라는 회문을 만들 수 있는지 없는지 확인하는 문제이다.

먼저 대문자와 소문자를 구별할 것인지, 공백은 무시할 것인지 아니면 하나의 문자로 볼 것인지 확인하는 것이 좋아보인다. 일단 대소문자와 공백을 무시한다고 가정하고 문제를 풀어보자.

회문의 특징은 문자열의 등장 횟수를 count했을 때 홀수번 반복되는 문자가 1개 이거나 혹은 0개 이어야 한다.

# 1.4 회문순열
from collections import Counter

s = "Tact Coab"

def solution(s):
    s = s.lower() # 소문자로 치환
    s = s.replace(" ", "") # 공백제거
    s_list = list(s)
    odd_cnt = 0

    counter = Counter(s_list)

    for x in counter:
        if counter[x] % 2 != 0:
            odd_cnt += 1
    if odd_cnt > 1:
        return False
    else:
        return True
solution(s)

# -결과----------------------------------------------------------------------------------
# False

해답

1. 각 문자가 몇 번 등장했는지 세고, 홀수 번 등장한 문자가 한 개 이상인지 확인한다.

한 번 순회하며 각 문자열의 등장 횟수를 세고, 이후 각 문자마다 몇번 등장 했는지 확인하며 홀수 번 등장한 문자가 몇개인지 확인한다.

O(N)의 시간 복잡도가 소요 된다. 충분히 좋은 알고리즘 이지만 최선의 방향을 찾는 노력은 중요하다. 좀 더 개선할 수 있는 방법을 생각해보자.

같은 아이디어 이지만 내 풀이는 홀수개의 문자열이 몇 개인지 다 센후 검증하지만, 우리는 2개 이상인지만 확인하면 되기 때문에 홀수 개 문자열이 2개 이상 등장하는 순간 바로 프로그램을 종료할 수 있다.

// 회문순열인지 판단하는 함수
boolean isPermutationOfPalindrome(String phrase){
    int [] table = buildCharFrequencyTable(phrase);
    return checkMaxOneOdd(table);
}

boolean checkMaxOneOdd(int[] table){
    boolean foundOdd = false;
    for (int count : table){
        if (count % 2 == 1){
            if (foundOdd) {
                return false; // 홀수개 문자가 2개 이상 나오는 순간 false
            }
            foundOdd = true;
        }
    }
    return true ;
}

// 문자에 해당하는 숫자를 리턴한다. a=1, b=2 ...
int getCharNumber(Character c){
    int a = Character.getNumericValue('a');
    int z = Character.getNumericValue('z');
    int val = Character.getNumericValue(c);

    if (a <= val && val <= z){
        return val - a;
    }
    return -1;
}


// 각 문자가 몇 번씩 등장하는지 기록하여 저장하는 함수
int [] buildCharFrequencyTable(String phrase){
    int [] table = new int[Character.getNumericValue('z') - Character.getNumericValue('a') + 1]; // a~z 길이만큼 배열 생성

    for (char c : phrase.toCharArray()){
        int x = getCharNumber(c);
        if (x != -1){
            table[x]++;
        }
    }
    return table
}

2. 1번과 같지만, 홀수 개 인지 여부를 문자열을 순회하면서 동시에 확인한다.

루프를 2번에서 1번으로 줄일 수 있다. 그러나 각 문자마다 수행되는 코드가 더 많아져 성능이 향상되었다고 얘기할 수는 없다.

3. 등장 횟수를 세지 않고, 문자열이 등장할 때마다 해당 위치의 비트값을 바꿔주며 홀수, 짝수 여부를 판단한다.

시간 복잡도는 O(N)으로 똑같다. 그러나 정수 하나만 가지고 확인할 수 있기 때문에 메모리는 확실히 효율적이다.!

boolean isPermutationOfPalindrome(String phrase){
    int bitVector = createBitVector(phrase);

}

int createBitVector(String phrase){
    int bitVector = 0;
    for (char c : phrase.toCharArray()){
        int x = getCharNumber(c);
        bitVector = toggle(bitVector, x);
    }
}

// 정수의 i번째 비트값을 바꾼다.
int toggle(int bitVector, int index){
    if (index < 0 ) return bitVector;

    int mask = 1 << index;
    if ((bitVector * mask) == 0){
        bitVector |= mask;
    }else{
        bitVector &= ~mask;
    }
    return bitVector;
}

boolean checkExactlyOneBitSet(int bitVector){
    return (bitVector & (bitVector - 1)) == 0;
}

비트벡터 개념과 비트연산자 문법 정리..!

01. 배열과 문자열

문제 1.3

URL화 : 문자열에 들어 있는 모든 공백을 '%20'으로 바꿔 주는 메서드를 작성하라. 최종적으로 모든 문자를 다 담을 수 있을 만큼 충분한 공간이 이미 확보되어 있으며 문자열의 최종 길이가 함께 주어진다고 가정해도 된다.

풀어보기

1. 문자열 순회하면서 이어붙이기

단순하게 문자열을 하나씩 확인하며 공백일 때는 '%20', 공백이 아닐 때는 기존 문자열을 덧붙여서 새로운 결과 문자열을 만들어 리턴한다.

# 1.3 URL화
s = "Mr John Smith"

def toURL(str):
    newS = ""
    for x in s:
        if x == ' ':
            newS += "%20"
        else:
            newS += x
    return newS

print(toURL(s))

# -결과----------------------------------------------------------------------------------
# Mr%20John%20Smith

수정된 풀이(하나의 문자열로 편집하여 리턴)

# 1.3 URL화
s = "Mr John Smith"

def toURL(str):
    n = len(str)

    # 마지막 부터 첫번째까지 순회
    for i in range(len(str)-1, 0-1, -1):
        if str[i] == ' ':
            str = str[:i] + "%20" + str[i+1:]

    return str

print(toURL(s))
# -결과----------------------------------------------------------------------------------
# Mr%20John%20Smith

해답

문제에 정확히 나오지 않았지만 주의해야할 사항은 이 문제는 새로운 문자열을 만들어 변환 하는 것이 아니라, 기존의 문자열을 가지고 조작하여 풀어야 하는 문제!

따라서 문자열을 앞에서 부터 편집하는 것이 아니라, 뒤에서 부터 편집한다. 앞에서 부터 편집하면 아직 편집해야 할 문자가 덮어쓰여질 우려가 있기 때문이다.

1. 공백의 갯수를 세고, 문자열을 뒤에서부터 거꾸로 편집하며 복사해나간다. 

void replaceSpaces(char [] str, int trueLength){    // truelength는 주어진 문자열의 길이
    int spaceCount = 0, index, i = 0;
    for (i = 0; i < trueLength; i++){
        if (srt[i] == ' '){
            spaceCount++;        // 공백의 숫자를 센다
        }
    }

    index = trueLength + spaceCount * 2; // 문자열의 길이에다가 URL화로 인해 치환될 문자열의 길이를 더한 값이 index

    if (trueLength < str.length){ // 만약 주어진 문자열의 길이가 실제 문자열의 길이보다 작다면 중간에 종료
        str[trueLength] = '\0'
    }
    // str[trueLength] -> str[index] 로 문자열 복사
    for (i = trueLength - 1; i>=0; i--){
        if (str[i] == ' '){
            str[index - 1] == '0';
            str[index - 2] == '2';
            str[index - 3] == '%';
            index = index-3;
        }
        else{
            str[index - 1] = str[i];
            Index--;
        }
    }
}

01. 배열과 문자열

문제 1.2

순열 확인 : 문자열 두 개가 주어졌을 떄 이 둘이 서로 순열 관계에 있는지 확인하는 메서드를 작성하라.

풀어보기

순열 관계라는 것은 두 문자열에서 사용된 문자는 같은데 문자의 순서만 다른 형태라는 것을 의미한다.

1. 정렬 후 리스트 비교

먼저 두 문자열의 길이가 같은지 확인한다. 길이가 다르면 순열 관계가 아니라고 판단한다.

길이가 같다면 두 문자열을 정렬하여 두 개의 리스트가 같은지 비교연산자를 통해 비교한다.

# 1.2 순열 확인

def istnsduf(str1, str2):
    if len(str1) == len(str2):

        listStr1 = list(str1)
        listStr2 = list(str2)
        listStr1.sort()
        listStr2.sort()

        if listStr1 == listStr2:
            return True
    return False

print('ABC', 'AER', istnsduf('ABC', 'AER'))
print('CBS', 'SCB', istnsduf('CBS', 'SCB'))

# -결과----------------------------------------------------------------------------------
# ABC AER False
# CBS SCB True

모법답안

먼저 확인 해야 할 사항은. 대소문자는 구별할 것인지? 그리고 공백은 어떻게 볼 것인지?

여기서는 대소문자를 구별하고 공백을 하나의 문자열로 판단하기로 한다.

1. 정렬하여 비교하기

순열 관계의 문자열은 정렬하면 같은 문자열이 되기 때문에 정렬 후 두 문자열을 비교해주면 된다. 단순하고 이해하기 쉽다는 측면에서 좋은 풀이이지만, 효율성 측면에서는 최적은 아니다.

2. 문자열에 포함된 문자의 출현 횟수가 같은지 비교

순열 관계의 문자열은 동일한 문자가 동일한 횟수로 출현한다는 특징이 있다. 이를 각각 문자열에서 기록하고 이 횟수를 비교한다

1번 풀이는 O(NlogN) 의 시간 복잡도, 2번 풀이는 O(N)의 시간 복잡도가 걸릴 것 같다!

패리티 비트(parity bit)란 정보의 전달 과정에서 오류 발생 여부를 검사하기 위해 추가된 비트이다. 전송하고자 하는 데이터의 끝에 1비트를 더하여 송수신 하는 방식으로 사용한다.

패리티 비트의 종류는 전송하고자 하는 데이터에 포함된 1의 개수에 따라서 짝수 패리티와 홀수 패리티, 2가지가 있다.

예를 들어 ASCII코드 A 를 나타내는 1000001 을 전송하고자 할 때,

홀수 패리티를 사용한다면 1000001 + 1 (1의 개수가 총 3개로 홀수를 맞춰 준다)

짝수 패리티를 사용한다면 1000001 + 0 (1의 개수가 총 2개로 짝수를 맞춰 준다)

송신 호스트는 다음과 같은 방식으로 데이터를 전송한다. 이때 수신 호스트도 7비트까지의 데이터를 보고 패리티 검사 방식(짝수, 홀수)에 따라 패리티 비트를 계산한 결과와 실제 받은 데이터 값을 비교하고 값이 같다면 오류가 없다고 판단하고, 값이 다르다면 오류가 있다고 판단하는 방식이다. 이렇게 오류가 있는 데이터를 받았을 경우에는 송신 측에 다시 데이터를 요청하는 방식으로 안정적인 통신을 할 수 있게 해주는 장치이다.

패리티 비트의 한계점

하지만 패리티 비트는 오류를 검사만 할 수 있을 뿐, 수정하지 못한다는 한계점을 가지고 있다. 그리고 만약 두 개의 비트가 오류 전송 될 경우 데이터는 서로 다르지만 같은 패리티 비트를 가지기 때문에 이 때는 오류를 제대로 검사할 수 없다. 즉 오류 비트가 홀수 개일 경우에만 오류를 검사할 수 있다는 한계점이 있다.

병렬 패리티

이런 한계점을 보완하기 위해 패리티를 가로 세로로 구성되는 데이터 블록에 적용하여 에러 위치를 찾아 정정할 수 있도록 만든 것이 병렬 패리티이다.

병렬 패리티는 아래 표에서와 같이 각각의 가로 1바이트에 대해 패리티를 만들고 각각의 세로 1바이트에 대해 패리티를 구성하여 블록 단위로 전송하면 가로와 세로에 대해 각각 패리티를 검사함으로써 에러를 찾아내고 정정할 수 있다.

전송된 데이터 블록 중에서 한 비트의 에러가 발생하면 가로와 세로 패리티의 특정 부분에 패리티가 맞지 않게 되며 아래 표에서와 같이 두 부분이 마주치는 곳에서 에러가 발생함을 알 수 있음에 따라 이를 정정할 수 있다.

01. 배열과 문자열

문제 1.1

중복이 없는가 : 문자열이 주어졌을 때, 이 문자열에 같은 문자가 중복되어 등장하는지 확인하는 알고리즘을 작성하라. 자료구조를 추가로 사용하지 않고 풀 수 있는 알고리즘 또한 고민하라.

풀어보기

1. 집합(SET) 자료형을 사용한다.

집합 자료형의 특성은 중복을 허용하지 않는다. 따라서 주어진 문자열을 집합 자료형으로 변환하여 최초 문자열의 길이와 변환된 집합 자료형의 길이를 비교한다. 길이가 늘어나는 것은 불가능하고 길이가 같다면, 중복이 없는 것이고 길이가 줄어들었다면 중복된 문자열이 제거된 만큼 길이가 줄어든 것이므로 중복된 문자열이 등장한 것이다.

# python
str = 'absas'    # 문자열 선언
def isUniqueChar(str):    # 중복된 문자열이 있으면 False, 중복되지 않고 유니크하다면 True
    str_set = set(str)    # 문자열을 집합 자료형으로 변환
    if len(str) == len(str_set):
        return True
    else:
        return False

print('naver', isUniqueChar('naver'))
print('kakao', isUniqueChar('kakao'))

# ----------------------결과--------------------------------------------------------------
# naver True
# kakao False

2. 각 문자를 순차적으로 다른 문자들과 비교한다.

문자열의 0번째 문자를 1부터 n번째 문자열과 순차적으로 비교한다. 그리고 1번째 문자를 2부터 n번째 문자열과 비교한다. 이런식으로 (n-1)~n번째 까지 반복하여 같은 문자열이 나오는 즉시 중복이 있는 문자열로 판단한다. 시간 복잡도는 O(N^2). 문제에서 요구한 자료구조를 추가로 사용하지 않고 풀 수 있는 알고리즘

# python
def isUniqueChar(str):     # 중복된 문자열이 있으면 False, 중복되지 않고 유니크하다면 True
    for i in range(len(str)):
        if str[i] in str[i+1:]:    # 중복된 것 있는지 확인
            return False
    return True
print('naver', isUniqueChar('naver'))
print('kakao', isUniqueChar('kakao'))

# ---------------------결과--------------------------------------------------------------
# naver True
# kakao False

모법답안

먼저 문자열이 ASCII 문자열인지 유니코드 문자열인지 확인 하는 센스. 이에 따라 저장 공간 크기가 달라질 수 있다. 일단 문자열이 아스키 코드 라고 가정했을 때 풀이. 아스키코드와 유니코드 이해

1. 표현 가능한 범위만큼 배열을 선언하여 배열의 인덱스에 접근하는 횟수를 통해 중복을 판단한다.

코드의 시간 복잡도는 O(N). N은 문자열의 길이. 하지만 아스키 코드가 표현 가능한 갯수를 초과하여 순회하지 않기 때문에 O(1)이라고 볼 수도 있다.

boolean isUniqueChars(String str) {
    if (str.length() > 128)
    {
        return false;    // 아스키 코드 문자의 개수 128. 이를 넘어가면 반드시 중복이 발생한다.
    }
    boolean[] char_set = new boolean[128];    // 128길이의 배열 선언

    for(int i = 0; i < str.length(); i++)    // 문자열의 길이만큼 반복
    {
        int val = str.charAt(i);    // i번째 문자열의 아스키 코드 값을 val변수에 저장
        if (char_set[val] == true)
        {
            return false;    // 현재 문자열과 같은 아스키코드를 가진 문자가 이미 존재했었다.
        }
    }
    return true;    // 겹친 것이 하나도 없다면 
    }

2. 비트벡터를 사용

비트벡터를 사용하여 문자열 중복 판단하기

3. 문자열을 정렬한 뒤 인접한 문자열을 비교하는 방식으로 판단한다.

정렬을 할 때 O(nlogn)의 시간이 소요된다. 정렬 할 때 많은 알고리즘이 공간을 추가로 사용한다는 것도 기억해라. 문제에서 요구한 자료구조를 추가로 사용하지 않고 풀 수 있는 알고리즘

문제 설명

1. N 개의 정수를 가진 리스트 A와 정수 K가 입력으로 주어진다.
2. 문제의 목표는 A리스트를 K번 회전한 결과 리스트를 리턴하는 것.
3. 회전이란 리스트의 모든 요소가 하나씩 오른쪽으로 이동하는 것을 말한다(마지막 요소는 첫번째로 이동)

풀면서 주의할 점은 예외케이스를 놓치지 않는 것이다. 

입력으로 빈 리스트가 주어지거나 

리스트는 입력 됬는데 회전 횟수가 0으로 입력되는 경우를 처음에 생각못해서 헤맸다...  

 you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A, K):
    # write your code in Python 3.6
    if len(A) == 0:	## 빈 리스트가 입력으로 들어올 수 있다.
        return []
    if K == 0:		## 리스트만 입력되고 회전 수가 0으로 주어질 수 있다.
        return A
        
    while K > 0:
        
        result = []
        for i in range(len(A)):
            if i == 0:
                result.append(A[-1])
            else:
                result.append(A[i-1])
        A = result
        K -= 1
    return result
    pass

Codility 사이트에서 문제를 풀어보았다.

영어로 된 문제에 처음부터 당황..

하지만 수많은 예시들 덕분에 이해하는데 어렵진 않았다.

파이썬 알고리즘 공부를 하면서 여러가지 유용하고, 헷갈리는 문법들 정리

#1 시간, 공간 복잡도 관련 팁

알고리즘 수행시간을 알아보기 위한 코드

import time
start_time = time.time()

# 프로그램 작성

end_time = time.time()
print("time :", end_time - start_time)

- pypy3는 파이썬3의 문법을 그대로 지원하며, 대부분 파이썬3보다 실행 속도가 더 빠르다. Pypy3를 지원하는 환경이라면 속도를 줄이기 위해 이를 이용하도록 하자

- 기업코딩 테스트 환경에서는 파이썬으로 제출한 코드가 1초에 2000만번 연산을 수행한다고 가정하면 크게 무리가 없다.

- 시간제한이 1초인 문제를 만났을 경우 (참고만 하세요)

- 일반적으로 탐색해야할 전체 데이터의 개수가 100만개 이하일 때 완전탐색을 사용하면 적절하다.

- 정수형 자료형 데이터의 개수에 따른 메모리 사용량

#2 입출력

공백을 기준으로 입력받기

# 3 3 3     <-- 변수로 저장
n, m, k = map(int, input().split())

# 2 4 5 2 3 <-- 배열로 저장
data = list(map(int, input().split()))

2차원 배열 입력받기

data = []
for i in range(n):
    # 데이터가 공백없는 형태로 입력될 때
    # 12345 --> [1, 2, 3, 4, 5]
    data.append(list(map(int, input())))
    
    # 데이터가 공백을 두고 입력될 떄
    # 1 2 3 4 5 --> [1, 2, 3, 4, 5]
    data.append(list(map(int, input().split())))

빠르게 입력받기 (일반적인 입력 방식보다 더 효율적)

import sys

data = sys.stdin.readline().rstrip()

f-string (더 간결하게 여러 자료형을 한 줄로 출력할 수 있음)

num = 7
print(f"정답은 {num}입니다.")

#3 정렬

#0 내림차순 정렬
B.sort(reverse=True) # 내림차순정렬

#1 튜플리스트, 2차원리스트일 경우 여러 가지 기준으로 정렬하기.
s_list.sort(key = lambda x : (-x[1], x[2], -x[3], x[0]))

#2 튜플에 숫자형과 문자형이 섞여있을 경우 숫자형에 int()를 씌워주면
# bad operand type for unary -: 'str' 이슈를 해결할 수 있다
s_list.sort(key = lambda x : (-int(x[1]), int(x[2]), -int(x[3]), x[0] ))

#3 리스트에서 median 값 구하는 식
data[(n-1) // 2] # n은 리스트 길이

#4 sorted with key
array = [('홍길동', 35), ('이순신', 75), ('아무개', 50)]
result = sorted(array, key = lambda x: x[1])
# 성적을 기준으로 오름차순정렬


#5 문자열, 배열, 튜플 등을 역순으로 출력(간결하게)
s = 'abcde'
print(s[::-1])  # 'edcba'
print(s[3:0:-1])  # dcba, 0~3인덱스를 역순으로

l = ['a', 'b', 'c', 'd', 'e']
print(l[::-1])  # ['e', 'd', 'c', 'b', 'a']
t = ('a', 'b', 'c', 'd', 'e')
print(t[::-1])  # ('e', 'd', 'c', 'b', 'a')

#4 문자열, 배열 다루기

파이썬 문자열 아스키변환

주요 아스키 코드값 0 ~ 9 : 48 ~ 57 , A ~ Z : 65 ~ 90, a ~ z : 97 ~ 122

ord('a') ## 아스키코드 숫자 반환
chr(ord('a')) ## 아스키코드에 해당하는 문자 반환

크기가 N이고 모든 값이 0인 리스트 초기화

N = 10
arr = [0] * N

1부터 10까지 증가하는 리스트 초기화

array = [i for i in range(1, 11)]

2차원 배열 좌표 이동

## 풀이 - 좀더 간단한 코드로

n = int(input())
x, y = 1,1
plans = input().split()

## L, R, U, D
dx = [0, 0, -1, 1]
dy = [-1,1,  0, 0]
move = ['L', 'R', 'U', 'D']

for plan in plans:
    for i in range(len(move)):
        if plan == move[i]:
            nx = x + dx[i]
            ny = y + dy[i]
    if nx < 1 or ny < 1 or nx > n or ny > n:
        continue
    x, y = nx, ny
print(x, y)

2차원 배열 90도 회전

n = len(a) # 행 길이 계산
m = len(a[0]) # 열 길이 계산
result = [[0] * n for _ in range(m)]
after = [] # 90도 회전된 배열 저장

# 시계방향으로 회전
for i in range(n):
	tmp = []
	for j in range(m):
    	tmp.append(before[m-1-j][i])
    after.append(tmp)
    
# 반시계방향으로 회전
for i in range(m):
    tmp  = []
    for j in range(n):
    	tmp.append(before[j][m-1-i]) #반시계

    after.append(tmp)

#5 자료형

- 1e9, 1E9 는 10의 9제곱과 같다.

- 임의의 큰 수를 표현하기 위해 자주 표현되는 형식

# 실수형의 계산은 정확하게 떨어지지 않는다.
# 반올림해서 사용하는 것을 습관화하자

if 0.3 + 0.6 == 0.9:
	print(True)
else:
	print(False)

# --> False

- 튜플은 한 번 선언되면 변경할 수 없다.

- 튜플은 리스트에 비해 공간 효율적이다.

#6 내장함수 및 라이브러리

eval() : 문자열로 표현된 수식의 계산 결과값을 반환

result = eval("(3+5)*7")
# --> 56

순열과 조합

# 순열 : 주어진 데이터를 가지고 서로 다른 n 개를 선택하여 일렬로 나열하는 것 
from itetools import permutations

data = [1, 4, 5, 6, 7]
result = list(permutations(data,3))

# 조합 : 주어진 데이터를 가지고 서로 다른 n 개를 선택하는 것 
from itetools import combinations

data = [1, 4, 5, 6, 7]
result = list(combinations(data,3))

Counter : 원소의 등장 횟수를 간단히 셀 수 있다, 원소와 등장 횟수를 사전 형태로 저장할 수 있다.

from collections import Counter

counter = Counter(['red', 'blue', 'green'])
print(dict(counter))

# --> {'red' : 1, 'blue' : 1, 'green' : 1}