바다에 퐁당 Ꙭ̮ ꉂ ◡̈⋆*

https://www.acmicpc.net/problem/11660

👀👉 구간 합 기본 개념 및 전략

Input

표의 크기 N(NxN), 합을 구해야 하는 횟수 M(아주 큼)

둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다

다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어짐

ex. 
4 3
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
2 2 3 4
3 4 3 4
1 1 4 4

output

(x1, y1)부터 (x2, y2)까지 합, 총 M개 (각 줄에 하나의 값, M줄)

ex. 

27

6

64

문제 풀이

1. 단순한 구간 합으로 ,,,, 단순 비효율적으로 => 시간 초과

#시간초과

import sys

[N, M] = list(map(int, sys.stdin.readline().split()))
inputs = []
outputs = []
for i in range(N+M):
    if i < N:
        inputs.append(list(map(int, sys.stdin.readline().split())))
    else:
        outputs.append(list(map(int, sys.stdin.readline().split())))

sum_lst = [[0 for _ in range(N)] for _ in range(N)]  # [[0]*N]*N
max_y = max([x[3] for x in outputs])
sums = 0

for y in range(max_y):
    for x in range(N):
        sums += inputs[y][x]
        sum_lst[y][x] = sums

for [a, b, c, d] in outputs:
    if a==c and b==d:
        print(inputs[c-1][d-1])
        continue
    elif a==1 and b==1:
        print(sum_lst[c-1][d-1])
        continue
    elif a>=2 and b==1:
        print(sum_lst[c-1][d-1] - sum_lst[a-2][-1])
        continue
    else:
        f_sum = 0
        for t in range(a-1, c):
            f_sum += sum_lst[t][d-1] - sum_lst[t][b-2]
        print(f_sum)

2. 합 배열과 구간 합의 변용 (중복처리 중요)

문제에 따른 조작적 정의

- 합 배열 :

• 단순히 1번 원소부터 특정 원소까지 다 더한 합이 아니라, 처음부터 직사각형 형태의 합으로 구함
• 점화식의 초항처럼, x=0, y=0일 때의 가장자리 원소를 별도로 구해줌 (base)
• 가장자리 원소(x,y)까지 직사각형 형태의 합 = (x-1까지 직사각형) + (y-1까지 직사각형) - ((x-1, y-1)까지 직사각형)

- 구간 합: 직사각형 형태로 도출될 수 있도록 구함

• (x2,y2)에서 합 배열의 원소 - (x1-1, y2)에서 합 배열의 원소 - (x2, y1-1)에서 합 배열의 원소 + (x1-1, y1-1)에서 합 배열의 원소

import sys

[N, M] = list(map(int, sys.stdin.readline().split()))
inputs = []
outputs = []
for i in range(N+M):
    if i < N:
        inputs.append(list(map(int, sys.stdin.readline().split())))
    else:
        outputs.append(list(map(int, sys.stdin.readline().split())))

sum_lst = [[0 for _ in range(N)] for _ in range(N)]  # [[0]*N]*N
max_y = max([x[3] for x in outputs])

#default setting
sum_lst[0][0] = inputs[0][0]
for x in range(1,N):
    sum_lst[0][x] = sum_lst[0][x-1] + inputs[0][x]
    
for y in range(1,max_y):
    sum_lst[y][0] = sum_lst[y-1][0] + inputs[y][0]


for y in range(1, max_y):
    for x in range(1, N):
        sum_lst[y][x] = sum_lst[y-1][x] + sum_lst[y][x-1] - sum_lst[y-1][x-1] + inputs[y][x]

    
for [x1, y1, x2, y2] in outputs:
    if x1 == x2 and y1==y2:
        print(inputs[x1-1][y1-1])
    elif x1>=2 and y1 >=2:
        print(sum_lst[x2-1][y2-1] - sum_lst[x1-2][y2-1] - sum_lst[x2-1][y1-2] + sum_lst[x1-2][y1-2])
    elif x1==1 and y1>=2:
        print(sum_lst[x2-1][y2-1] - sum_lst[x2-1][y1-2])
    elif x1>=2 and y1==1:
        print(sum_lst[x2-1][y2-1] - sum_lst[x1-2][y2-1])
    else:
        print(sum_lst[x2-1][y2-1])

