[백준][파이썬]

문제 번호 : 16637
문제 출처 : https://www.acmicpc.net/problem/16637

Code

from itertools import combinations


def disable(tu):    # 괄호를 둘 수 있는가 판별
    if len(tu) > 1:
        tmp_li = list(combinations(tu, 2))

        for tmp in tmp_li:  # 2개를 골라와서 그 차이가 1이면 괄호를 둘 수 없다.
            if max(tmp) < min(tmp) + 2:
                return True

        return False

    else:
        return False


def calc(expr):
    result = 0
    old_op_idx = -1
    old_op = '+'
    op1 = 0
    for i in range(len(expr)):
        if expr[i] == '+' or expr[i] == '*' 
                or expr[i] == '-' and i - old_op_idx != 1:
            op1 = result
            op2 = expr[old_op_idx+1:i]
            result = eval(str(result) + old_op + expr[old_op_idx+1:i])
            old_op = expr[i]
            old_op_idx = i
    result = eval(str(result) + old_op + expr[old_op_idx+1:])
    return result


n = int(input())
expression = input()    # 수식 입력
num_op = n//2           # 연산자 개수 = 수식 길이 // 2
answer = - 2**31        # -2**31 < ANSWER < 2**31
maximum = 2**31

if n == 1:      # 길이가 1 ==> 숫자 하나 입력
    print(int(expression))
elif n == 3:    # 길이가 3 ==> 연산자 하나를 가지는 수식 입력
    print(eval(expression))
else:
    for br in range(1, num_op//2+1):    # br : 괄호 갯수, 괄호의 최대 개수는 연산자 수 // 2
        cases = list(combinations(range(num_op), br))   # 괄호 br 개를 넣을 수 있는 경우의 수를 모두 찾아냄
        for case in cases:
            if disable(case):   # 괄호를 넣을 수 있는지 판별
                continue
            else:
                ex = expression # 수식을 잠깐 저장
                for i in range(len(case)-1, -1, -1):                # 수식을 뒤에서 부터 수정
                    i = case[i]                                     # 앞에서부터 수정하면 뒷 부분의 index값이 변함
                    ex_li = list(ex) # 수식의 중간을 수정하기 위해 list 형으로 잠시 변환
                    ex_li[i*2: i*2+3] = str(eval(ex[i*2:i*2+3]))    # 수식의 중간 부분 수정
                    ex = ''.join(ex_li)                             # join()함수로 list를 다시 str으로 변환
                answer = min(max(calc(ex), answer), maximum)        # 계산 결과와 원래 값 중 최대값을 비교
                                                                    # 문제에서의 최대값을 넘어가지 않도록 비교
    print(answer)

Idea

1. 입력 예시 1을 기준으로 설명하겠다. 재귀 함수를 사용하면 더 쉬울 듯 하다.
   예를 들어 3+8*7-9*2 가 입력되면 3+8을 한 후 7-9*2를 재귀함수의 입력으로 넣고 다시 2를 입력으로 넣는 방식으로 풀어도 괜찮을 듯 한데 재귀함수를 많이 접하지 않아서 만들지 못했다.
2. 그래서 단순 반복으로 했는데 괄호가 들어갈 수 있는 위치의 모든 경우의 수를 구해야 했다. 우선 괄호의 최대 개수는 입력된 수식에서 연산자 개수를 2로 나눈 몫이다.
3. 괄호가 1개인 경우부터 최대 개수까지 반복해서 연산자의 개수에서 괄호 개수 만큼 가능한 모든 조합을 뽑아서 조건을 확인한다. 괄호 연산이 가능한 조건은 한 가지 뿐이다. 괄호 연산을 할 연산자가 붙어 있으면 안 된다.
4. 괄호 계산을 먼저 한 후 문자열에서 3글자를 한 숫자로 바꾸어주어야 했는데 str 형에서 문자를 대체하는 replace()함수로 구현을 하게 되면 바꾸려는 문자열과 같은 문자열이 더 앞에 존재하면 원하는 위치가 아니라 엉뚱한 문자열을 바꾼다.
   ex) 예제 입력 6에서 수식은 1-9-1-9-1-9-1-9-1-9 일 때
   1-9-1-9-(1-9)-1-9-1-9, 1-9-1-9-1-9-1-9-(1-9) 두 경우 모두 -8-1-9-1-9-1-9-1-9로 바뀐다.
   그래서 문자열로 표현된 수식을 잠깐 리스트로 바꿔서 원하는 위치의 문자들을 바꾼후 다시 str로 변환한다. 문자열로 바꿀 때는 전에 사용했던 ''.join()을 사용했다.
   ( 문자열은 튜플 같이 요소들의 직접적인 변경이 허용되지 않는다. ex) str[0] = 'a' error
