# 3052
arr = []

for i in range(10):
  a = int(input())
  arr.append(a%42)

print(len(list(set(arr))))

# 2675
T = int(input())

for i in range(T):
  R, S = input().split()
  R = int(R)
  P = list(S)
  Q = ''
  for j in P:
    Q = Q+j*R
  print(Q)

print(, end ='')으로 풀면 되겠네하고 쉽다고 생각했다가 머리 쥐 나는 줄 알았다.

# 2439 
N = int(input())
for i in range(N):
  print(('*'*(i+1)).rjust(N))

출력할 때 오른쪽 정렬은 .rjust(출력자리수) 왼쪽 정렬은 .ljust(출력자리수)

F = list(input().lower()) # 문자를 소문자열로 받아옴
Q = list(set(F))          # 문자 갯수를 세기 위해서 중복 제거
cnt = 0                   # 가장 많은 문자 갯수 저장
R = []                    # 문자 갯수가 같은 문자 저장

# 가장 많은 문자의 갯수를 구하기 위한 반복문
for i in Q:               
  if F.count(i) > cnt:
    cnt = F.count(i)

# cnt와 중복값을 가진 문자를 R에 저장
for i in Q:
  if F.count(i) == cnt:
    R.append(i)
    
if len(list(set(R))) > 1:
  print('?')
else:
  print(R[0].upper())

맞추긴 했는데 메모리와 시간을 엄청 먹는다. 좀더 빠르게 푸는 방법은 없을까?

2022.01.07

백준 2667 단지 번호 붙이기

#2667 단지번호붙이기
from collections import deque

N = int(input())
arr = [list(map(int,input())) for i in range(N)]
visited = [[False]*N for i in range(N)]  # 한 번 들른 곳은 방문처리

dx = [-1, 0, 0, 1]    # 상하좌우의 좌표를 이용하기 위해서
dy = [0, 1, -1, 0]

R = []  # 단지 내 아파트 숫자를 저장하려는 리스트

def BFS(x,y):
    queue = deque()
    queue.append((x,y)) # (x,y)로 append하면 pop할 때 두 x,y를 한 번에 꺼낼 수 있다
    num = 0             # 단지 내 아파트 숫자 세기
    if arr[x][y] == 1 and visited[x][y] == False:
        num += 1
        visited[x][y] = True
        
    while queue:
        v,b = queue.popleft()
        
        for i in range(4):
            nx = v + dx[i]
            ny = b + dy[i]
            if 0<=nx<N and 0<=ny<N:
                if arr[nx][ny] == 1 and visited[nx][ny] == False:
                    queue.append((nx,ny))
                    visited[nx][ny] = True
                    num += 1
    return R.append(num)

for i in range(N):
    for j in range(N):  # 반복문 두개 돌려서 좌표 (0,0) 부터 (N-1,N-1)까지 확인
        if arr[i][j] == 1 and visited[i][j] == False:
            BFS(i,j)
            
print(len(R))
for i in sorted(R):
    print(i)

deque에 좌표(x,y)를 append 해서 한 번에 꺼내는 것을 몰랐다면 더욱 지저분한 코드가 되었을 것 같다.

return을 해주는 위치랑 nx,ny 범위 지정을 잘못했는데 못 찾아서 한참을 헤맸다.

DFS로 풀 때와 다른점은 좌표의 범위 제한을 while구문 안에 넣은 것과 visited를 사용한 점이다.

숙달되려면 멀었다. 더 많은 관련 문제를 풀어봐야지

2022.01.06

백준 2606 바이러스

## 2606
from collections import deque

N = int(input())
C = int(input())
arr = [[] for i in range(N+1)]        # N+1 해준 이유는 숫자 인덱싱을 맞추려고

for i in range(C):
    a, b = map(int,input().split())
    arr[a].append(b)
    arr[b].append(a)

visited = []        # 방문한 컴퓨터 번호
def BFS(x):
    queue = deque([x])
    visited.append(x)
    
    while queue:
        v = queue.popleft()
        for i in arr[v]:
            if i not in visited:
                queue.append(i)
                visited.append(i)
                
BFS(1)
print(len(visited) -1) # 1번 컴퓨터는 제외

queue는 while 문이 핵심 같다.popleft를 통해서 나온 수를 인덱스로 사용해서 큐에 다시 삽입하고

다시 반복을 통해서 queue를 공백으로 만드는 것이 재귀를 이용하는 DFS와의 차이처럼 느껴진다.

2022.01.04

백준 1012 유기농 배추