구간 합 개념

: 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 (가능한 케이스 개수가 극단적으로 많을 경우 특히!)

*핵심: 합 배열 S의 정의

S[i] = A[0] + A[1] + A[2] + .... A[i-1] + A[i]

=> 기존 배열의 일정 범위의 합을 구하는 시간 복잡도: O(N)

=> A[i]~A[j]까지 배열 합: 최악은 i가 0이고 j가 N이므로.

<=> 합 배열을 미리 구해 놓으면 : O(1)로 감소

구현 공식: S[i] = S[i-1](재귀느낌) + A[i](특정 원소)

=> 이것을 기본으로, 문제에 따라 다양한 변용!

구간 합 구현

구현 공식: S[j] - S[i-1]

=> 이것을 기본으로, 문제에 따라 다양한 변용!

https://youtu.be/O514yiWg8YE

https://www.acmicpc.net/problem/17298

1. 문제 개요

1.1 Input

N (ex. 9)

크기가 N인 수열 A (ex. 10 1 2 3 11 4 5 6 12)

1.2 Output

A의 각 원소에 대한 오큰수 배열(*오큰수 NGE(I): 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수)

(ex.  [11,2,3,11,12,5,6,12,-1])

2. 문제 풀이

2.0 귀찮은 백준 입력 세팅: 여러 줄을 입력으로 받는다 (for문 활용 + sys.stdin.readline())

import sys

for y in range(2):
    if y == 0:
        n = int(sys.stdin.readline())
    else:
        inputs = deque(map(int, sys.stdin.readline().split()))

2.1 진짜 단순하게 하나씩: O(n^2)

from collections import deque

answer = deque()
for t in range(n):
    now = inputs.popleft()
    for i in inputs:
        if i > now:
            answer.append(i)
            break
        else:
            continue
    if len(answer) < t+1:
        answer.append(-1)

print(*answer)

Tip: 리스트 내 원소만 출력하고 싶으면, print(*리스트)

2.2 reverse

탐색 문제 풀이 시 input과 output의 관계(경향)을 잘 살피고

• reverse 탐색 / 양방 탐색 등의 방법도 고려해야 함
• 발상의 전환! 반대 방향으로 탐색하면 더 효율적이지 않을까? => 본 문제에서는 여전히 O(n^2)

2.3 O(n^2) => O(n)으로 효율화 필요함! 

• for 문을 한 번만 쓰는 방법,, + 이미 오큰수 구한 원소는 고려 대상에서 제외하는 거,,
• 리스트 내 원소 i는 순차적으로 한 번씩 탐색 (유일한 for문)
• answer = [-1] * n
• stack!! => 오큰수를 찾지 못한 원소의 index를 stack에 저장해두고, 완료된 것은 지움으로써, 당장 필요한 원소만을 추리는 기능
  • stack = [0] 으로 시작 (base case에 대한 사전 처리)
  • while 현재 탐색 중인 i가 stack의 top보다 크면, i는 top의 오큰수가 됨! (이하이면 pass)
  • stack에서 top을 pop (이미 오큰수 구하였으므로 제거) & top의 Index 위치에 해당하는 answer의 value에 오큰수를 저장
  • while 문 끝나면 i가 stack에 append

for y in range(2):
    if y == 0:
        n = int(input())
    else:
        inputs = list(map(int, input().split()))

answer = [-1] * n
stack = [(0)]

for i in range(1, n):
    if inputs[stack[-1]] >= inputs[i]:
        pass
    else:
        while stack and (inputs[stack[-1]] < inputs[i]):
            answer[stack[-1]] = inputs[i]
            stack.pop()
    stack.append((i))
print(*answer)

