완전탐색(Brute Forcing)

카테고리 Python

완전탐색(Brute Forcing)

가능한 모든 경우의 수를 검사하는 방법

문제 1

시간에서 ‘3’이 포함된 횟수 구하는 문제

1
2
3
4
5
6
7
8
9
10
h = int(input())

count = 0
for i in range(h+1):
    for j in range(60):
        for k in range(60):
            if '3' in str(i)+str(j)+str(k):
                count += 1

print(count)

문제 2

체스 말이 움직일 수 있는 경우의 수 구하라

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
col,row = map(str,input())

n = 8

# ASCII 코드 구하는 코드 ord(str), ord('a') = 97
array = [[i+1 for i in range(n)] for _ in range(n)]

steps = [(-2,-1),(-1,-2),(1,-2),(2,-1),(2,1),(1,2),(-1,2),(-2,1)]

count = 0
for step in steps:
    y = int(row) + step[0]
    x = int(ord(col)) - int(ord('a')) + 1 + step[1]
    if x < 1 or y < 1 or x > 8 or y > 8:
        continue
    count += 1

print(count)
1
2
3
4
5
6
# 말이 움직이는 벡터 방향
dx = [2,2,-2,-2,1,1,-1,-1]
dy = [1,-1,1,-1,2,-2,2,-2]

# x,y로 방향이 2개로 정해져있으니 튜플 사용 가능
steps = [(-2,-1),(-1,-2),(1,-2),(2,-1),(2,1),(1,2),(-1,2),(-2,1)]
  • ASCII 코드를 사용하여 ‘a’ 문자열을 숫자로 변환

문제 3

문자는 정렬하고 숫자는 더하여 반환하라

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
input = input()
result = []
value = 0

for i in input:
    if i.isalpha():
        result.append(i)
    else:
        value += int(i)

result.sort()

if value != 0:
    result.append(str(value))

print(''.join(result))
  • isalpha() 내장함수를 사용하여 i가 문자열인지 확인
  • join() 내장함수를 사용하여 list를 문자열로 합침

댓글 공유

그리디 알고리즘 with Python

카테고리 Python

greedy 알고리즘

탐욕적으로 현재 상황에서 가장 최적의 문제풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토한다.

문제

1이 될 때 까지, N을 K로 나누거나 N에 1을 빼거나 행동의 최소 횟수 구하기

조건

N(1 <= N <= 100,000) K(2 <= K <= 100,000)

풀이

K가 2이상이므로 1을 빼는 것보다 최대한 많이 나누는 것이 연산횟수를 최소화할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
N,K = list(map(int,input().split(' ')))
count = 0

# 시간복잡도 O(N)
while N != 1:
    if (N % K == 0):
        N /= K
        count += 1
        continue
    N -= 1
    count += 1

# 시간복잡도 O(log N)
while True:
    target = (N // K) \* K
    count += (N - target)
    N = target
    if N < K:
        break
    count += 1
    N //= K

count += (N - 1)
print(count)

댓글 공유

코딩테스트를 위한 파이썬 기본문법

카테고리 Python

리스트 컴프리핸션

1
2
3
4
5
6
7
n = 4
m = 3

array = [[0] \* m for \_ in range(n)]

array[0][1] = 5
print(array)

2차원 배열 참조값 복사 오류

1
2
3
4
5
6
7
8
n1 = 4
m1 = 3

# 참조값이 복사되어 원하는 부분 이외의 요소도 변경됨

array1 = [[0]*m]*n
array1[0][1] = 5
print(array1)

dictionary

1
2
3
4
5
6
7
8
9
10
data = dict()
data['apple'] = '사과'
data['banana'] = '바나나'

if 'apple' in data:
print(data['apple']+'가 존재합니다.')

key_list = list(data.keys())

print(key_list)

set 자료형

1
2
3
4
5
6
c = 3.11
print(int(c))

sett = set([1,2,3])
print(sett)
print(sett)

입력

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
n = int(input())

data = list(map(int,input().split()))

x,y,z = map(int,input().split())

print(n)

print(data)

print(x,y,z)

# sys.stdin.readline() 빠른 입력

import sys

data1 = sys.stdin.readline().rstrip();

print(data1)

출력

1
2
3
4
5
6
7
8
9
f = 1
g = 2

print(f,g)
print(f, end=' ')
print(g, end=" ")

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

조건문

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
x = 15
if x >= 10:
print('X는 10이상입니다.')

if x >= 0:
print('X는 0 이상입니다.')

if x >= 0 and x <= 100:
print('X는 0보다 크거나 같고 100보다 작거나 같습니다.')

res = 'cool' if x>10 else 'fail'
print(res)

if x > 12: rest = 'cooler'

print(rest)

반복문

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
i = 1
result = 0

while i <= 9:
result += i
i += 1

print(result)

arr = [9,8,7,6,5,4]

for x in arr:
print(x)

rss = 0
for k in range(1,10):
rss += k

print(rss)

for u in range(2,10):
for o in range(1,10):
print(f"{u} X {o} = {u\*o}")
print()

함수

1
2
3
4
5
6
7
8
9
10
gf = 0

def func():
global gf
gf += 1

for \_ in range(10):
func();

print(gf)

람다표현식

1
2
3
4
5
6
7
8
9
10
11
12
print((lambda a,b: a+b)(33,7))

people = [('홍길동',10),('이순신', 5),('아무개',70)]

print(sorted(people,key=lambda x: x[1]))

list1 = [1,2,3,4,5]
list2 = [6,7,8,9,10]

list_result = map(lambda a,b:a+b, list1, list2)

print(list(list_result))

내장함수

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
minvalue = min(10,2,3,7)

print(minvalue)

evalvalue = eval('3\*5-2');

print(evalvalue)

from itertools import permutations
from itertools import combinations
from itertools import product
from itertools import combinations_with_replacement

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

print(list(permutations(dataaa,3)))
print(list(combinations(dataaa,2)))

# 2개를 뽑는 모든 순열 (중복포함)

print(list(product(dataaa,repeat=2)))

# 2개를 뽑는 모든 조합 (중복포함)

print(list(combinations_with_replacement(dataaa,2)))

# 객체의 갯수 구하기

from collections import Counter

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

print(counter['blue'])
print(counter['green'])
print(dict(counter))

# 최대 공약수, 최소 공배수

import math

def lcm(a,b):
return a\*b // math.gcd(a,b);

v = 21
j = 14

print(math.gcd(v,j))
print(lcm(v,j))

댓글 공유

loco9939

author.bio


author.job