알고리즘(Python)

기린이·2021년 6월 26일
0

알고리즘🔑

목록 보기
16/17

문자열 유형

반복되는 패턴으로 특정 길이 채우기

원래 나의 접근

p = [1,2,3,4,5]
length = 9

m = length//len(p[s])
n = length%len(p[s])

if m > 0:
    lst = p[s]
    for _ in range(m-1):
        lst += p[s]

    # last_lst = [0 for _ in range(n)]
    # for i in range(n):
    #     last_lst[i] = p[s][i]

    last_lst = p[s][:n]

    all_lst = lst + last_lst
    # print(all_lst)
else:
    all_lst = [0 for _ in range(length)]
    for i in range(length):
        all_lst[i] = p[s][i]

몫 = 채워야하는 길이 // 패턴길이
나머지 = 채워야하는 길이 % 패턴길이

몫만큼 패턴 반복해서 더하기 + 나머지길이만큼 패턴 자르기
-> 최종 리스트 완성

내가 한 해결

m = length // len(p[s])
n = length % len(p[s])

if m > 0:
    all_lst = p[s] * m + p[s][:n]
else:
    all_lst = p[s][:length]

다른 사람 해결

def solution(answers):
    pattern1 = [1,2,3,4,5]
    pattern2 = [2,1,2,3,2,4,2,5]
    pattern3 = [3,3,1,1,2,2,4,4,5,5]
    score = [0, 0, 0]
    result = []

    for idx, answer in enumerate(answers):
        if answer == pattern1[idx%len(pattern1)]:
            score[0] += 1
        if answer == pattern2[idx%len(pattern2)]:
            score[1] += 1
        if answer == pattern3[idx%len(pattern3)]:
            score[2] += 1

    for idx, s in enumerate(score):
        if s == max(score):
            result.append(idx+1)

    return result
  • 1%5 = 1 몫=0, 나머지=1

  • answer의 인덱스 % 패턴길이 -> answer의 인덱스와 매칭되는 패턴의 인덱스

특정값이 여러개 있을 때 인덱스 값을 알아내기

result = []
for idx, val in enumerate(lst):
	if val==max(lst):
    	result.append(idx)

dfs, bfs 유형

이중 리스트로 visited나 grid 만들때

visited = [[False]*3]*3 
  • 위와 같이 3x3 격자에 대한 visited 어레이를 만들면 안된다.
  • [1,2,3]* 3 은 리스트 내부 원소를 3번 반복하라는 것인데 만약 안에 들어있는 것이 숫자가 아니라 리스트면 하나의 리스트를 변경하면 다른 리스트도 변경된다. 아마 리스트의 얕은 복사와 깊은 복사의 차이때문에 그런 듯 하다.
  • 따라서 아래와 같이 리스트가 복사가 되지 않도록 해야한다.
visited = [[False]*3 for _ in range(3)]

visited = [[False for _ in range(3)] for _ in range(3)]

dfs

# dfs 문제 구현

# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())

# 2차원 리스트의 맵 정보 입력 받기
grid = []
for i in range(n):
    grid.append(list(map(int, input())))

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def dfs(x, y):
    if grid[x][y] == 0:
        grid[x][y] = 1

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx > (n-1) or ny < 0 or ny > (m-1):
                continue
            elif grid[nx][ny] == 1:
                continue

            else:
                dfs(nx, ny)
        return True

    else:
        return False

cnt = 0
for i in range(n):
    for j in range(m):
        if dfs(i, j) == True:
            print(i, j)
            cnt += 1
print(cnt)
  • 처음 넣어준 좌표로부터 시작해서 모든 순회가 끝났을 때(모든 재귀함수를 수행한 후,) return True를 해주는 것이 핵심.
  • 좌표 벗어날 때의 범위 설정 해주는 것 주의
  • 재귀함수 안의 함수의 리턴값이 어떻게 되던간에 마지막 재귀함수의 리턴값만 생각하면 된다.
  • else return False는 안해줘도 상관없다.

bfs

# 최단거리 미로

from collections import deque

# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())

# 2차원 리스트의 맵 정보 입력 받기
grid = []
for i in range(n):
    grid.append(list(map(int, input())))

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

visited = [[False for _ in range(m)] for _ in range(n)]
def bfs(x, y):
    queue = deque([(x, y)])
    visited[x][y] = True
    while queue:
        x, y = queue.popleft()
        if (x, y) == (n-1, m-1):
            break
        print((x,y))
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx<0 or nx>(n-1) or ny<0 or ny>(m-1):
                continue
            elif grid[nx][ny] == 0:
                continue
            else:
                if visited[nx][ny] == True:
                    print('a')
                    if grid[x][y]+1 < grid[nx][ny]:
                        grid[nx][ny] = grid[x][y]+1

                else:
                    print('b')
                    grid[nx][ny] = grid[x][y]+1
                queue.append((nx, ny))
                visited[nx][ny] = True
