척척석사의 코딩기록

from itertools import permutations
N = int(input())
num = list(map(int,input().split())) #숫자들
cal = list(map(int,input().split())) #연산자 갯수

sym = []
for i in range (0,4):
    for j in range (0,cal[i]):
        if i == 0:
            sym.append("+")
        elif i == 1:
            sym.append("-")
        elif i == 2:
            sym.append("*")
        elif i == 3:
            sym.append("//")
#A가 결국은 연산자 순서를 나타나게 될 것이다.
number = [i for i in range (0,N-1)]
A = list(permutations(number,N-1))
minimum = 1e10
maximum = -1e10
for a in A:
    t = num[0]
    for i in range (0,N-1):
        if sym[a[i]] == "+":
            t += num[i+1]
        elif sym[a[i]] == "-":
            t -= num[i+1]
        elif sym[a[i]] == "*":
            t *= num[i+1]
        elif sym[a[i]] == "//":
            t = int(t / num[i+1])
    minimum = min(minimum, t)
    maximum = max(maximum, t)
print(maximum, minimum)

이 코드를 짜면서 문제인 부분은, 답이 1e9가 나왔을때 출력이 10000..... 0.000... 으로 실수형으로 나온다는 점에 제대로 착안해야한다는 점이다.

이 부분을 피하기 위해서, 초기 셋팅을 1e10과 -1e10 등으로 변경하는 것이 주효하였다.

삼성 서류에 붙었으니만큼, 코테를 확실히 준비하는 것이 맞지 않나싶어 열심히 풀어보고 있다.

작년 하반기에는 메모리 분석 및 평가 포지션에 넣었는데 광탈했던 슬픈 기억이 새록새록 ㅎㅎ...

from collections import deque
N = int(input())
pool = [] #전체적인 지도
for i in range (0,N):
    a = list(map(int,input().split()))
    for j in range (0,len(a)):
        if a[j] == 9:
            start = [i,j]
    pool.append(a)

ans,exp,lev = 0,0,2 #exp가 lev와 같아지면 lev += 1, exp = 0
dx,dy = [0,0,1,-1], [1,-1,0,0]

def bfs(x,y):
    visited = [[0 for _ in range (0,N)] for _ in range (0,N)]
    deq = deque([[x,y]])
    next = []
    visited[x][y] = 1
    while deq:
        t = deq.popleft()
        a,b = t[0], t[1]
        for i in range (0,4):
            aa,bb = a + dx[i], b + dy[i]
            if 0 <= aa < N and 0 <= bb < N and visited[aa][bb] == 0:
                if pool[x][y] > pool[aa][bb] and pool[aa][bb] != 0:
                    visited[aa][bb] = visited[a][b] + 1
                    next.append([visited[aa][bb]-1, aa,bb])
                elif pool[aa][bb] == pool[x][y]:
                    visited[aa][bb] = visited[a][b] + 1
                    deq.append([aa,bb])
                elif pool[aa][bb] == 0:
                    visited[aa][bb] = visited[a][b] + 1
                    deq.append([aa,bb])
    next.sort(key = lambda x: (x[0], x[1], x[2]))
    pool[x][y] = 0
    if next == []:
        return None
    return next[0]

while True:
    pool[start[0]][start[1]] = lev
    t = bfs(start[0], start[1])
    if t == None:
        break
    else:
        ans += t[0]
        exp += 1
        start = [t[1], t[2]]
        if lev == exp:
            exp = 0
            lev += 1
        pool[start[0]][start[1]] = 0
print(ans)

BFS를 최대한 잘 사용하는 것이 좋을 것 같다.

삼성 코딩 테스트까지 얼마 남지 않았는데, 잘 준비해서 좋은 결과 있었으면 좋겠다.

제발 오전에 봤으면 좋겠다 ... (오후부터 LG전자 코테 예정되어있음)

삼성 출제 문제였다고한다.

아무래도 직접 주사위를 굴렸다면 훨씬 이해가 빨랐을 수도 있을 것 같다 !

N,M,x,y,K = map(int,input().split())
#N,M은 지도의 사이즈, (x,y)는 좌표, K는 명령의 갯수
plane = []
for _ in range (0,N):
    t = list(map(int,input().split()))
    plane.append(t)