5. 수식을 계산하는 함수 calc()를 살펴보면 연산자의 위치를 찾고 연산자가 나타날 때까지의 수를 operand로 사용해서 그 전의 값과 old_op에 해당하는 연산을 수행한다. 만약 연산자 뒤에 바로 -가 나오면 그건 음수를 뜻하는 것으로 if 문에서 False가 되어 동작하지 않는다.
6. 수식의 길이가 1인 경우와 3인 경우에는 괄호의 최대 개수가 0으로 되어 동작하지 않아서 처음에 예외 처리를 해두었다.

이번 코드는 재귀함수로 여러 번 시도하다가 안 돼서 시간이 오래 걸렸다. 이 문제에서 처음으로 사용한 함수는 eval()이라는 함수이다. 어떤 책에서는 괄호 안의 수식을 계산해주는 함수라고만 설명이 되어 있다. 하지만 eval()은 괄호 안에 파이썬 명령어를 써 넣으면 명령어에 해당하는 동작을 수행하고 그 값을 반환해준다.

s = "\"Hello World\""
eval("print(" + s + ")")

# 결과
# Hello World

내가 봐도 코드가 이해가 안 될 수 있는 부분들이 많아서 설명이 길어졌다. 더 클린한 코드를 짜도록 노력해야겠다.

C언어 복습하기 2회차 - C 기초**

이 글은 C programming : a modern approach를 바탕으로 공부한 내용을 정리한 것입니다.

오늘 공부할 내용은 전처리 지시자, 함수, 변수, 구문 등 기본적인 내용이다. 이번 챕터의 내용은 간단히 알면 되는 것이고 변수형과 scanf 같은 함수는 이후에 다시 나올 것이므로 자세하게 설명하지 않고 넘어간다.

목차

2. C 기초
   2.1 프로그램 컴파일과 링크
   2.2 프로그램 일반적 구조
   2.3 주석
   2.4 변수
   2.5 scanf
   2.6 상수 이름 정의하기
   2.7 식별자
   2.8 프로그램의 레이아웃
   Q & A

2.1 프로그램 컴파일과 링크

문장 출력하는 프로그램

To C, or not to C: that is the question.
위의 문장을 출력하는 프로그램을 만들 것이다. 이 프로그램은 pun.c에 쓰여진다.

#include <stdio.h>

int main(void)
{
printf("To C, or not to C: that is the question.\n");

return 0;
}

#include는 라이브러리 정보를 불러오기 위함이다. 여기서는 stdio.h라는 표준 입출력 라이브러리 정보를 가져온다. 이 안에 printf가 있다.
프로그램에서 사실상 실행되는 코드는 main에 존재한다. \\n 은 다음 줄로 넘긴다는 의미가 된다. 마지막 줄의 return 0;은 프로그램이 종료될 때 운영체제에 0이라는 값을 반환하는 것을 의미한다.

컴파일과 링크

pun.c파일을 컴퓨터는 바로 실행하지 못한다. c 언어의 경우 보통 전처리, 컴파일, 링크의 과정이 필요하다.