Tip: stack 저장 대상에 index만 있을 수 있음!

Tip: 반복문에서 pass VS continue

Tip: while stack and 조건: 해당 조건문이 stack이 False인 상태에서 에러 발생!

스택 Stack

1. 마지막에 넣은 것이 - 먼저 나온다
2. stack의 top: 삽입과 삭제가 일어나는 위치
3. s.append(data): top 위치에 새로운 데이터 삽입
4. s.pop(): top 위치의 현재 데이터를 삭제하고 확인
5. s[-1]: top 위치의 현재 데이터를 단순 확인

• DFS: 깊이 우선 탐색
• 백트래킹 종류
• 재귀 알골과 일맥상통

큐 Queue

1. 먼저 들어온 것이 - 먼저 나간다
2. 파이썬에서 deque를 이용하여 큐를 구현 (import collections)
3. stack의 top과 달리, rear(가장 끝)와 front(가장 앞)가 있음
4. s.append(data): rear에 새로운 데이터 삽입
5. s.popleft(): front 부분의 데이터를 삭제하고 확인
6. s[0]: 큐의 맨 앞(front) 데이터 확인

• BFS: 너비 우선 탐색
• 우선순위 큐: 값이 들어간 순서와 상관 없이 우선순위가 높은 데이터가 먼저 나옴. ⇒ front에 항상 최댓값 또는 최솟값
  • 힙(heap)을 이용해 구현.

https://youtu.be/JwOFYxirPPU

https://school.programmers.co.kr/learn/courses/30/lessons/43163

문제 개요

rule
1. 한 번에 '한 개의 알파벳'만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

input
- begin 단어
- target 단어
- words 단어의 집합

*각 단어는 알파벳 소문자로만 이루어져 있습니다.
*각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
*words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
*begin과 target은 같지 않습니다.

output
최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지의 값.
*변환할 수 없는 경우에는 0를 return

ex)
input: "hit" / "cog" / ["hot", "dot", "dog", "lot", "log", "cog"]
output: 4
"iii", "jjj", ["iij", "jjj", "iji", "jij"]

BFS + Depth

from collections import deque

def qualify(now, word):
    no = list(now)[:]
    wor = list(word)[:]
    for x in now:
        if x in word:
            if (x in no) and (x in wor):
                no.remove(x)
                wor.remove(x)
    if (len(no)==1) and (len(wor)==1):
        return True
    else:
        return False

def solution(begin, target, words):
    words.append(begin)
    queue = deque()
    queue.append(begin)
    visited = [0]*len(words)

    for x in words:
        if x == begin:
            visited[words.index(x)] = 1
    if target not in words:
        return 0
    while queue:
        now = queue.popleft()
        for idx, word in enumerate(words):
            if qualify(now, word) and (visited[idx]==0):
                queue.append(word)
                visited[idx] = visited[words.index(now)] + 1
            answer = visited[words.index(target)]
            if answer != 0:
                return answer-1

    if answer == 0:
        return 0

• 게임맵 최단거리 로직과 비슷했다
• BFS + Depth
• 가능한 다음 단어 찾는 qualify 함수 추가
• begin의 단어가 words 리스트에 포함될 경우에 대한 별도 처리 필요!!! (처음 에러 이유)
• 하지만 위 코드 역시 더 간결하게 정리될 필요성이 있다. 다시 복습해야지..

https://school.programmers.co.kr/learn/courses/30/lessons/1844

문제 개요

게임 맵 최단거리

*각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리
*캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동
*게임 맵을 벗어난 길& 검은 부분은 갈 수 없습니다
*상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다

input
maps: 게임 맵의 상태
*n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열
*n, m 모두 1이상 100이하 자연수
*n, m모두 1인 경우는 없음.
*0은 벽이 있는 자리, 1은 벽이 없는 자리

내 캐릭터 위치 초깃값: (1,1) == 게임맵 좌측 상단
상대 캐릭터 초깃값: (n,m) == 게임맵 우측 하단