#plane을 통해서 각 좌표에 무엇이 쓰여있는지 알 수 있다

cube = [0,0,0,0,0,0,0]
#바닥 - 북 - 동 - 남 - 서 - 천장
coordinate = [x,y]
ans = []
movement = list(map(int,input().split()))
for i in range (0,K):
    n = movement[i]
    if n == 1:
        #동쪽으로 이동
        if 0 <= coordinate[1] + 1 < M:
            coordinate[1] += 1
            cube = [0,cube[3],cube[2],cube[6],cube[1],cube[5],cube[4]]
            if plane[coordinate[0]][coordinate[1]] == 0:
                plane[coordinate[0]][coordinate[1]] = cube[1]
            else:
                cube[1] = plane[coordinate[0]][coordinate[1]]
                plane[coordinate[0]][coordinate[1]] = 0
            ans.append(cube[-1])
        else:
            continue
    elif n == 2:
        #서쪽으로 이동
        if 0 <= coordinate[1] - 1 < M:
            coordinate[1] -= 1
            cube = [0,cube[4],cube[2],cube[1],cube[6],cube[5],cube[3]]
            if plane[coordinate[0]][coordinate[1]] == 0:
                plane[coordinate[0]][coordinate[1]] = cube[1]
            else:
                cube[1] = plane[coordinate[0]][coordinate[1]]
                plane[coordinate[0]][coordinate[1]] = 0
            ans.append(cube[-1])
        else:
            continue
    elif n == 4:
        #남쪽으로 이동
        if 0 <= coordinate[0] + 1 < N:
            coordinate[0] += 1
            cube = [0,cube[5],cube[1],cube[3],cube[4],cube[6],cube[2]]
            if plane[coordinate[0]][coordinate[1]] == 0:
                plane[coordinate[0]][coordinate[1]] = cube[1]
            else:
                cube[1] = plane[coordinate[0]][coordinate[1]]
                plane[coordinate[0]][coordinate[1]] = 0
            ans.append(cube[-1])
        else:
            continue
    elif n == 3:
        #북쪽으로 이동
        if 0 <= coordinate[0] - 1 < N:
            coordinate[0] -= 1
            cube = [0,cube[2],cube[6],cube[3],cube[4],cube[1],cube[5]]
            if plane[coordinate[0]][coordinate[1]] == 0:
                plane[coordinate[0]][coordinate[1]] = cube[1]
            else:
                cube[1] = plane[coordinate[0]][coordinate[1]]
                plane[coordinate[0]][coordinate[1]] = 0
            ans.append(cube[-1])
        else:
            continue
for i in range (0,len(ans)):
    print(ans[i])

하이고 힘들다 ...

문제는 이런 느낌

import math
N = int(input())
jud = False
t = int(math.log2(N+1)) #t개까지 할 수 있을듯?
for k in range (3, t+1): #k는 항의 갯수
    r = 2
    while r ** (k-1) <= N: 
        if N * (r - 1) % (r ** k - 1) == 0:
            a = N * (r - 1) // (r ** k - 1)
            ans = [a * (r**l) for l in range (0,k)]
            jud = True
            break
        else:
            r += 1
if jud == False:
    print(-1)
else:
    print(len(ans))
    print(*ans)

부등식을 통해서 수를 얼마나 잘 컨트롤 할 수 있을지 체크하는 것이 중요하겠다.

처음 공비의 상한을 () ** (1/k) 꼴로 만들어서 했었는데, 이러면 10000이상에서 문제가 해결이 되지 않는 경우가 생겼었다.

이를 해결하게 위해 while을 통해서 그 범위를 컨트롤 하는 것으로 변경하였더니 바로 문제가 풀렸다 :)

이 문제를 풀면서 가장 어려운 점 중 하나는, 메모리 관리인 것 같다.

메모리 관리와 시간을 얼마나 잘 활용하느냐에 따라서 이 문제를 풀 수 있는지가 나뉘겠다.

처음 풀었던게 25일전이었다 ... 복기에 꽤 시간이 많이 걸렸던 것 같다.

