7월 20일 목요일 코테 : 알고리즘 강의 - 시뮬레이션

No. 1

 

 

* 시뮬레이션 문제는.. 1초마다 일어나는 일들을 .. 잘 명세해서 적어주는게 좋음 

 

-  문제 1: 최고의 33위치 

 

코드 1

 

n = int(input()) #격자크기

matrix=[]

#격자 생성
for i in range(n):
    aline = list(map(int,input().strip().split())) 
    matrix.append(aline)


#동전개수 구하기 

#3*3 격자내 동전개수 
MaxCoin = [] 
#시작행값
for i in range(n-2):
    #시작열값
    for j in range(n-2):
        
        #시작값으로부터 행3개씩 열3개씩 더함 
        sumCoin=0
        for k in range(i,i+3):
            for t in range(j,j+3):
                sumCoin += matrix[k][t]

        MaxCoin.append(sumCoin)



print(max(MaxCoin))

 

새롭게 알게된것 

 

시뮬레이션 :  문제에서 주어진 상황을 그대로 재현해보는것 

시뮬레이션 문제는 삼성에서 무척 좋아하는 문제이다.

 

완전탐색 : 가능한 경우를 전부 다 따져서 탐색하는것 

이건 오래걸리기때문에 n 의개수가 적은경우에만 사용가능.. 안그러면 시간초과뜸 

 

 

강사님 코드 

#변수 선언 및 입력
n=int 

#생략 ㅎ..그냥 입력받고.. matrix 를 grid 에 담기.. 이차원배열형태로 


def get_num_of_gold(row_s,col_s,row_e,col_e):
    num_of_gold=0

    for row in range(row_s,row_e+1):
        for col in range(col_s,col_e+1):
            num_of_gold += grid[row][col]
    return num_of_gold



max_gold = 0 

#(row, col)이 3*3 격자의 좌측상단 모서리인 경우를 전부 탐색합니다. 
for row in range(n):
    for col in range(n):
        #3*3 격자가 n*n 격자를 벗어나는 경우는 계산하지 않습니다. 
        if row +2>=n or col +2 >=n:
            continue
        
        num_of_gold = get_num_of_gold(row,col,row+2,col+2)

        #최대 금의 개수를 저장합니다.
        max_gold=max(max_gold,num_of_gold)

print(max_gold)

 

 

주의할점

for 문이 네개 쓰였다.. .

 

 

 

No. 2

기본개념 

격자안에서 밀고당기기 문제..

실수 자주 나는부분 

n=6
a=[0,1,2,3,4,5]

temp =a[0]
for i in range(1,n): # 1번원소부터 (n-1)번 원소까지 선택하기
    a[i-1] = a[i]    # i 번 원소를 i-1 번 위치로 옮길것 
    a[n-1] =temp     # 마지막 위치에 temp 복구 

print(*a)

a=[0,1,2,3,4,5]
n=6

temp2= a[n-1] #a[n] 아님.. 그럼 a[6] 들어가는건데.. 인덱스값 5까지 있음 

##안되는답.. .오른쪽으로밀땐 뒤에서부터 밀어줘야한다... 
for j in range(0,n-1):
    a[j+1] = a[j] # i 가 아니라 j 써야함.. 
    a[0] =temp2

print(*a)

a=[0,1,2,3,4,5]
for k in range(n-2,-1,-1):
    a[k+1] =a[k]
    a[0]= temp2
print(*a)

 

-  문제 2: 격자 안에서 밀고 당기기 / 컨베이어 벨트

코드 

 

#입력받는부분 
n,t = map(int,input().strip().split())

#첫째줄,둘째줄
line1= list(map(int,input().strip().split()))
line2= list(map(int,input().strip().split()))

#시간초 지나는 동안 변경 
for i in range(t):
    #윗줄값 변경
    temp1= line1[n-1]
    for j in range(n-2,-1,-1):
        line1[j+1] = line1[j]

    temp2= line2[n-1]
    #아랫줄값 변경
    for k in range(n-2,-1,-1):
        line2[k+1]=line2[k]

    #임시저장된값을 제위치에 넣기 
    line2[0] =temp1
    line1[0]=temp2

#출력
print(*line1)
print(*line2)

 

새롭게 알게된것 

 

 