output
상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값
상대 팀 진영에 도착할 수 없을 때는 -1

1) BFS로 구현 + 효율성 최하

from collections import deque

def solution(maps):
    n = len(maps[0]) #가로
    m = len(maps) #세로
    answer = []
    queue = deque()
    queue.append(((1,1), [(1,1)]))
    
    while queue:
        (a,b), route = queue.popleft()
        neighbor = [(a+1,b), (a, b+1), (a-1, b), (a, b-1)]
        for (x,y) in neighbor:
            if (1<=x<=n) and (1<=y<=m) and ((x,y) not in route) and (maps[y-1][x-1] == 1):
                temp = route + [(x,y)]
                if (x==n) and (y==m):
                    answer.append(len(temp))
                else:
                    queue.append(((x,y), temp))        
    if not answer:
        return -1
    else:
        return min(answer)

• 가능한 neighbor을 추려내어 queue에 저장
• 각 노드마다 자신에게 도달하기까지 거쳐야 하는 visited를 temp를 활용하여 모두 저장
• 노드가 도착지점이 되었을 때 answer에 visited의 length를 저장 후 그 가운데 min을 구함
  → 아예 불필요한 절차. (무조건 첫번째 값이 answer가 되기 때문에 바로 return하면 됨)

2) BFS로 구현 + 효율성 하

from collections import deque

def solution(maps):
    n = len(maps[0]) #가로
    m = len(maps) #세로
    answer = 0
    queue = deque()
    queue.append(((1,1), [(1,1)]))
    
    while queue:
        (a,b), route = queue.popleft()
        neighbor = [(a+1,b), (a, b+1), (a-1, b), (a, b-1)]
        for (x,y) in neighbor:
            if (1<=x<=n) and (1<=y<=m) and ((x,y) not in route) and (maps[y-1][x-1] == 1):
                if (x==n) and (y==m):
                    answer = len(route)+1
                    return answer
                else:
                    temp = route + [(x,y)]
                    queue.append(((x,y), temp))
                    
                             
    if not answer:
        return -1

• min 절차 제외하고 answer 나오자마자 바로 return.
• 그렇다고 answer를 visited의 length로 구할 수 없음.
  answer에서 원하는 '방문 노드'와 BFS에서의 'visited'의 기능이 다르기 때문.
  → 각 경로의 vistied가 아니라, 큐 생성 시 제외할 노드를 가리기 위함.
• 여전히 효율성 0점인 이유는?
  1. 각 노드마다 visited를 별도로 구해서 저장하는 게 최악의 비효율.
  2. '노드가 도착지점이 되자마자' 그것이 거쳐 온 노드 개수가 바로 answer가 됨. 이 지점을 활용해야 하는데!
  3. 경로마다 거쳐 온 노드 개수가 다른데 이건 BFS의 Depth를 활용하면 된다!

→ visited 기능을 구현하면서 + BFS의 Depth를 구하는 방법은?

3) BFS로 구현 + Depth 활용 + 효율성 최상 ⭐⭐⭐

from collections import deque

def solution(maps):
    n = len(maps[0]) #가로
    m = len(maps) #세로
    answer = 0
    queue = deque()
    queue.append((1,1))
    
    while queue:
        a,b = queue.popleft()
        neighbor = [(a+1,b), (a, b+1), (a-1, b), (a, b-1)]
        for (x,y) in neighbor:
            if (1<=x<=n) and (1<=y<=m) and (maps[y-1][x-1] == 1):
                    queue.append((x,y))
                    maps[y-1][x-1] = maps[b-1][a-1] + 1
                                 
    if maps[m-1][n-1] == 1:
        return -1
    else:
        return maps[m-1][n-1]

• 명시적인 visited 리스트는 없지만 그 기능을 하는 것이 if maps[y-1][x-1] == 1 조건
  원래 0이면(막혀 있으면) 로직 상 0 초과의 값을 가질 수 없음
  1이면 '뚫려 있지만' '아직 방문된 적 없다'를 의미함
  1 초과 값이면 '방문된 적 있다' & 해당 값은 '나를 방문하기까지 거쳐야 하는 노드 개수'를 의미함.