하여튼, 잘 문제를 풀어서 기분은 꽤 좋은 편이다.

이 문제를 푸는 과정에 있어서 주의해야할 과정이 있다 (메모리와 시간 관리에 있어서)

첫번째로,

def prime_set(n):
    if n == 2:
        return [2]
    if n == 3:
        return [3]
    prime = []
    t = int(math.sqrt(n)) + 1
    num = [False for i in range (0,t+1)]
    for i in range (2,t+1):
        if num[i] == False:
            prime.append(i)
            for j in range (i, t+1, i):
                num[j] = True
    return prime
#prime은 소수를 저장하고 있는 집합

위 과정에서는 주어진 n까지의 소수를 취하고 싶은 상황인데, n까지의 집합을 취하게 되면 꼭 도중에 메모리가 터지게 되는 것 같았다.

그래서, 메모리 관리를 해주는 법으로,  t를 저렇게 정리해둔 다음에, t까지의 소수들을 전부 취해준다.

나머지 것들은 이후에 핸들링 해주는 것으로 저렇게 얻어낸다.

def ofprime(n):
    prime = []
    t =  prime_set(n)
    for i in range (0,len(t)):
        if n % t[i] == 0:
            prime.append(t[i])
            while n % t[i] == 0:
                n //= t[i]
    if n != 1:
        prime.append(n)
    return prime

ofPrime이라는 함수를 통해서, n의 소인수들을 얻어줄 것이다. 이 과정에서 위에서 구한 prime_set을 활용하겠다.

여기서 중요한 점으로서, 마지막 조건문인 n!= 1이라면 n을 추가해주는 것. 이게 핵심인 부분이다.

예를 들어 주어진 수 n이 합성수라면, n =   a x b라는 형식으로 얻어질텐데, 일반성을 잃지 않고 a <= b라고 둘 수 있겠다.

저말이 무슨 뜻이냐면, 만약 n의 제곱근정도까지의 소수로 안 나눠떨어졌다 ! 그러면 n은 반드시 소수여야만 한다는 것

이후의 과정은 포함배제의 원리를 사용하면 되겠다.

이거는 아래에 추가로 기재해두겠다.

import sys
from itertools import combinations
import math
input = sys.stdin.readline

def prime_set(n):
    if n == 2:
        return [2]
    if n == 3:
        return [3]
    prime = []
    t = int(math.sqrt(n)) + 1
    num = [False for i in range (0,t+1)]
    for i in range (2,t+1):
        if num[i] == False:
            prime.append(i)
            for j in range (i, t+1, i):
                num[j] = True
    return prime
#prime은 소수를 저장하고 있는 집합

def ofprime(n):
    prime = []
    t =  prime_set(n)
    for i in range (0,len(t)):
        if n % t[i] == 0:
            prime.append(t[i])
            while n % t[i] == 0:
                n //= t[i]
    if n != 1:
        prime.append(n)
    return prime

T = int(input())
for case in range (0,T):
    a,b,N = map(int,input().split())
    cnt1,cnt2 = a-1,b
    prime = ofprime(N)
    for i in range (1,len(prime)+1):
        k = list(combinations(prime,i))
        k = list(set(k))
        for comb in k:
            t = 1
            for j in range (0,len(comb)):
                t *= comb[j]

            #t로 나누겠다는 뜻
            if i % 2 != 0:
                cnt1 -= (a-1) // t
                cnt2 -= b // t
            else:
                cnt1 += (a-1) // t
                cnt2 += b // t
    print(f'Case #{case + 1}: {(cnt2 - cnt1)}')

간만에 기분 좋게 풀었던 문제가 되겠다. 꽤 오래된 체증이 내려가는 느낌....

내일부터는 계약직으로 일을 시작하게 되는데, 코딩 역량도 키우면서 운동도 해보고, 바쁜 삶을 한동안 살아봐야겠다. 

화이팅 !

K를 소인수분해한 뒤, 각각의 소인수가 몇번 곱해져있는지를 defaultdict를 통해서 저장한다...

인데, defaultdict을 안썼구나.

