[코드트리챌린지] 4회차

실력진단

 

 

 

진단문제 못푼거 

#격자생성
n= int(input())
li=[]

for _ in range(n):
    li.append(list(map(int,input().split())))

#마을사람수 세기 
cnt3= 0 #사람수 세명인 마을수 

#상하좌우 탐색용
di=[-1,0,1,0]
dj=[0,1,0,-1]

#함수정의
#i,j 와 인접한 1 찾고 / 8로 바꿔버리고 / 3명인곳 명수 추가 
queue= [] 

def findP(i,j): #(i,j) 부터 안나올때까지 탐색
    global queue
    queue.append((i,j))
    pcnt = 1
    
    while queue:
        ii,jj = queue.pop(0)
        #인접 지점 탐색 
        for t in range(4):
            if ii+di[t] >= 0 and ii+di[t] <n and jj +dj[t] and jj +dj[t] <n:  

                ddi, ddj = ii+di[t], jj+dj[t]
                
                
                if li[ddi][ddj] ==1:
                    #탐색리스트에 추가
                    
                    queue.append((ddi,ddj))
                    pcnt +=1 
                    li[ddi][ddj] = 8 

    if pcnt ==3:
        global cnt3
        cnt3 +=1

#탐색시작  - 방문한곳은 8로 변경 
for i in range(n):
    for j in range(n):
        if li[i][j] == 1:
            #탐색시작 
            findP(i,j)



print(cnt3)

 

진단문제 4번 ..백트래킹 

n = int(input())

#재귀함수 
#1. 현재상태 idx 
#2. 종료조건
#3. 재귀함수 
arr=[0 for _ in range(n)] #n자릿수의 값 
def func(idx): # 0~(idx-1) 까지는 조건에 맞게 결정했고 
               # idx ~ (n-1) 까지 조건에 맞게 모두 탐색하는 함수 
    #종료조건 : 0 ~ (n-1) 까지 조건에 맞게 결정한 경우
    if idx == n:
        print(*arr,sep="")
        return
    
    #재귀함수 : idx 번째 값을 결정 
    for i in range(1,10): #1~9 까지 숫자를 하나씩 넣어볼것이다 
        if idx ==0 or abs(arr[idx-1]-i) ==1: #idx 가 0 인건 체크할필요없이 가능함...
            arr[idx] =i 
            func(idx+1) # (idx+1)  인덱스 부터 (n-1) 까지 탐색
            arr[idx] =-1 #초기화 

#재귀함수 실행
func(0)

 

공부한내용

 

개념 - 피보나치 풀이방법

 

 

문제풀이 -숫자들의 배수

https://www.codetree.ai/missions/4/problems/multiple-of-numbers?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

그냥 내맘대로 푼거(속도가 좀더 느리다)

n = int(input())

arr= [n*i for i in range(1,11)]

cnt=0
for j in arr: 
    if j%5==0:
        cnt +=1
    print(j,end=" ") 
    if cnt >=2 :
        break

해설보고 문제에서 풀라는대로 배열에 저장(피보나치처럼) 다시풀어본거 

속도가 좀더 빠르다 

 

n = int(input())

arr =[n] 
cnt=0
for i in range(1,10):
    arr.append(arr[0]+arr[i-1])

for j in arr:
    if j%5==0:
        cnt+=1
    
    print(j,end=" ")

    if cnt >=2:
        break

 

 

문제2 

https://www.codetree.ai/missions/2/problems/n-permutations-of-k-with-repetition-under-constraint?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

K,N =map(int,input().split())
#k : 1~K 까지 숫자 고름  2
#N : N 개 고름 3
#연속 3 개 이상 안나오게.. 앞이랑 앞앞이 아니면됨 or 인덱스값이 0,1 인경우 가능 

#재귀함수 
#1. 현재상태 매개변수 
#2. 종료조건
#3. 재귀함수 호출 

answer = [0 for _ in range(N)] 

def func(idx): # 0~ (idx-1) 까지 조건에 맞게 결정했고 
               # idx ~ (n-1) 번째 인덱스를 조건에 맞게 모두 탐색하는 함수
    #종료조건 : 0~ (n-1)까지 조건에 맞게 결정한 경우 
    if idx == N:
        print(*answer,sep=" ") 
        return

    #재귀함수 호출 
    # idx 번째 값을 정해주자
    for i in range(1,K+1):
        
        #조건에 맞게 추가 
        if idx<2 or answer[idx-1] != i or answer[idx-2] != i : #and 조건아님.. 둘중에 하나라도 아니면 됨 둘다 아닐 필요가 없음..

            answer[idx] = i

            #idx+1 부터 n-1 값 탐색하는 함수 
            func(idx+1)
            answer[idx]=-1 # 제거해줘야함 .. 


#함수 호출 
func(0)





"""K,N = map(int,input().split())

#현재상태 조건
#종료조건
#호출함수 작성

answer = [0 for _ in range(N)] 

def func(idx): # 0 ~ (idx-1) 까지는 조건만족하게 잘 정한 상태 
               # idx ~ (N-1) 번째 까지 조건만족하게 잘 정해야한다.
    #종료조건  : 0 ~ (N-1) 까지 조건 만족하게 잘 정한경우 
    if idx == N:
        print(*answer)
        return 

    # 재귀 호출문
    for num in range(1,K+1):
        if idx <= 1 or answer[idx-1] != num or answer[idx-2] !=num : # or 조건임 .. 다 ..
            answer[idx] = num #해당 번지에 숫자를 넣는 구문
            func(idx+1) #다음번 재귀호출
            answer[idx] = -1 #삭제의 의미
    


func(0)
"""

 

#코드트리 #코딩테스트 #코딩테스트실력진단