삼성 기출 정리

Index	년도	문제 제목	유형	풀이
1	2024 상반기 오후 1번	마법의 숲 탐색	회전, BFS	- X,Y 좌표 방향 주의 하기 - 조건절 할때 항상 생각 한번 더 하고!! 짜기 - 내 위치가 출구일때, 어떻게 조건절 처리할지 -> 출구 Map 만들거나..
2	2024 상반기 오전 1번	고대 문명 유적 탐사	완전탐색 + BFS + 구현	복사 적절히해서 시간초과 안나게 구현
3	2023 하반기 오후 1번	루돌프의 반란	구현..? + 연쇄적으로 밀때 큐로 관리	연쇄적으로 밀려난다 -> 새로운 배열 만들고 다 이동한 뒤에 만들어주기 한칸씩만 밀려날때도 주의하기
4	2023 하반기 오전 1번	왕실의 기사 대결	BFS	명령을 받고 무응답일때 조건을 설정했어야함
5	2023 상반기 오후 1번	메이즈러너	BFS, 회전, 완전탐색	회전, 동시에 이동 -> 복사 / 0 으로 새로운 배열 만들어주기
6	2023 상반기 오전 1번	포탑 부수기	BFS	첫번째 공격 -> 두번째 공격 이어질때 플래그 잘 설정하기
7	2022 하반기 오후 1번	코드트리 빵	BFS	최단경로 -> BFS로 어디서 오는 방향인지 조심해서 구현
8	2022 하반기 오전 1번	싸움 땅
9	2022 상반기 오후 1번	꼬리잡기놀이
10	2022 상반기 오전 1번	술래잡기	달팽이, BFS	동시에 움직인다 -> 복사 / 0 으로 새로운 배열 만들어주기 리스트 복사 주의하기!!!

 

---

시험치기 전에 읽어보기

 

- SUDO 코드 깔끔하게 작성

- 좌표 이동은 종이에 적어보고 정리한 뒤에 구현하기

 

동시에 움직인다/ 회전 -> 새로운 배열 / 복사한 배열 만들어서 나중에 적용!

비교는 복사하기 전 배열을 조건으로!!

 

- 조건절 방향 확인 direction 중요

- BFS 구현시 visited[x][y] 큐에 처음 넣는 값 방문처리 확실하게 하기

- 함수에서 리턴값이 어떻게 되는지 잘 파악하기

- Flag 반환할때 조심하기!!

- 회전은 구간 회전으로만 구현하고 나머지는 전역변수로 관리하기(최대한)

- 회전은 꼭 복습 복습 복습.. 구간회전도 복습

- 사각형 면적 만들기, 달팽이 구현 꼭 마스터 하기

 

- 명령을 받았을때, 해당 부분의 체력(?) 같은거 구현할때 빈 리스트만 나오는 경우가 가끔가다 있음!! 체크해두고 디버깅할때 꼭 다시 구현하기

 

- 술래잡기 처럼 칸이 만약 겹친다면 어떻게 처리할지 생각해보기. -> 동시이동이니 새로운 배열만들기

꼭 모든 것을 하나의 맵에 표현할 필요는 없음

맵 자체를 카운팅만 하는것보다 리스트로 사용하는 방식도 떠올려보자.

 + 리스트 복사 조심하기!!!!! -> 0으로 복사하면 원래 있던 좌표 위치도 반영해야할게 있을거임 그거 주의

 

- Row, Col, X, Y 범위 확인할때 조심또 조심!!! 확인 잘하기!!

 

회전 코드

def rotate(sr, sc, maps, size):
    # size x size 영역을 시계 방향으로 회전
    new_maps = [row[:] for row in maps]  # 전체 맵을 얕은 복사
    for i in range(size):
        for j in range(size):
            new_maps[sr+i][sc+j] = maps[sr+size-1-j][sc+i]  # 시계 방향으로 회전
    return new_maps

순열, 중복순열, 조합, 중복조합

arr = [1, 2, 3, 4]
visited = [False] * 4
# 순열
def permutatuon(n,new_arr):
    global visited
    if len(new_arr) == n:
        print(new_arr)
        return
    else:
        for i in range(len(arr)):
            if visited[i] == False: # 순열은 방문처리 지정해야함
                visited[i] = True
                permutatuon(n,new_arr + [arr[i]])
                visited[i] = False
# 중복순열
def product(n,new_arr):
    if len(new_arr) == n:
        print(new_arr)
        return
    else:
        for i in range(len(arr)):
            product(n,new_arr + [arr[i]]) # 제일 나이브한 코드
# 조합
def combination(c,n,new_arr):
    if len(new_arr) == n:
        print(new_arr)
        return
    else:
        for i in range(c,len(arr)):
            combination(i+1,n,new_arr + [arr[i]]) # 조합은 i + 1