전처리Preprocessing **
#으로 시작하는 지시어directive로 알려진 줄들의 지시를 먼저 따른다.

컴파일Compile *
전처리를 거친 프로그램은 컴파일러를 통해 오브젝트 파일로 번역이 된다.
*링킹Linking **
오브젝트 파일이 완벽하게 실행하기 위해 라이브러리 내부의 명령문 같은 추가적인 코드를 합친다.

UNIX에서는 C 컴파일러를 cc라고 부른다.

% cc pun.c

위의 명령문으로 pun.c를 컴파일과 링킹까지 완료된다. 이 경우 a.out이라는 실행 파일이 만들어진다.

GCC 컴파일러

GCC 컴파일러는 가장 유명한 C 컴파일러이다. 리눅스에서는 기본 제공되고 다른 환경에서도 사용할 수 있다.

통합개발환경 IDE

하나의 프로그램에서 코드를 수정, 컴파일, 링킹과 디버깅까지 해주는 개발환경을 말한다.

2.2 프로그램의 일반적 구조

C 프로그램의 기본 구조

*directive*

int main(void)
{
*statements*
}

지시자directive

C 프로그램이 컴파일되기 직전 전처리기에 의해 처음으로 수정된다. 전처리기가 수행하는 명령문들을 지시자라고 한다.
지시자에서는 ;를 사용하지 않는다.

함수function

반환형 함수명(parameter){
statement
}
인자를 받아와서 구문에 따라서 동작한 후 정해진 반환형을 반환한다.

구문statement

프로그램이 실행될 때 실행되어야 하는 명령들이다.
pun.c에서는 printf("문장");과 return 0;가 구문이다. C언어에서 구문은 ;로 끝나야 한다.

2.3 주석comment

