coding test - python/SAMSUNG SWT(SW역량 테스트)

삼성 기출 정리

sillon 2024. 10. 12. 19:30
728x90
반응형
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]

 

 

24.10 시험 후기

 

'최단 거리' 문제라고 하면 보통 맨해튼 거리나 유클리드 거리로 해결할 수 있을 거라 생각하기 쉽습니다. 하지만 장애물이나 특정 이동 제한이 있는 경우, 이런 방법으로는 정확한 최단 경로를 찾을 수 없습니다.

-> BFS (너비 우선 탐색)으로 풀기 

왜 BFS로 풀어야 할까?

  • BFS는 한 지점에서 모든 경로를 넓게 탐색하며 가장 먼저 도착한 경로가 최단 거리가 됩니다.
  • 장애물이 있는 복잡한 상황에서도 실제 갈 수 있는 경로만 탐색하므로 정확한 최단 경로를 찾을 수 있습니다.

출발지와 목적지 설정이 중요하다!

  • 예: "참가자가 A 장소로 가는 최단 경로" → 참가자 = 출발지, A 장소 = 목적지
  • 여러 참가자가 A 장소로 가는 경우 → A 장소를 출발지로 설정해 모든 참가자까지의 거리를 BFS로 한 번에 구할 수 있음.

정리

  1. 장애물이 있는 경우 BFS로 탐색해야 최단 경로를 정확히 찾을 수 있다.
  2. 출발지와 목적지 설정에 따라 탐색 효율이 달라진다.
  3. 상황에 맞게 BFS 방향을 설정하면 더 빠르고 정확한 해답을 얻을 수 있다.
728x90
반응형