bfs(0,0)
print(grid)
print(grid[n-1][m-1])
  • 다익스트라 비스무리하게 풀었는데 좀 어렵게 생각했던 것이다.
    다익스트라를 쓰려고 하다보니 해당 노드를 처음 방문하는 경우, 재방문하는 경우로 나누어서 처리해야했다.
  • bfs자체가 시작노드부터 한단계씩 가까운 노드순으로 순회하는 것이기때문에 처음 방문하는 경우에 가장 최단경로로 온 것이다.
  • 그러므로 아래와 같이 처음 방문일때의 경로길이만 반영하는 형태로 하면 훨씬 쉬운 풀이가 된다.
from collections import deque

# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

# 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# BFS 소스코드 구현
def bfs(x, y):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    queue = deque()
    queue.append((x, y))
    # 큐가 빌 때까지 반복하기
    while queue:
        x, y = queue.popleft()
        # 현재 위치에서 4가지 방향으로의 위치 확인
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 미로 찾기 공간을 벗어난 경우 무시
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            # 벽인 경우 무시
            if graph[nx][ny] == 0:
                continue
            # 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))
    # 가장 오른쪽 아래까지의 최단 거리 반환
    return graph[n - 1][m - 1]

# BFS를 수행한 결과 출력
print(bfs(0, 0))

구현 유형

이코테의 게임 문제
백준문제

이코테 책읽었을 때의 코드

약간 이코테 정담 아이디어를 슬쩍 보고 작성한 코드

n, m = map(int,input().split())
x, y, p = map(int, input().split())

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

grid = []
for i in range(n):
    grid.append(list(map(int, input().split())))

visited = [[False for _ in range(m)] for _ in range(n)]
visited[x][y] = True
def move(x, y, p):
    mcnt = 0
    while True:
        fcnt = 0
        for i in range(4):
            print('x,y', (x, y))
            print('i', i)
            if p == 0:
                np = 3
            else:
                np = p - 1

            nx = x + dx[np]
            ny = y + dy[np]
			
            # 맵은 어차피 벽으로 사면이 둘러쌓여 있어서 a는 사실 불필요
            a = (nx<0 or nx>(n-1) or ny<0 or ny>(m-1))
            # 방문한 격자라면
            b = (visited[nx][ny] == True)
            # 벽이라면
            c = (grid[nx][ny]==1)

            if a or b or c:
                p = np # 방향만 바꾸고
                fcnt += 1 
            else:
                x = nx
                y = ny # 위치 바꾸고
                p = np # 방향 바꾸고
                visited[x][y] = True
                mcnt += 1
                break # 옮겨갔으니까 break
        if fcnt==4:
            if grid[x-dx[p]][y-dy[p]] == 1:
                print(visited)
                return mcnt
            x -= dx[p]
            y -= dy[p]

print(move(x, y, p))
  • 해당 방향으로 앞으로 갈때는 x + dx[i] 뒤로 갈때는 x - dx[i]

  • 구현 문제는 문제 이해가 엄청 중요함

  • 모든 경우가 어떻게 되는건지 머릿속으로 시뮬돌려봐야됌

  • 백준풀고 다시보니 이코테 테스트 케이스만 통과.

  • 처음 노드 방문처리하는 것 잊지 말자

  • flag처리를 안해도 되는 이유는 위 코드에서는 방향만 바꾸는 횟수(fcnt)를 따로 세기 때문이다.

기억리셋되고 백준문제 푼 코드

n, m = map(int, input().split())
x, y, pos = map(int, input().split())

grid = []
for _ in range(n):
    grid.append(list(map(int,input().split())))
visited = [[False for _ in range(m)] for _ in range(n)]
cnt = 1
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
visited[x][y] = True

while True:
    for i in range(4):
        flag = False
        if pos == 0:
            pos = 3
        else:
            pos -= 1

        nx = x + dx[pos]
        ny = y + dy[pos]
		
        # 움직일 수 있는 조건이라면
        if grid[nx][ny] != 1 and visited[nx][ny]!=True:
            visited[nx][ny] = True
            x = nx
            y = ny
            cnt += 1
            flag = True # 4번 돌았지만 위치를 옮긴 상황을 기록
            break
    if i == 3:
        if flag==True:
            continue
        elif grid[x-dx[pos]][y-dy[pos]] == 1:
            break
        else:
            x -= dx[pos]
            y -= dy[pos]
print(cnt)
  • for문 4번 돌았지만 마지막 방향에서 움직일 수 있는 경우가 있기때문에 flag로 그런 상황 고려
  • 처음노드 방문처리 & 처음노드고려해서 cnt 1부터 시작 주의

달팽이 문제

  • 구현 문제
  • 좌표만 조작해서 이동한다는 개념
  • 삼각형이 아닌 nxn 어레이라고 생각하면 인덱싱할 때 더욱 쉽다는 점
  • 특정방향으로 한번씩 돌때마다 그 단계의 개수는 한개씩 줄어든다는 점
  • 참고
n = 5
grid = [[-1 for _ in range(n)]  for _ in range(n)]
x = -1
y = n
num = 0
for i in range(n):
    for j in range(n-i):
        if i%3==0:
            x += 1
            y -= 1
        elif i%3==1:
            x -= 1
        elif i %3 == 2:
            y += 1
        num += 1
        grid[x][y] = num

# print(grid)
for i in grid:
    print(i)
profile
중요한 것은 속력이 아니라 방향성

0개의 댓글