취준! ✒/삼성
[코테준비] 삼성19. 삼성 코테 준비전에 꼭 볼 것- SW Expert에 대해서! (feat. 보호 필름 문제 python)
deepbluechip
2023. 10. 11. 02:03
728x90
SW Expert에 대해서
우선, 삼성코테를 보기 위해서는 해당 사이트에 익숙해질 필요가 있다고 한다. 삼성에서 운영하는 코딩테스트 사이트이다. 코드트리나 백준과는 또 다른 느낌이기에 꼭 체험해 보길 바란다.
https://swexpertacademy.com/main/main.do
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
이 사이트에 좋은 점은, 아래와 같다.
- 삼성 코테의 input & output 형식에 대해 잘 알 수 있다. 아래 사진과 같이 삼성 코테는 여러 테케를 한 번에 돌리고 출력하는 것이다. print(f'#{변수명} {숫자}) ← 이것 사용에 익숙해질 필요가 있다. & 초기화도
- 어떤 lib가 허용되는지, 안되는지 알 수 있다. 이 사이트에서 import sys를 하고 컴파일을 하면, 에러가 뜬다. sys를 못쓴다는 소문을 들었는데, 뭐가 더 안되는지 이렇게 import후에 컴파일해 보면 알 수 있다. (확실하지는 않지만, 높은 확률로 맞을 것이다)
참고로 ide를 사용할 수 있는데, python은 pycharm이다. pycharm으로 연습하는 습관도 들이면 좋을 것이다.
익숙해지기 위해 문제를 하나 풀어봤다. 문제를 고른 방법은 '제출순'으로 나열했을 때, 별로 안 어렵고 & SW 모의 역량테스트 기출을 선택하였다.
보호 필름
- 링크:https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu
- 기출: 모의 SW 역량테스트
- 난이도:?
- 분류: ?
- 직접 푼 여부: X https://velog.io/@unani92/SWEA-2112.-%EB%AA%A8%EC%9D%98-SW-%EC%97%AD%EB%9F%89%ED%85%8C%EC%8A%A4%ED%8A%B8-%EB%B3%B4%ED%98%B8-%ED%95%84%EB%A6%84 ← 이 블로그를 참고하여, 이해한 것을 주석으로 표시하였으며, 중간중간 내가 익숙한 방법으로 변경시켰다.
- 언어: 파이썬
풀이
1. main코드를 짜며, 필요한 function 생각하기
for tt in t: # case개수만큼
-- input 받기
-- if k ==1: ans =0
-- else: # 작업시작
---- ans = search() #필요한 작업수 찾기 function
2. "필요한 약물 작업 횟수 찾기 search() "를 어떻게 할 것인가 → 재귀가 필요 (그냥 재귀 / bfs / dfs)
- 그냥 생 상태로 test통과하는지 확인 / 투약 횟수를 1씩 늘리며 test통과하는지 확인 → test 통과하는지 확인하는 def필요 testpass(array)
- 테스트 통과시, ans 업데이트 (현재가 더 작으면)
- 테스트 미통과시, 약을 더 넣어봄 or 약을 더이상 못 넣으면 다음 단계로 넘어감
- 어느 행에 약을 투여할지 정해야 함 → combination
- for i in range(n) / for j in range(i+1, n) → 그전 loop이 어디서 시작했는지 알아야 함 → i 저장 필요 & 몇 개를 뽑는지 정해져 있지 않으므로 재귀 → dfs
- 모든 combination 다 해봐야 함 → 너무 오래걸림 → 중간에 아니다 싶으면 끊어줘야함
- 아니다 싶은 경우:
- (1) 이미 최솟값보다 투약 횟수가 큰 경우 → 최솟값(정답값 ans)와 현재 투약횟수 비교필요
- (2) k 보다 크거나 같은 경우 (k가 최댓값) → k == 현재 투약횟수 → 더 이상 깊게 안들어가도 됨 (재귀함수), 즉, 그 케이스에 대해서 더 이상 투약 안해봐도 됨
- 아니다 싶은 경우:
- 즉, (1) search 안에 (2) testpass (3) dfs 필요 → dfs가 search ! 2개 함수 정의 필요
3. dfs구성
뭘 업데이트하며 재귀해야하는가?
- 투약 횟수: pillcnt
- 어디서 부터 투약하는가: start
+ 바뀐 필름을 계속 새로 만들어서 재귀 하지 않고, film상태를 바꿔가며 재귀 (메모리 효율을 위해) 그래서 dfs를 나왔을 때는 다시 원상 복귀 → 어디를 바꿨는지 저장해둬야함 (이것은 각 재귀당 1열이니, 필름 전체를 만드는 것보다 효율적임. 1/d)
4. testpass 구성
- 열마다 체크
- 한 열이라도 k 이상이 아닌게 있으면 testpass fail - retrun False
- 중간에 retrun False안되었으면 마지막에 True
열마다 어떻게 체크?
- 지금과 다음 것 같은지 - 같으면 cnt +=1, 다르면 cnt =0
- 열 끝까지 안갔는데, cnt >= k 이면, 다음 열로 이동 (그 열은 성공)
+. 만약에 k ==1이면, 그냥 바로 투약안하고 통과 됨 - main코드에 넣어 놓기
5. 만약 중간에 안끊고, 다 찾는다면? 시간 복잡도
- combination: d! = 13! > 10! = 3*10^6
- test: w*d = 20*13 > 2*10^2
- 대충 적어도 6*10^8 = 6억 이상 → 10억 넘어가면 안됨 → 위험
정답 코드 1💻
def inspect(film, k):
# 열(w)마다 돌며, 각 행(d)의 끝까지 가야하므로, w가 밖, d가 안
for i in range(w):
# 한 막에 있는 셀 개수만큼
stack =1 # 연속 셀 개수
for j in range(d-1):
# 막 개수 -1 만큼
if film[j][i] == film[j+1][i]:
#지금꺼랑 다음꺼랑 같으면,
stack +=1
else:
# 다르면, 다시 세기 시작
stack =1
if stack ==k:
# 기준 통과하면, 이 열은 더이상 안봐도 됨
break
# 한 열을 다 살펴봤는데, 개수가 k가 안되면, 불가능 한 것
if stack !=k:
return False
# return False 안되었다는 것은, 다 True가 되었다는 것!
return True
def dfs(l,s,film):
"""
:param l: 약품 사용 횟수
:param s: 약품 치는 곳 시작 위치 (0-1,2,3,4,5 / 1-2,3,4,5 / 2-3,4,5 / .. 이런식으로 combination
:param film: 현재 film상태
:return:
"""
global answer
if l>=answer:
return
if inspect(film, k): # 보호 필름 테스트 통과!
if l<answer: # 현재 정답보다 투약횟수 적으면, 업데이트
answer = l
return
# 테스트 통과 X
if l==k: # 투약횟수가 최댓값이 되면,
if l < answer: # 최댓값이 ans보다 작으면
answer =l # 업데이트
return
else: # 투약횟수 아직 초과 X -> 투약 해줌
# depth마다, 모든 열(w)을 바꿔줘야하니까, d가 밖 & w가 안
for i in range(s,d):
# (1) 1->0 0으로 다 바꿈
switched = []
for j in range(w):
if film[i][j] == 1:
film[i][j] =0
switched.append(j) # 어디를 바꿨는지 기록
# (2) 그 상태로 확인
dfs(l+1,i+1, film)
# (3) 다시 돌려놓음
for j in switched:
film[i][j] = 1
switched=[]
# (4) 1->0 . 1로 다 바꿈
for j in range(w):
if film[i][j] ==0:
film[i][j] =1
switched.append(j)
# (5) 그 상태로 확인
dfs(l+1, i+1, film)
# (6) 다시 돌려 놓음
for j in switched:
film[i][j] =0
# main 문 ------
t = int(input())
for tt in range(1, 1+t):
d,w,k = map(int, input().split())
films = [list(map(int, input().split())) for _ in range(d)] # d * w 배열
answer = 1000000
if k ==1:
# 합격기준이 1이면 그냥 0임
print(f'#{tt} {0}')
else:
dfs(0,0, films)
print(f'#{tt} {answer}')
정답 코드 2💻
def passtest():
"""
test 통과 여부
:return: True / False
"""
for j in range(w):
cnt = 1
for i in range(d-1):
if film[i][j] == film[i+1][j]: # 지금과 다음이 같으면 cnt +=1
cnt+=1
else: # 아니면 초기화
cnt=1
if cnt==k: # 현재 k개 되면, 다음 열 확인
break
if cnt<k:
return False # break 안되었으면, 통과 못했다이야기 - 한 열이라도 통과못하면 아웃
return True # 다 break되었으면, 통과
def dfs(pillcnt, start):
"""
:param pillcnt: 투약 횟수
:param start: 약 어디서 부터 넣으면 되는지
:return:
"""
global answer, film
# 이미 필요 없는 과정은 자르기
if pillcnt >= answer: # 1) 현재 최솟값보다 작지 않은 경우
return
if pillcnt ==k: # 2) 최솟값의 최댓값보다 커지는 순간 - 무조건 통과함
if answer>pillcnt:
answer= pillcnt
return
# 다 검증을 할 필요도 없는 케이스를 다 했으니, 검증하기
if passtest(): # test통과시
if pillcnt<answer:
answer=pillcnt
return
else: # 테스트 통과 못했으면, 더 투약하기 (더 깊게 들어가기)
for i in range(start,d): # 앞에서 해본 경우는 안해봄
# 깊게 들어갈 때, 투약을 먼저함 - film 변화 - 어떻게 변화하는지 저장 (메모리 효율)
# [1] 약 ver1. 0->1
# 1-1. 0->1 로 다 바꿈
switched =[] # 바뀐 부분 체크
for j in range(w):
if film[i][j] ==0:
switched .append(j)
film[i][j] =1
# 1-2. 그 상태 check
dfs(pillcnt+1, i+1)
# 1-3. 다시 상태 돌려놓기
for j in switched :
film[i][j] =0
# [2] 약 ver2. 1->0
# 2-1. 1->0 로 다 바꿈
switched =[]
for j in range(w):
if film[i][j] ==1:
switched.append(j)
film[i][j] =0
# 2-2. 그 상태 check
dfs(pillcnt+1, i+1)
# 2-3. 다시 상태 돌려놓기
for j in switched:
film[i][j] =1
return
import sys
sys.stdin = open("./input.txt")
input = sys.stdin.readline
# main & input
t= int(input())
for tt in range(t):
answer = int(1e9) # 큰 값 넣어둠 (최솟값 찾는 것이므로)
d,w,k = map(int, input().split())
film = [list(map(int, input().split())) for _ in range(d)]
if k ==1:
print(f'#{tt+1} {0}')
else:
dfs(0,0)
print(f'#{tt+1} {answer}')
728x90