주의할점

 

 

No. 3

 

 

-  문제 3: 격자 안에서 터지고 떨어지는 경우 / 1차원 젠가

 

코드 

#입력받기 
n= int(input()) #블럭수 

block=[]
for _ in range(n):
    block.append(int(input()))


#첫번째 제거
temp1=[]
s1,e1 = map(int,input().strip().split())
for k in range(n):
    if not (s1-1) <= k <= (e1-1): 
        temp1.append(block[k])
    
block=temp1
    
#두번째 제거
temp2=[]
s2,e2 = map(int,input().strip().split())
n2= len(block)
for j in range(n2):
    if not (s2-1) <= j <= (e2-1):
        temp2.append(block[j])

block=temp2

#출력
print(len(block)) #남은 블록의 개수
for p in block:
    print(p)

 

새롭게 알게된것 

 

파이썬에서는.. 슬라이스 사용해서 써도 된다. 

근데 슬라이스는 시간복잡도가 좋은편은 아니라서.. 안쓸수있으면 안쓰는게 좋긴함 

메모리를 계속 새로 만드는 행위여서 잘 알고 써야함 

 

그런데 이문제에선 어차피 다 순회해야하기때문에 슬라이스 써도 상관없긴함 

 

주의할점

문제에서 뭘 출력하라고 하는지 잘 읽기... 

 

 

 

No. 4 -> 난 아직 안풂... 

 

 

-  문제 4 : 격자 안에서 여러 객체를 이동 / 숫자가 가장 큰 인접한 곳으로 동시에 이동

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 (codetree.ai)

 

강사님 코드 

 

n,m,t =map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
marbles =[[0 for _ in range(n)] for _ in range(n)]

for _ in range(m):
    r,c = map(int,input().split())
    marbles[r-1][c-1] =1 



def find_max(i,j):
    #같은 값을 가질 때, 상하좌우 우선순위를 갖도록 하는 장치 
    di=[-1, 1, 0, 0]
    dj=[ 0, 0,-1, 1] 

    max_value,max_i,max_j =0,0,0

    for k in range(4):
        ni,nj = i +di[k] , j+dj[k]

        if 0<= ni < n and 0 <= nj <n: #격자를 벗어나지 않는다면 

            if a[ni][nj] > max_value:
                max_value, max_i, max_j = a[ni][nj] , ni, nj 

    return max_i, max_j 


#step 1. 각 구슬을 규칙에 맞게 이동시키기
def moveAll():
    global marbles 
    temp = [[0 for _ in range(n)] for _ in range(n)] #이동된 결과를 저장할 배열 

    #구슬먼저 찾기 
    for i in range(n):
        for j in range(n):
            if marbles[i][j] ==0: 
                continue
            
            #i행 j 열에 구슬이있다.
            ni,nj = find_max(i,j) #i 행 j 열에 있느 구슬이 가야하는 위치를 계산  
            temp[ni][nj] += 1 #해당 위치로 구슬 이동 # temp 는 각 격자마다 몇개의 구슬이있는지를 의미함 

    marbles = temp 

#step 2. 겹치는 구슬 삭제하기 
def deduplicate():
    #2개 이상이 모인 격자의 구슬을 0개로 초기화 
    for i in range(n):
        for j in range(n):
            if marbles[i][j] >= 2:
                marbles[i][j] = 0 



#시뮬 문제는 스텝마다 함수를 작성하는거 추천  
for _ in range(t):
    #step 1. 각 구슬을 규칙에 맞게 이동시키기
    moveAll()


    #step 2. 겹치는 구슬 삭제하기 
    deduplicate()



#남아있는 구슬 개수 출력하기 
ans =0 
for i in range(n):
    ans += sum((marbles[i]))
print(ans)

 

새롭게 알게된것 

 

t초후  라는 키워드 

일초마다 일어나는 규칙이 상세하게 나와있다면

=> 시뮬레이션 문제 

: 문제가 시키는거 그대로 구현하면됨 

 

근데 이때 t 초의 범위가... 20억 초 .. 라면...

1초마다 시뮬레이션 하는게아니라.. 빠르게 구할방법을 생각해봐야함 

 

주의할점

 

 

이거 쓰면 안되는이유.. 옮겨진 구슬이 또 옮겨지게 됨..