• BFS의 depth는 maps[y-1][x-1] = maps[b-1][a-1] + 1
  '직전 위치의 값에 +1' 한 값으로 갱신

이와 별개로, BFS 구현 시 주의해야 하는 점. (특히 효율성)

- 혹시 본인의 코드가 방문체크를 큐에서 꺼낼 때 하고있는건 아닌지 확인해보세요.
방문체크를 큐에 넣을 때 해야 효율성이 통과됩니다. 그 이유는 만약 꺼낼 때 방문체크를 하게되면, 하나의 블럭을 꺼내서 통로를 탐색할 때, 이미 큐에 들어있는 블럭을 또 큐에 넣을 수도 있기 때문입니다.

- https://school.programmers.co.kr/questions/23794

https://school.programmers.co.kr/learn/courses/30/lessons/87946

문제 개요

input
k: 현재 피로도 (1이상 5000이하 자연수)
2차원 배열 dungeons: [["최소 필요 피로도", "소모 피로도"], [],...]
*"최소 필요 피로도" >=  "소모 피로도"
*각 값은 1이상 1000이하 자연수
*dungeons 내 원소 중복 가능.
ex) [[80,20],[50,40],[30,10]]

output
유저가 탐험할 수 있는 최대 던전 수
*k값이 0이상일 때까지 반복.

배열의 문제.
어떻게 배열해야 최대한 많은 개수의 던전을 탐험할 수 있을까.

구현 아이디어

BFS (queue 활용)

https://lets-hci-la-ai-withme.tistory.com/51

• 시작정점을 default((k, []))로 고정하고
  BFS 기반으로 - for문 통해 그다음 노드를 선택(단, 조건 충족하는 것만 queue에 인큐)
  
  
• graph는 주어진 2차원 배열 dungeons 사용
• node(첫 시작)을 (k, [])로 지정함.
  • k: (현재 업데이트된) k값
  • [] : visited 역할을 하는 'route'. 어떤 노드를 거쳤는지 노드 인덱스 남기는 리스트. default는 빈 리스트.
• queue 생성 필수: queue = deque() 
• while queue
• 중심 축(매번 업데이트되는 시작 정점)은 queue에서 popleft한 것. (k, route)
  • 그 안에서 for문으로 처리
    • 그다음 탐색할 노드(두 가지 조건 충족 )를 queue에 저장하거나
    • 조건 충족 안 할 경우, max 활용하여 answer 업데이트

from collections import deque

def solution(k, dungeons):
    answer = -1
    queue = deque()
    queue.append((k, []))

    while queue:
        k, route = queue.popleft()
        for i in range(len(dungeons)):
            a, b = dungeons[i]
            if (k>=a) and (i not in route):
                temp = route + [i]
                queue.append(((k-b),temp))
            else:
                answer = max(answer, len(route))

    return answer

좋은 아이디어

복습복습복습!

그래프 탐색

하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것

-> 두 점을 연결하는 길이 있는가? 이를 확인하기 위해 하나씩 방문. (특정 도시에서 다른 도시로 갈 수 있는가? 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는가?)

너비 우선 탐색(BFS, Breath-First Search)

루트 노드(or 임의의 노드)에서 시작해서 '인접한' 노드를 먼저 탐색하는 방법

1. 의미

• 가까운 것부터.
• 깊게(deep) 탐색하기 전에 넓게(wide) 탐색.
• (가중치가 동일할 때) 두 노드 사이의 최단 경로를 찾거나, 혹은 임의의 경로가 있는지 확인하고 싶을 때
  • 지구상 모든 친구 관계를 '그래프'로 표현한 후 A와 B 사이에 존재하는 경로를 찾는 경우
    • BFS: A와 가장 가까운 관계부터 탐색 <-> DFS: 모든 친구 관계를 다 살펴봐야 할지도...
    • 그러나 BFS가 DFS보다 좀 더 복잡한 경향 O