def combination_with_replacement(c,n,new_arr):
    if len(new_arr) == n:
        print(new_arr)
        return
    else:
        for i in range(c,len(arr)):
            combination_with_replacement(i,n,new_arr + [arr[i]]) # 조합이랑 i 만 다름
print('permutaion')
permutatuon(3,[])
print('product')
product(3, [])
print('combination')
combination(0,3,[])
print('combination_with_replacement')
combination_with_replacement(0,3,[])

permutaion
[1, 2, 3]
[1, 2, 4]
[1, 3, 2]
[1, 3, 4]
[1, 4, 2]
[1, 4, 3]
[2, 1, 3]
[2, 1, 4]
[2, 3, 1]
[2, 3, 4]
[2, 4, 1]
[2, 4, 3]
[3, 1, 2]
[3, 1, 4]
[3, 2, 1]
[3, 2, 4]
[3, 4, 1]
[3, 4, 2]
[4, 1, 2]
[4, 1, 3]
[4, 2, 1]
[4, 2, 3]
[4, 3, 1]
[4, 3, 2]
product
[1, 1, 1]
[1, 1, 2]
[1, 1, 3]
[1, 1, 4]
[1, 2, 1]
[1, 2, 2]
[1, 2, 3]
[1, 2, 4]
[1, 3, 1]
[1, 3, 2]
[1, 3, 3]
[1, 3, 4]
[1, 4, 1]
[1, 4, 2]
[1, 4, 3]
[1, 4, 4]
[2, 1, 1]
[2, 1, 2]
[2, 1, 3]
[2, 1, 4]
[2, 2, 1]
[2, 2, 2]
[2, 2, 3]
[2, 2, 4]
[2, 3, 1]
[2, 3, 2]
[2, 3, 3]
[2, 3, 4]
[2, 4, 1]
[2, 4, 2]
[2, 4, 3]
[2, 4, 4]
[3, 1, 1]
[3, 1, 2]
[3, 1, 3]
[3, 1, 4]
[3, 2, 1]
[3, 2, 2]
[3, 2, 3]
[3, 2, 4]
[3, 3, 1]
[3, 3, 2]
[3, 3, 3]
[3, 3, 4]
[3, 4, 1]
[3, 4, 2]
[3, 4, 3]
[3, 4, 4]
[4, 1, 1]
[4, 1, 2]
[4, 1, 3]
[4, 1, 4]
[4, 2, 1]
[4, 2, 2]
[4, 2, 3]
[4, 2, 4]
[4, 3, 1]
[4, 3, 2]
[4, 3, 3]
[4, 3, 4]
[4, 4, 1]
[4, 4, 2]
[4, 4, 3]
[4, 4, 4]
combination
[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]
combination_with_replacement
[1, 1, 1]
[1, 1, 2]
[1, 1, 3]
[1, 1, 4]
[1, 2, 2]
[1, 2, 3]
[1, 2, 4]
[1, 3, 3]
[1, 3, 4]
[1, 4, 4]
[2, 2, 2]
[2, 2, 3]
[2, 2, 4]
[2, 3, 3]
[2, 3, 4]
[2, 4, 4]
[3, 3, 3]
[3, 3, 4]
[3, 4, 4]
[4, 4, 4]

중력

maps =[[0]*5 for i in range(5)]
maps[0][3] = 1
maps [4][3] = 1
c = [0,3]
def gravity(c):
    global maps
    new_maps = [x[:] for x in maps]
    cx,cy = c[0], c[1]
    ncx = cx
    while True:
        if ncx < 5 and maps[ncx+1][cy] == 0:
            ncx += 1
        else:
            break
    new_maps[cx][cy] = 0
    new_maps[ncx][cy] = 1
    return new_maps
print('하강 전')
for i in maps:
    print(i)
maps = gravity(c)
print('하강 후')
for i in maps:
    print(i)

하강 전
[0, 0, 0, 1, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 1, 0]
하강 후
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 1, 0]
[0, 0, 0, 1, 0]

 

범위 정해서 특정 영역~회전

maps2 = [[i*5+j for j in range(5)] for i in range(5)]
def rotate(sr,sc,size):
    new_maps = [x[:] for x in maps2]
    for i in range(size):
        for j in range(size):
            new_maps[sr+i][sc+j] = maps2[sr+size-1-j][sc+i]
    return new_maps
print('90도 회전 전')
for i in maps2:
    print(i)
maps2 = rotate(1,1,3)
print('90도 회전 후')
for i in maps2:
    print(i)

90도 회전 전
[0, 1, 2, 3, 4]
[5, 6, 7, 8, 9]
[10, 11, 12, 13, 14]
[15, 16, 17, 18, 19]
[20, 21, 22, 23, 24]
90도 회전 후
[0, 1, 2, 3, 4]
[5, 16, 11, 6, 9]
[10, 17, 12, 7, 14]
[15, 18, 13, 8, 19]
[20, 21, 22, 23, 24]