[Python] 백준 2164, 백준 1929, 백준 1012 풀이

새롭게 시작한 라이브 코딩 스터디에서 푼 문제들을 복기해보고자 한다.

1회차: 241006 라이브 코딩 복기

 

1. 백준 2164 : 카드2 

실버4

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

 

문제

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.

출력

첫째 줄에 남게 되는 카드의 번호를 출력한다.

난이도: 실버 2

 

 

나의 풀이

왜 큐인가?

- 긴 파이프 안에 변수를 넣고 조작하는 문제 

- 스택은 한쪽이 막힌 파이프기 때문에 요소들을 끝으로 자유로이 이동시킬 수 없음 

- 큐를 사용해서 조작 & deque로 변수 빼고 넣기 자유롭게 할 수 있음

 

1) 처음 풀었을 때

from collections import deque
n = int(input()) #1부터 n까지의 수를 list에 넣고 
#넣었다 뺏다 하니까 ->큐로
from collections import deque
queue = deque(range(1, n+1)) #1부터 n까지의 큐 만들기 
while len(queue)> 1:
    queue.popleft() #첫번째거 버림
    queue.append(queue.popleft()) #버린거 추가
print(queue[0])

- 가장 앞에 있는 걸 뒤에 추가하는 방식으로 : 가장 직관적인 풀이 

 

2)다시 풀 때

from collections import deque
n = int(input())
queue = deque()

for i in range(1, n+1):
    queue.append(i)
print(queue)
while len(queue)>1:
    queue.popleft()
    queue.rotate(-1)
print(queue[0])

 

- 버린 걸 추가하는 방식 대신 rotate 사용 

- rotate(-1) : 제일 앞에 있는게 제일 뒤로 이동 

 

 

2. 백준 1929 : 소수 구하기 

실버 3

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

풀기 전에 알고 있었던 개념: 에라토스테네스의 채 

1. 소수는 1과 자기 자신으로만 나눠지는 수 

2. 범위 내의 소수를 찾아내는 방법은 단순하게는 전체 범위를 모두 반복하며 소수인지 여부를 판단하는 방법이 있음 

3. 하지만 이 방법은 시간복잡도가 높고 확인해야 할 숫자의 범위가 클 경우에는 타임에러가 발생할 수 있음 

4.에라토스테네스의 채의 핵심 개념 : 소수의 배수들을 제거하여 소수를 남기는 방식

- 소수의 배수는 그 소수의 제곱 이상에서 등장함: n**0.5 범위까지의 숫자만 확인해도됨

-> 3을 예시로 생각했을 때, 2의 배수로 처리된 6을 제거하고 9부터 판단해야함 -> 9는 3의 제곱

- 2부터 시작 (1은 소수가 아님)

- 소수의 배수들을 왜 제거하는가? : 소수의 배수들은 이미 1과 본인 이외에 약수가 존재하기 때문에 소수 자격 이미 박탈

 5. 2부터 n**0.5까지 숫자 반복문 돌면서 나머지가 0인 수가 있다면 소수 아님 

 

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

단순 소수 판별식 활용해서 풀었음 

m,n = map(int, input().split())
for i in range(m, n+1):
    if i ==1:
        continue
    for j in range(2,int(i**0.5)+1):
        if i % j ==0:
            break
    else: 
        print(i)

 

에라토스테네스의 채 활용해서 풀 경우 

def eratosthenes_sieve(m, n):
    sieve = [True] * (n + 1)  # 처음엔 모든 수를 소수라고 가정 (True)
    sieve[0] = sieve[1] = False  # 0과 1은 소수가 아님

    # 2부터 √n까지의 배수를 지움
    for i in range(2, int(n ** 0.5) + 1):
        if sieve[i]:  # i가 소수라면
            for j in range(i * i, n + 1, i):  # i의 배수들은 소수가 아님
                sieve[j] = False

    # m부터 n까지의 소수 출력
    for i in range(m, n + 1):
        if sieve[i]:  # True로 남은 수가 소수
            print(i)

# 입력 예시: m과 n 사이의 소수 출력
m, n = map(int, input().split())
eratosthenes_sieve(m, n)

 

3. 백준 1012 유기농 배추 

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

실버2

 

문제

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.

1	1	0	0	0	0	0	0	0	0
0	1	0	0	0	0	0	0	0	0
0	0	0	0	1	0	0	0	0	0
0	0	0	0	1	0	0	0	0	0
0	0	1	1	0	0	0	1	1	1
0	0	0	0	1	0	0	1	1	1

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.

출력

각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

 

 

전형적인 dfs/bfs 문제 

좌표가 나오면 탐색으로 푸는 걸 고려하자 !

from collections import deque
import sys 
input = sys.stdin.readline

def bfs(maps, x,y):
    #이동시킬 방향 좌표 
    dx= [-1,1, 0, 0]
    dy = [0,0,-1,1]
    #큐 초기화 후 처음 좌표 넣기 
    queue = deque([(x,y)]) #좌표를 넣을 때는 꼭 리스트 사용해주기 , x,y, cnt를 넣는다면 그냥 괄호로 해도됨
    maps[x][y] = 0 #배추 심은 곳도 0으로 바꿔서 방문처리 
    
    while queue:
        x,y = queue.popleft()
        
        for i in range(4):
            nx = x+ dx[i]
            ny = y+dy[i]
            
            if 0<=nx <m and 0<=ny<n and maps[nx][ny] ==1:
                maps[nx][ny] = 0
                queue.append((nx,ny))
t = int(input())
for i in range(t):
    m, n, k = map(int, input().split())
    maps = [[0] * n for _ in range(m)]
    cnt = 0 
    # 0으로만 이루어진 배열 먼저 만들고 k개의 위치 정보 받아 1로 채워줌 
    for _ in range(k):
        x, y = map(int, input().split())
        maps[x][y] = 1

    for i in range(m):
        for j in range(n):  # m이 아니라 n 범위로 수정
            # 1일 경우에만 탐색하고 카운트 올려줌
            if maps[i][j] == 1:
                bfs(maps, i, j) 
                cnt += 1
    print(cnt)

 

헤맸던 부분

- 방문 처리용 배열을 따로 만들려고 했는 걸 그럴 필요 없었음 !

- 0 <= nx <= m - 1 이라는 비교는 nx가 0 이상 m - 1 이하인지를 확인하는 방식으로 의도했지만, 파이썬 논리 연산자에서 이중 비교 연산을 사용할 때 문제가 발생할 수 있음. 0<=nx <m 으로 처리하자