컨트롤이 어려웠던 부분은 처음 소인수분해 부분이었던 것 같다.

먼저, 2의 배수인지 판별한 뒤에, while에서 조금 테크닉을 사용했다.

int(sqrt ...) + 1까지 나눠봤을 때, 안 나눠진다면 그 친구는 소수라고 정의 하는것이 주효하게 사용되는 것 같다.

from collections import defaultdict
T = int(input())

for _ in range (0,T):
    N,K = map(int,input().split())
    #primeset을 통해 K를 나누는 소인수 집합을 구할 예정
    prime_set = {}
    if K % 2 == 0:
        cnt = 0
        while K % 2 == 0:
            cnt += 1
            K //= 2
        prime_set[2] = cnt
    num = 3
    while True:
        if K % num == 0:
            cnt = 0
            while K % num == 0:
                cnt += 1
                K //= num
            prime_set[num] = cnt
        else:
            num += 2
        if K == 1:
            break
        if num >= int(K ** (1/2)) +1:
            prime_set[K] = 1
            break

    prime_num = list(prime_set.keys())
    prime_cnt = list(prime_set.values())
    for i in range (0,len(prime_num)):
        #prime_num[i]가 소인수를 indicate, prime_num[i]에 대응하는 prime_cnt을 통해 총 몇번 나누어지는지 확인할 예정
        if i == 0:
            cnt,deg,n = 0,1,N
            while n > 1:
                cnt += n // (prime_num[i] ** deg)
                deg += 1
                if n < (prime_num[i] ** deg):
                    break
            ans = cnt//prime_cnt[i]
        else:
            cnt,deg,n = 0,1,N
            while n > 1:
                cnt += n // (prime_num[i] ** deg)
                deg += 1
                if n < (prime_num[i] ** deg):
                    break
            ans = min(ans, cnt//prime_cnt[i])
    print(ans)

와 진짜 많이 틀렸는데 어떻게든 통과해서 다행입니다 ......

즐거웠던 문제였습니다.

마지막 컨트롤이 조금 어려웠네요.

N = int(input())
paint = []
for _ in range (0,N):
    painting = list(map(int,input().split()))
    paint.append(painting)
dp1 = [0 for _ in range (0,N)] #idx 0부터 시작하는 경우
dp2 = [0 for _ in range (0,N)] #idx 1부터 시작하는 경우
dp3 = [0 for _ in range (0,N)] #idx 2부터 시작하는 경우

idx = 0
for i in range (0,N):
    if i == 0:
        dp1[i],dp2[i],dp3[i] = paint[i][0],paint[i][1],paint[i][2]
    else:
        dp1[i] = min(dp2[i-1], dp3[i-1]) + paint[i][0]
        dp2[i] = min(dp1[i-1], dp3[i-1]) + paint[i][1]
        dp3[i] = min(dp1[i-1], dp2[i-1]) + paint[i][2]
print(min(dp1[-1], dp2[-1],dp3[-1]))

이렇게 보니까 가운데에 idx는 필요 없다는 것이 ...

N,M,B = map(int,input().split())
land = []
height_min = 1e9
entire_block = B
for _ in range (0,N):
    a = list(map(int,input().split()))
    land.append(a)
    entire_block += sum(a)
    height_min = min(height_min, min(a))

k = (entire_block // (N * M))
ans = []
k = min(k, 256)
for height in range (height_min,k+1):
    time = 0
    for i in range (0,N):
        for j in range (0,M):
            if land[i][j] < height: #쌓아야함
                time += (height - land[i][j])
            elif land[i][j] > height: #깎아야함
                time += 2 * (land[i][j] - height)
    ans.append([time, height])

ans.sort(key = lambda x:x[0])
x = ans[0][0] #최저시간
height = []
for i in range (0,len(ans)):
    if ans[i][0] == x:
        height.append(ans[i][1])
height.sort(reverse = True)
print(x,height[0])

아이디어로서 쓸만한 것 중 하나는, 높이가 최대 256이라는 것 정도가 되겠다.

그리고 k라는 변수로 쌓을 수 있는 최대 높이 (평평하게 하기 위한)를 구하는 것이 주효한 포인트가 될 것이다.