2. 특징

• 복잡해,, 좀 어렵지?
• 재귀적으로 동작하지 않음
• 어떤 노드를 방문했었는지 여부를 반드시 check해야 함. (그렇지 않으면 무한루프 가능 O)
  • BFS 방문 노드를 큐(Queue)에 차례로 저장, 하나씩 다시 꺼낼 수 있도록.
  • 큐는 선입선출(FIFO): 먼저 들어간 게 먼저 나온다.
• Prim, Dijkstra 알고리즘과 유사.

3. 과정

1) 시작 정점에서 깊이가 1인 모든 노드 방문

• 방문할 때마다 해당 원소가 enqueue
• 시작 정점은 dequeue

2) 깊이가 2인 모든 노드 방문

• 어떻게 보면, 시작 정점이 Queue의 첫번째 원소로 바뀐 셈.
• 이때 Queue에서 해당 원소가 dequeue됨. 
• 바뀐 원소에서 깊이가 1인 걸 탐색하고, 만약 Queue에 이미 저장되어 있는 원소라면 pass.

3) 깊이가 3인....

4) 더 이상 방문할 곳이 없으면(큐가 소진될 때) 탐색 종료

4. 구현

• deque 라이브러리를 활용, 큐.
• 시간 복잡도는 O(N) (대체로 DFS보다 BFS가 우수)

1️⃣ 탐색 시작 노드 정보를 큐에 삽입하고 *방문 처리합니다.
2️⃣ 큐에서 노드를 꺼내 방문하지 않은 인접 노드 정보를 모두 큐에 삽입하고 방문 처리합니다.
3️⃣ 2번의 과정을 더 이상 수행할 수 없을 때까지 반복합니다.

여기서 *방문 처리란 탐색한 노드를 재방문하지 않도록 구분하는 것입니다. 즉, 큐에 한 번이라도 삽입된 노드를 다시 삽입하지 않도록 체크하는 것이죠.

from collections import deque

def bfs(graph, node, visited):
	# 그래프 탐색
    # node는 시작 정점의 default
    # visited는 graph의 node 개수만큼 False로 채워진 리스트
    queue = deque([node])
    visited[node] = True #방문 node에 방문 처리
    
    while queue:
    	# queue가 완전히 빌 때까지 반복
        v = queue.popleft() #선입선출
        print(v, end = '')
        for i in graph[v]:
        	if not (visited[i]):
            queue.append(i)
            visited[i] = True

graph = [
    [],
    [2, 3],
    [1, 8],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7, 8],
    [6, 8],
    [2, 6, 7]
]

그래프 표현: 노드 간의 연결 정보는 위와 같이 2차원 배열을 통해 표현할 수 있습니다.

즉, 리스트 내 인덱스는 노드 번호를 의미하고 각 인덱스에 해당하는 원소에 해당 노드에 인접한 노드 번호가 담겨 있습니다.

# 노드별로 방문 정보를 리스트로 표현
visited = [False] * 9

# 정의한 BFS 메서드 호출(노드 1을 탐색 시작 노드로 설정)
bfs(graph, 1, visited)


#>>> 1 2 3 8 4 5 6 7

*참고 및 인용

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

https://heytech.tistory.com/56

https://school.programmers.co.kr/learn/courses/30/lessons/42842

문제 개요

카펫의 패턴
가장자리(테두리) 1줄: 갈색
나머지 중앙: 노란색

input
본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow

ex) 10, 2
*brown: 8 이상 5,000 이하
*yellow: 1 이상 2,000,000 이하

output
[카펫의 가로, 세로 크기] ex) [4,3]
*가로>=세로
*즉 두 값 중 큰 것을 가로로 세우면 됨.

나의 풀이

def solution(brown, yellow):
    x = int((brown-4)*(1/2))
    for i in range(x-1, int(x*(1/2)-1), -1):
        if (i+2)*(x-i+2) == brown+yellow:
            return [i+2, x-i+2]