주석은 프로그램 안에서 프로그램에 대한 설명이나 명령들에 대한 설명을 적는 것이다.
한 줄 주석은 //로 작성할 수 있고 여러 줄의 주석은 /* */로 작성한다.
주석은 실행되지 않는다.
(//로 주석을 적는 건 C99를 사용하는 경우이다.)

/* 
주석1    
주석2
주석3
*/
// 주석4

2.4 변수와 할당

형type

모든 변수들은 반드시 type을 가져야 한다. 데이터를 저장하는 형태와 크기가 type에 따라 달라진다.

선언declare

변수들은 반드시 선언 과정이 필요하다.

type name;

구식 컴파일러에서는 구문들 사이에서 선언을 할 수 없으므로 주의해야한다.
하지만 C99를 사용한다면 변수가 필요한 순간 직전에 변수를 선언하는 것이 보편적이다.

할당assignment

할당은 변수에 값을 저장하는 것을 의미한다.

int height;    // 선언
height = 8;    // 할당

초기화initializaion

기본 설정값이 없는 변수는 초기화되지 않았다고 한다. 컴파일러에 따라 프로그램이 중단되기도 한다. 초기값을 부여하는 방법은 변수에 값을 할당해주는 것이다.

int height = 8;
int height = 8, length = 12;    // 여러 변수에 각기 여러 값 할당이 가능
int height, length = 10;    // length만 10으로 초기화되고 height는 선언만 되었다.

2.5 scanf

printf()는 출력하는 함수라면 scanf()는 입력을 받는 함수이다. 두 함수에서 f는 formatted의 약자이다.

scanf("%d", &i); // 정수를 입력받아 i에 저장

%d 는 int 형을 의미하고 &는 나중에 알아보도록 하겠다.

2.6 상수 이름 정의하기

프로그램 내에서 절대 값이 변하지 않는 상수를 사용한다면 상수에도 이름을 지어주는 것이 좋다. 예를 들어서 일한 시간에 따른 임금을 구할 때 사용할 수 있다.

#define money_per_hour 8720

int main(void){
    int hour = 8
    money = hour * money_per_hour
}

위와 같이 상수도 이름을 정해주게 되면 코드의 가독성이 높아지게 된다. 시급을 모르는 사람이 보더라도 이해하기 쉬워진다.

2.7 식별자identfier

프로그램을 작성할 때 변수, 함수, 매크로의 이름들을 식별자라고 부른다. C에서는 문자, 숫자, _ 를 사용 가능하고 숫자로 시작할 수는 없다.

C에서는 식별자를 대부분 소문자로만 작성하고 가독성을 위해 언더바 _ 를 사용한다. Jave나 C#, C++ 같은 경우에는 언더바보다는 첫 번째 글자를 대문자로 적어준다.
어떤 방법을 선택하던지 항상 통일 시키는 것이 중요하다. 식별자 글자 수에 제한이 없으므로 최대한 구체적으로 사용하는 것이 좋다.

키워드keyword

auto enum restrict unsigned
break hextern return void
case float short volatile
char for signed while
const goto sizeof _Bool†
continue if static _Complex†
default inline† struct _Imaginary†
do int switch
double long typedef
less register union

위의 표에 있는 키워드들은 식별자로 사용이 불가능하다. 컴파일러에 따라 error나 경고가 뜰 수도 있다.
( 나는 ATmega128과 관련해 프로그램을 만들 때 mode라는 변수를 사용했고 에러가 나지도 않았지만 원하는 대로 프로그램이 동작하지 않았고 디버거로 한 줄씩 실행을 하면서 발견한 경험이 있다.)

2.8 C 프로그램의 레이아웃

이 책에서 C 프로그램은 토큰token의 연속이라고 표현한다. 토큰은 의미를 가진 최소 단위이다.

printf("Height: %d\n", height);

이렇게 7개의 토큰으로 구성되어 있다. 토큰 사이의 공백은 가독성을 높여준다. 같은 이유로 연산자마다 줄을 띄워 주는 것도 좋은 방법이다.
빈 줄은 프로그램을 잘게 쪼개어 주어서 이해하기 편하게 만들어 주기도 한다.

int main(void)
{
    float fahrenheit;    // 변수의 선언
    float celsius;

    printf("Enter Fahrenheit temperature: ");    // 화씨 값 입력받기
    scanf("%f", &fahrenheit);

    celsius = (fahrenheit - FREEZING_PT) * SCALE_FACTOR;    // 섭씨로 변환하기

    printf("Celsius equivalent: %.1f\n", celsius);    // 섭씨 값 출력

    return 0;
}

Q & A

GCC의 약자는 뭔가요?

GNU C Compiler의 약자였는데 현재는 GNU Compiler Collection의 약자로 바뀌었다. GCC가 C 외에도 Ada, C, C++, Fortran, Java, Objective-C 같은 언어를 컴파일 하기 때문에

컴파일러는 주석을 어떻게 인식하나요?

a/**/b = 0;
예전에는 ab = 0;으로 해석했지만 현재에는 a b = 0으로 해석한다. 컴파일러는 주석을 공백으로 인식한다.

부동소수점 상수 끝에 f를 붙이는 이유

소수점을 포함하지만 f가 붙지 않은 상수는 double 형이 될 수 있습니다. double은 float 보다 2배 정밀도를 갖는 type으로 float이 저장할 수 없는 수가 할당되려고 할 수도 있기 때문

[백준][파이썬] 16943번 숫자 재배치

문제 번호 : 16943
문제 출처 : https://www.acmicpc.net/problem/16943

Code

from itertools import permutations

def to_int(t):
    if t[0] != '0':
        pos = 10 ** (len(t)-1)
        tmp = 0
        for i in t:
            tmp += int(i) * pos
            pos = pos // 10
        return tmp
    return -1


a, b = input().split()
b = int(b)
c = -1

numbers = list(permutations(a)
for number in numbers:
    if number[0] == '0':
        continue
    num = int(''.join(number)) # to_int(number)
    if num < b:
        c = max(num, c)

print(c)

Idea

1. a를 순열을 사용해서 만들기 편하게 하기 위해서 int형으로 변환하지 않고 문자열로 입력받는다. (문자열도 iterable이기 때문에)
2. b는 미리 int형으로 형변환을 한다.
3. permutations(a) r 이 생략되었으므로 a의 길이를 인자로 갖는다.
4. 문자로 이루어져 있는 튜플을 숫자로 변환한다.
5. b와 비교해서 작으면 다시 max()로 비교한 후 저장한다.

for 문에서 number 가 튜플 자료형이기 때문에 int(number)를 사용할 수 없어서 처음에는 to_int()라는 함수를 만들어서 사용했다. 그러다가 튜플을 문자열로 바꾸는 방법이 있어서 적용해봤다. 내가 만든 to_int()로 프로그램을 돌렸을 때 시간이 1288ms 가 나왔고 int(''.join(number))를 사용했을 때 432ms 가 나왔다.

''.join(iterable) 은 iterable 자료형의 값들을 모두 이어붙여서 반환해준다. 값들 사이에 문자를 넣고 싶다면 따옴표 사이에 넣으면 된다. 예를 들어'-'.join(['a', 'b','c']) 라는 함수가 있으면 'a-b-c'를 반환한다.

Itertools 순열 조합 라이브러리

알고리즘 문제를 풀다보면 순열이나 조합을 사용해서 문제를 풀 때 더 간단하게 풀 수 있는 경우가 많다. 그럴 때에는 itertools 라이브러리를 사용한다.
itertools 라이브러리에는 사실 순열과 조합 외에도 iterable 자료형을 처리하는 다른 함수들이 존재하지만 가장 자주 쓰이는 것이 순열과 조합이기 때문에 여기서는 순열, 조합을 사용하는 법만 확인한다.
다른 기능을 알고 싶으면 https://docs.python.org/ko/3/library/itertools.html 를 확인하길 바란다.

1. 순열 Permutation

itertools.permutations(iterable, r = None)
순열은 iterable 자료형에서 r 개의 데이터를 뽑아 순서가 있는 형태로 나타낸다.
각각의 sub sequence는 길이가 r 이고 튜플로 이루어진다. 반환형태는 클래스이기 때문에 사용하기 힘들 수 있기 때문에 주로 리스트로 변환을 해주는 것이 편하다. (필수는 아니다.)

from itertools import permutations

data = ['a', 'b', 'c']

result = list(permutations(data))
result2 = permutations(data)
# 두 번째 인자를 넣어주지 않으면 자동으로 r = len(data) 가 된다.
print(result)
print(result2)
for i in result2:
    print(i, end=' ')

| [('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'a', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a')]
<itertools.permutations object at 0x0000020AD7E80EA0>
('a', 'b', 'c') ('a', 'c', 'b') ('b', 'a', 'c') ('b', 'c', 'a') ('c', 'a', 'b') ('c', 'b', 'a') |
| --- |

코드에서 처럼 for 문에서 튜플을 하나씩 가져와서 사용하는 것은 가능하지만 result2[0]같이 직접적으로 객체에 접근하는 것은 불가능하다. 그래서 list로 변환을 해주는 것이 편하다는 것이고 앞으로 나올 combinations, product, combinations_with_replacement 에서는 설명을 생략한다.

2. 조합 Combination

itertools.combinations(iterable, r =None)
조합은 순열은 iterable 자료형에서 r 개의 데이터를 뽑아 순서가 없는 상태로 나열한다.

from itertools import combinations

data = ['a', 'b', 'c']
result = list(combinations(data, 2))    # r = 2 로 설정

print(result)

3. 데카르트 곱(cartesian product)

itertools.product(iterable, repeat = 1)
데카르트 곱은 iterable 자료형에서 repeat 개 만큼을 중복을 허용해서 순열을 만든다고 책에 쓰여져 있기도 하지만 사실 product는 여러개의 iterable 자료형을 입력으로 받아서 가능한 모든 곱을 나타내는 것이다. 다음은 3가지 예시를 보여준다.

from itertools import product

data = ['a', 'b', 'c']
data2 = ['x', 'y']
data3 = range(2)    # [0, 1]
result = list(product(data, repeat=2))

print(result)
print(list(product(data, data2)))
print(list(product(data3, repeat=3)))

| [('a', 'a'), ('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'b'), ('b', 'c'), ('c', 'a'), ('c', 'b'), ('c', 'c')]
[('a', 'x'), ('a', 'y'), ('b', 'x'), ('b', 'y'), ('c', 'x'), ('c', 'y')]
[(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)] |
| --- |
| 'product(data, repeat=2) 는 사실 product(data, data) 이다. 두 번째 예시에서 보듯이 data에서의 값과 data2에서의 값으로 만들 수 있는 모든 순열을 만들어 내는 것이다. |
| 세 번째 예시는 나중에 이진수를 만들어 낸다면 유용하게 쓰일 것 같아서 적어봤다. |

4. 중복 조합

** itertools.combinations_with_replacement(iterable, r = None)**
중복 조합은 말 그대로 중복을 허용해서 조합을 완성시키는 것이다. 바로 예시로 넘어간다.

from itertools import combinations_with_replacement

data = ['a', 'b', 'c']

result = list(combinations_with_replacement(data, 2))

print(result)

마무리

파이썬 개념 정리는 처음으로 글을 썼다. 백준닷컴 문제를 풀다보니 순열, 조합을 사용하는 것이 많아서 정리가 필요해서 글을 썼다. 파이썬 라이브러리를 직접 찾아보면서 글을 적다보니 시간이 많이 걸렸지만 대충 알고 있던 정보도 올바르게 알게 되어서 시간이 날 때면 라이브러리를 찾아 봐야할 것 같다.
오늘 공부한 내용 중에서 중요했던 것을 되짚어보면서 마무리 하겠다.

• itertools를 import해서 만들어져있는 순열, 조합 함수를 쓰면 쉽게 코드를 작성할 수 있다.
• 순열, 조합의 반환형은 class이기 때문에 list로 변환하면 편하게 쓸 수 있다. 하지만 필수는 아니다.
• product는 단순히 중복 순열만을 위한 함수가 아니지만 알고리즘 상 중복 순열을 만들어내는 능력이 있는 것이다.
• 함수를 제대로 공부하고 싶으면 라이브러리를 참고하자.

문제 번호 : 16938

문제 출처 : https://www.acmicpc.net/problem/16938 

Code

import itertools


def diff(num):
    return max(num) - min(num)


n, l, r, x = map(int, input().split())
a = list(map(int, input().split()))
count = 0

for i in range(2, n+1):
    numbers = list(itertools.combinations(a, i))
    for number in numbers:
        if l <= sum(number) <= r:
            if diff(number) >= x:
                count += 1

print(count)

Idea

1. N개의 난이도를 2개 이상으로 조합해서 조건에 맞는지 확인한다.
2. combination한 후 list의 요소는 iterable한 튜플 형으로 모든 난이도의 합은 sum 함수로 구현이 가능하다.
3. 차를 구하는 함수는 최대값에서 최소값을 빼주는 형태로 가능했다.
4. 두 조건을 모두 만족하면 count 값을 1씩 증가시키고 마지막에 출력한다.

이전의 문제들보다 난이도가 낮은 편이었다. 처음에는 n이 1인 경우에 print(0)을 먼저 하는 경우를 생각했었는데 print를 2번하게 되어서 채점중(99%)에서 "틀렸습니다"가 나왔다. 아무래도 마지막 입력에서 n이 1인 듯하다. n이 1이면 2개 이상을 조합으로 뽑아올 수 없다.