# 1012
import sys
sys.setrecursionlimit(10**6)


def DFS(x,y):
    if 0 > x or x >= N or 0 > y or y >= M:           
        return False
    
    if arr[x][y] == 1:         
        arr[x][y] = 0                                  
        DFS(x-1,y)
        DFS(x,y+1)
        DFS(x+1,y)
        DFS(x,y-1)
        return True


T = int(input())    #테스트 케이스
    
for i in range(T):
    M, N, K = map(int, input().split())
    
    arr = [[0]*M for i in range(N)]  # 배추밭의 2차원 배열
    R = 0                            # 배추흰벌레 마리 수
       
    for j in range(K):
        a, b = map(int, input().split())
        arr[b][a] = 1

    for ii in range(N):
        for jj in range(M):
            if DFS(ii,jj) == 1: # 배추밭의 좌표(0,0)부터 끝까지 확인
                R += 1
    print(R)

편법?

import sys
sys.setrecursionlimit(10**6)

서버의 재귀 깊이를 늘려주는 함수를 사용해서 간신히 풀었다.

아무래도 DFS 함수의 재귀로 불러오는 게 너무 많아서 그런 듯하다.

재귀를 줄이고 반복문을 늘리는 함수를 짜 봐야겠다.

BFS(Breadth First Search)란?

BFS란 너비 우선 탐색으로도 불리며 시작 노드부터 가장 가까운 노드들을 방문하고

멀리 떨어진 노드를 나중에 탐색하는 방법이다.

DFS가 하나의 노선을 따라 종점까지 다녀오고 다시 다음 노선의 종점까지 가는 느낌이라면

BFS는 내 친구들을 하나하나 만나고 그후에 내 친구들의 친구들을 만나는걸 반복하는 느낌이다. 

BFS의 장점

- 출발노드에서 목표노드까지 최단경로를 보장한다.

BFS의 단점

- 경로가 매우 길 경우, 많은 기억 공간을 필요하게 된다.

탐색

BFS는 선입선출인 큐(Queue) 자료구조 형태를 가졌기 때문에 우선 탐색 시작 노드를 큐에 삽입과

방문처리를 한다. 그다음 큐에서 노드를 꺼낸 후 노드의 인접 노드 중 방문처리 하지 않은 노드를

모두 큐에 삽입, 방문처리 한다. 위 과정을 반복한다.

파이썬에서는 큐 구조를 사용하기위해 collections의 deque 라이브러리를 사용한다.

from collections import deque

#2667 

N = int(input())
P = [list(map(int,input())) for i in range(N)]

def DFS(x,y):
    global R
    if 0 > x or x >= N or 0 > y or y >= N:
        return False
    
    if P[x][y] == 1:
        R += 1
        P[x][y] = 0
        DFS(x-1,y)
        DFS(x,y+1)
        DFS(x+1,y)
        DFS(x,y-1)
        return True
    return False           # 지워도 됨
        

arr = []                   # 단지 내 아파트 숫자를 저장
R = 0                      # 단지 내 아파트 숫자
for i in range(N):
    for j in range(N):
        if DFS(i,j) == 1:
            arr.append(R)
            R = 0
print(len(arr))
for i in sorted(arr):
    print(i)

DFS(Depth First Search)란?

DFS란 깊이 우선 탐색으로 불리며 그래프 탐색의 한 종류이다.

루트 노드나 지정된 노드에서 시작하여 그 노드의 최대 깊이까지 탐색한 다음

더 이상 탐색 불가능하면 부모 노드로 돌아와 다른 노드로 탐색을 진행한다.

알고리즘 진행 모습은 이렇다.

이처럼 최고 깊이까지 탐색한 다음 더 이상 진행할 곳이 없으면

부모 노드로 돌아와 노드로 탐색을 진행한다.

순서의 2, 5, 9 노드로 순서로 진행하는 것은 조건을 어떻게 주느냐에 따라 다르다.

예를 들어 노드에 주어진 값이 가장 작은 것부터 탐색하거나

큰 값부터 탐색하는지 주어진 조건에 따라 탐색 순서는 바뀔 수 있다.

DFS 알고리즘 문제는 스택자료구조나 재귀 함수를 사용한다.

이때 가장 중요한 점은 방문한 노드를 방문처리하는 것이다.

방문처리하지 않으면 같은 곳을 계속 방문할 가능성이 있다.

최근 DFS와 BFS 자료구조 문제를 풀려고 시도하는데 구현에 어려움이 있어서 

개념을 정리 후에 다시 풀어보려고 작성한 글입니다.