후기:

같은 레벨2이지만 그저께 푼 문제와 이번 문제 간 편차가 아주 크다..

레벨1 만큼 간단했던 문제!

결론: 레벨2인데 많이 어려웠다 !!!!ㅜㅜ

재귀는 아직 나에게 익숙하지 않았고 + 소수 찾는 아이디어도 익혀야했다. (에라토스테네스의 체 등.)

덕분에 순열 알고리즘도 공부했고, 소수 찾기 유형은 앞으로 껌이 될 예정🤩 매일매일 재귀랑 더 친해지는 중

사실 재귀 알골 대신 훨씬 효율 좋은 파이썬 모듈(itertools-permutations)이 있는데,

배운 것 적용도 해보고 모듈 의존적이지 않기 위하여 두 가지 방식 각각 시도해보았다

https://school.programmers.co.kr/learn/courses/30/lessons/42839

문제 개요

input
숫자가 적힌 문자열 numbers
*길이 1 이상 7 이하인 문자열
*각 숫자는 0~9
*"013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다

return
흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지, 소수 개수

EX
"17" -> 3
"011" -> 2

Idea

• 순열 구하는 방법(1. permutations 모듈 2. 재귀) : 👉 https://lets-hci-la-ai-withme.tistory.com/47
• 소수 구하는 방법:👉 https://velog.io/@cjy0029/소수-구하는-방법 
  • 소수에는 1 미포함, 2,3,... 포함
  • N의 소수 판별: 2부터 N-1까지 루프를 돌면서 나눠보는 방법(나머지가 없을 때)
    • 비효율적
  • "어떤 소수도 N의 제곱근보다 큰 수로 나눠지지 않는다는 규칙이 있다."
  • 에라토스테네스의 체
    • 2부터 순회를 하면서 2의 배수를 모두 지워주고, 3부터 순회를 하면서 3의 배수를 모두 지워주고, 4는 이미 지워졌으니 패스하고, 5의 배수를 지우고..
    • 주어진 수의 제곱근까지만 확인해보면 끝난다.

1. python itertools-permutations 활용

from itertools import permutations
def solution(numbers):
    nums = []
    for i in range(len(numbers)):
        nums += [int(''.join(x)) for x in list(permutations(numbers, i+1))]
    
    answers = []
    answers += [x for x in nums if (x in [2,3])]
    for x in nums:
        sqrt = int(x**(1/2))
        for i in range(1,sqrt):
            if x % (i+1) != 0:
                if i+1 == sqrt:
                    answers.append(x)
                continue
            else:
                break
    nums = len(set(answers))
    return nums

2. 재귀 알골 이용

def solution(numbers):
    answers = []
    def permutation(numbers, r):
        used = [0 for _ in numbers]
        def generate(chosen, used):
            if len(chosen) == r:
                chosen = int(''.join(chosen))
                if (chosen in [2,3]) and (chosen not in answers): #2,3은 sqrt값이 1이므로 이하 for문이 실행되지 않음
                    answers.append(chosen)
                
                sqrt = int(chosen**(1/2))
                for i in range(1, sqrt):
                    if chosen % (i+1) != 0:
                        if (i+1 == sqrt) and (chosen not in answers):
                            answers.append(chosen)
                            break
                        continue
                    else:
                        break
                return

            for i in range(len(numbers)):
                if not used[i]:
                    chosen.append(numbers[i])
                    used[i] = 1
                    generate(chosen, used)
                    used[i] = 0
                    chosen.pop()

        generate([], used)

    for i in range(len(numbers)):
        permutation(numbers, i+1)
    answer = len(answers)
    return answer

• append 하기 전, 중복 제거 필요
•  '구분자'.join(리스트)
  • map(''.join, 리스트)로 처리하면 빠름
• 순열 알고리즘 내에서, 모든 단어를 리스트에 저장하는 것이 아니라, 소수인 것만 filter 해서 저장 ←이때 에라토스테네스의 체