[이코테] 12. 구현문제

Nam_JU·2023년 8월 9일
algorithm
1

Algorithm

목록 보기
19/20

12. 구현

구현능력이 요구되는 대표적인 알고리즘 문제 유형으로는 완전탐색과 시뮬레이션이 있다. 완전 탐색은 모둔 경우의 수를 빠짐없이 다 계산하는 해결방법을 의미하고 시뮬레이션은 문제에서 제시하는 논리나 동작과정을 그대로 코드로 옮겨야 하는 유형을 의미한다.
완전탐색 문제는 모든 경우의 수를 다계산해야 하기 때문에 반복문 혹은 재귀함수를 적절히 사용하여 예외 케이스를 모두 확인해야 하는 경우가 많다. 그러므로 일반적으로 DFS/BFS 알고리즘을 이용해서 문제를 해결한다. 시뮬레이션문제 또한 비슷하다.


12-1. 럭키 스트레이트

"""
123402
"""

n = int(input())
n= list(map(int, str(n)))
s= len(n)

if sum(n[:s//2]) == sum(n[s//2:]):
    print("LUCKY")
else:
    print("READY")

12-2. 문자열 재정렬

  • 내 코드
"""
K1KA5CB7
AJKDLSI412K4JSJ9D
"""

s = input()
answer=[]
num=0
for c in s:
    if c.isalpha():
        answer.append(c)
    else:
        num+=int(c)
answer.sort()
answer.append(str(num))
print(''.join(answer))
  • 예외처리 : 숫자가 없는 문자열로 답이나올 경우, 끝에 0이 붙음
s = input()
answer=[]
num=0
for c in s:
    if c.isalpha():
        answer.append(c)
    else:
        num+=int(c)
answer.sort()

## 수정 - 예외처리
if num!=0:
    answer.append(str(answer))
print(''.join(answer))

12-3. 문자열 압축

def solution(s):
    answer = 0
    cnt=1
    word=''
    #한자리씩은 완료함 -> 1~len(s)//2바퀴만큼 늘려서 확인해야함
    j=1
    ch = [0]*(len(s)//2)
    while (j<=len(s)//2):
        for i in range(1, len(s), j):
            if s[i-1]==s[i]:
                cnt+=1
            else:
                if cnt==1:
                    word+=s[i]
                else:
                    word+=str(cnt)+s[i-1]
                    cnt=1
        # ch[j] = len(word)
        print(word)
        j+=1

    return answer

print(solution("aabbaccc"))

한글자씩 비교후, 턴했을때의 비교로 넓히려고 하니 세부 조건들이 더 생기면서 복잡해짐. i를 사용한 인덱스는 턴마다 슬라이싱으로 더해줘야하는데 여기서 한계를 겪음.
주어진 재료는 다찾았는데 요리를 못했음....

  • 정답
def solution(s):
    answer = len(s)
    for x in range(1, len(s)//2+1):
        char_len = 0 #턴이 끝날때마다 초기화
        char = ''
        cnt = 1
        for i in range(0, len(s)+1, x):
            temp = s[i: i+x]
            if char == temp:   #앞뒤 같은 문자열일 경우 누적합
                cnt += 1
            elif char != temp: #앞뒤 다른 문자열일 경우 - 문자만 저장
                char_len += len(temp)
                if cnt > 1:    #누적된 값의 여부 확인 T: 누적한 중복문자열 길이만 더하기
                    char_len += len(str(cnt))
                cnt = 1        # F,나머지: 1로 초기화, 마지막 문자열 저장
                char = temp
        answer = min(answer, char_len) #턴이 끝나기전 이전턴과 길이비교
    return answer
print(solution("aabbaccc"))
print(solution("abcabcdede"))
  1. answer를 문자열 1개씩 끊었을때 전부 다를경우로 초기화시킴
    최소값을 찾아나갈예정이니 max값을 문자열 길이로 지정.
  2. 연속된 문자열의 최대 길이가 전체 문자열 길이의 반임으로 1-len(s)//2로 턴 설정
  3. 문자열 비교를 위해 0-len(s)길이와 턴값을 두어 인덱스를 넓히기 위해 지정
  4. 슬라이싱을 사용해 현재 문자열을 저장
  5. 앞뒤 같은문자열일 경우 숫자를 초기화된 1부터 +=1씩 누적.
    1로 초기화시키지 않으면 앞의 문자열이 누락됨
  6. 앞뒤 다른문자열일 경우 공통으로 현재 문자열 저장
    • 누적값이 있을경우
      누적한 중복 문자열 길이만 더하기
    • 누적값이 없을경우
      누적합 부분을 1로 초기화, 다음 문자열과 비교를 위해 현재 문자열 저장
  7. 턴이 끝날때마다 저장된 최종길이 비교

12-4. 자물쇠와 열쇠

  • 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/60059
    예제를 분석하면서 오히려 편견에 갖힌느낌...
    90도 회전후 좌우 아래 1칸씩 이동을보고 방향 설정을 어떻게 해야할지 감이 안왔음.
    lock을 기준으로 회전을 한다고 했을때 침범하는 칸이동을 어떻게 해결할것인지, 구현부분도 막막함.

  • 정답

def match(graph, key, rot, x, y):
    n = len(key)
    #key 90회전
    for i in range(n):
        for j in range(n):
            #회전이 없는 경우
            if rot == 0:
                # key값을 더해 안맞는 경우 누적합으로 겹치는 부분을 판별 (최종 전부 1인지 확인을 위해서)
                graph[x + i][y + j] += key[i][j]
            elif rot == 1: #시계방향으로 90도
                graph[x + i][y + j] += key[n-1 -j][i]
            elif rot == 2: #180도
                graph[x + i][y + j] += key[n-1 -i][n-1 -j]
            else:
                graph[x + i][y + j] += key[j][n-1 -i]

# lock이 모두 1인지 확인
def check(graph, temp, n):
    for i in range(n):
        for j in range(n):
            if graph[temp + i][temp +j] != 1:
                return False
    return True

def solution(key, lock):
    answer = True
    temp = len(key)-1 #key와 lock의 떨어진 거리

    #key위치 x:행, y:열
    for x in range(temp+len(lock)):
        for y in range(temp + len(lock)):
            #key 4방향 회전
            for rot in range(4):
                # 전체 도면 생성 (key_max=20, lock_max=20 20X3-2 : 1개씩 걸쳐 있어야 함으로)
                graph = [[0 for _ in range(58)] for _ in range(58)]
                # lock 복사
                for i in range(len(lock)):
                    for j in range(len(lock)):
                        #lock기준 temp길이만큼 떨어진곳에 복사
                        graph[temp+i][temp+j]=lock[i][j]
                match(graph, key, rot, x, y)

                #맞은 경우 lock 영역이 모두 1인지 확인
                if check(graph, temp, len(lock)):
                    return True
    return False

print(solution([[0, 0, 0], [1, 0, 0], [0, 1, 1]],[[1, 1, 1], [1, 1, 0], [1, 0, 1]]))

12-5. 뱀

  • 사과 = 몸길이 길어짐
  • 종료 = 벽이나 자신의 몸에 닿으면 끝남
  • 뱀 = 1초마다 이동하며 이동한 칸에 사과가 있으면 뱀 길이 +1증가
    사과가 없으면 그대로
  • 이동 = L:왼쪽90 , D:오른쪽90
    뱀과 사과를 숫자 몇으로 두어서 판별할 것인지??
  • 정답코드
n = int(input())
k = int(input())
data = [[0] * (n + 1) for _ in range(n + 1)] # 맵 정보
info = [] # 방향 회전 정보

# 맵 정보(사과 있는 곳은 1로 표시)
for _ in range(k):
    a, b = map(int, input().split())
    data[a][b] = 1

# 방향 회전 정보 입력
l = int(input())
for _ in range(l):
    x, c = input().split()
    info.append((int(x), c))

# 처음에는 오른쪽을 보고 있으므로(동, 남, 서, 북)
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

def turn(direction, c):
    if c == "L":
        direction = (direction - 1) % 4
    else:
        direction = (direction + 1) % 4
    return direction

def simulate():
    x, y = 1, 1 # 뱀의 머리 위치
    data[x][y] = 2 # 뱀이 존재하는 위치는 2로 표시
    direction = 0 # 처음에는 동쪽을 보고 있음
    time = 0 # 시작한 뒤에 지난 '초' 시간
    index = 0 # 다음에 회전할 정보
    q = [(x, y)] # 뱀이 차지하고 있는 위치 정보(꼬리가 앞쪽)

    while True:
        nx = x + dx[direction]
        ny = y + dy[direction]
        # 맵 범위 안에 있고, 뱀의 몸통이 없는 위치라면
        if 1 <= nx and nx <= n and 1 <= ny and ny <= n and data[nx][ny] != 2:
            # 사과가 없다면 이동 후에 꼬리 제거
            if data[nx][ny] == 0:
                data[nx][ny] = 2
                q.append((nx, ny))
                px, py = q.pop(0)
                data[px][py] = 0
            # 사과가 있다면 이동 후에 꼬리 그대로 두기
            if data[nx][ny] == 1:
                data[nx][ny] = 2
                q.append((nx, ny))
        # 벽이나 뱀의 몸통과 부딪혔다면
        else:
            time += 1
            break
        x, y = nx, ny # 다음 위치로 머리를 이동
        time += 1
        if index < l and time == info[index][0]: # 회전할 시간인 경우 회전
            direction = turn(direction, info[index][1])
            index += 1
    return time

print(simulate())

12-6. 기둥과 보 설치


[x좌표, y좌표,(0:기둥/1:보), (0:삭제/1:설치)]
설치조건과 삭제조건은 동일하게 적용되어야 함

  • 기둥: 바닥위, 보의 한쪽끝, 다른 기둥 위 가능
  • 보 : 한쪽끝이 기둥위, 양쪽끝 보와 연결 가능

0,1일때 설치가 가능한지 여부를 판단하는 함수/
먼저 설치/삭제 후 여부 확인 -> answer구현 

def check(answer):
    for x, y, stuff in answer:
        if stuff == 0:
            if y==0 or [x-1, y, 1]in answer or [x,y,1]in answer or [x,y+1, 0]in answer:
                continue
            return False
        elif stuff == 1:
            if [x,y-1,0] in answer or [x+1, y-1, 0]in answer or ([x-1, y, 1] in answer and [x+1, y, 1]in answer):
                continue
            return False
    return True

def solution(n, build_frame):
    answer = []
    for ch in build_frame:
        x, y, stuff, operate = ch
        if operate==0:
            answer.remove([x,y,stuff])
            if not check(answer):
                answer.append([x,y,stuff])
        if operate==1:
            answer.append([x,y,stuff])
            if not check(answer):
                answer.remove([x,y,stuff])
    return sorted(answer)

print(solution(5,[[1,0,0,1],[1,1,1,1],[2,1,0,1],[2,2,1,1],[5,0,0,1],[5,1,0,1],[4,2,1,1],[3,2,1,1]]))

12-7. 치킨배달

리스트를 전부 만들고 위치값을 출력해서 모든 집과 치킨집을 대응해서 경우의 수를 구해야하나?
1. 좌표에 입력된 치킨집중 수익을 가장 많이 낼 수 있는 치킨집M의 조합을 찾기
2. 해당 조합별 대응되는 집거리의 합을 구해 최소거리를 찾기 

from itertools import combinations
n, m = map(int, input().split())
chicken = []
house = []
# house, chicken 좌표 저장
for x in range(n):
    data = list(map(int, input().split()))
    for y in range(n):
        if data[y]==1:
            house.append((x,y))
        elif data[y]==2:
            chicken.append((x,y))

comb = list(combinations(chicken, m))

# 각각의 집에 대응되는 치킨거리의 합 구하기
def all_find(comb):
    answer=0
    for hx, hy in house:
        temp = 1e9
        for cx, cy in comb:
            temp = min(temp, abs(hx-cx)+ abs(hy-cy))
        answer +=temp
    return answer

answer = 1e9
#치킨 위치를 하나씩 집어넣어 해당 치킨집에 대응되는 모든 집의 거리중 최소값 저장
for c in comb:
    answer = min(answer, all_find(c))

print(chicken)
print(house)
print(comb)
print(answer)

12-8. 외벽점검

from itertools import permutations
def solution(n, weak, dist):

   
    length = len(weak)
     # 0을 넘어가는 순간 길이를 두배로 늘림
    weak = weak + [w + n for w in weak]
    minCnt = 1e9
    
    
    for start in range(length):
    	# 이동거리의 모든 경우
        for d in permutations(dist, len(dist)):
            cnt = 1
            pos = start # 시작점 초기화 (현재 친구의 포지션이 시작점)
            # weak의 길이는 1부터 임으로 ~
            for i in range(1, length):
            	#다음 방문위치 = 시작점 + i
                nexPos = start + i
                # 다음 시작점 거리까지 가능한지 확인 
                diff = weak[nexPos] - weak[pos]
                # 다음 거리에 닿지 못하면 
                if diff > d[cnt-1]:
                    pos = nexPos
                    cnt += 1
                    # 사용할 수 있는 친구가 남아있는지 확인 
                    if cnt > len(dist):
                        break
             # 모두 방문했고, 주어진친구 이내에 사용했다면            
            if cnt <= len(dist):
                minCnt = min(minCnt, cnt)

    #방문이 안되는 경우
    if minCnt == 1e9:
        return -1
    return minCnt

profile
Nam_JU
개발기록
이전 포스트

[파알문] 5. 자료구조 활용

0개의 댓글