미정

백준에서 처음으로 DFS와 BFS 문제를 접했는데 해설을 자세하게 해볼려고 한다.

문제 링크

1260번: DFS와 BFS

해설

N,M,V = map(int,input().split())

#행렬 만들기
graph = [[0]*(N+1) for _ in range(N+1)]
for i in range (M):
    a,b = map(int,input().split())
    graph[a][b] = graph[b][a] = 1

#방문 리스트 행렬
visited1 = [0]*(N+1)
visited2 = visited1.copy()

#dfs 함수 만들기
def dfs(V):
    visited1[V] = 1 #방문처리
    print(V, end=' ')
    for i in range(1, N+1):
        if graph[V][i] == 1 and visited1[i] == 0:
            dfs(i)

#bfs 함수 만들기
def bfs(V):
    queue = [V]
    visited2[V] = 1 #방문처리
    while queue:
        V = queue.pop(0) #방문 노드 제거
        print(V, end = ' ')
        for i in range(1, N+1):
            if(visited2[i] == 0 and graph[V][i] == 1):
                queue.append(i)
                visited2[i] = 1 # 방문처리

dfs(V)
print()
bfs(V)

1. 행렬 만들기

행렬을 만들 때 자주 사용되는 리스트 컴프리헨션 문법을 사용한다.

graph = [[0]*(N+1) for _ in range(N+1)]
for i in range (M):
    a,b = map(int,input().split())
    graph[a][b] = graph[b][a] = 1

[[0]*(N+1)] 은 N이 3이라면 [[0] * (4)] 이므로 => [[0,0,0,0]]을 출력한다. 
리스트 컴프리헨션을 써주면 [[0,0,0,0], [0,0,0,0], [0,0,0,0], [0,0,0,0]]행렬이 완성된다.

graph =   0 1 2 3 행
	0 0 0 0 0
        1 0 0 0 0
        2 0 0 0 0
        3 0 0 0 0
        열
        
정점의 개수만큼의 행렬을 만들었다면,
이제는 정점 간의 연결을 행렬에 표시해 주어야한다.
만약 '1 2'가 입력된다면 정점1과 정점2가 연결되어있다는 뜻이므로 0을 1로 바꿔준다.

graph[1][2] = graph[2][1] = 1

graph =   0 1 2 3 행
	0 0 0 0 0
	1 0 0 1 0
	2 0 1 0 0
	3 0 0 0 0
	열

2. 방문 리스트 만들기

BFS와 DFS는 스택과 큐를 사용한다. 이때 스택과 큐에 한번 들어갔던 노드는 다시 들어가지 못한다.

즉, 이 노드가 스택과 큐에 들어갔던 적이 있는지 확인할 필요가 있다. 이를 표현하기 위해 정점의 수만큼의 방문 리스트를 만들겠다.

visited1 = [0]*(N+1)
visited2 = visited1.copy()

N이 3이라면, visited1 = [0,0,0,0]
만약 1번 노드가 스택에 들어간 적이 있다면 visited = [0,1,0,0] 이 될 것이다.

3. DFS 함수 만들기 - 재귀 사용

def dfs(V):
    visited1[V] = 1 #방문처리
    print(V, end=' ')
    for i in range(1, N+1):
        if graph[V][i] == 1 and visited1[i] == 0:
            dfs(i)
            
탐색을 시작하는 번호 V부터 탐색을 시작한다.
먼저 V노드가 시작이므로 V를 방문 처리한다. 
예를들어 V=1이라면 위에서 만들어놓은 방문 리스트에서 visited1[1] = 1 로 방문처리하는 것이다.
그러면 visited1 = [0,1,0,0]이 될 것이다.
이는 1번 노드가 스택에 들어간적이 있다는 기록인 것이다.

1번 노드가 방문했으므로 1번 노드를 출력한다.
print(V, end=' ')

이 후 for문을 돌려서 if graph[V][i] == 1로
graph[1][1], graph[1][2], graph[1][3]을 확인해 줄 것이다.
이는 1과 연결된 노드를 찾는 것이다. (위에서 행렬로 연결된 노드들을 1로 표시해두었으므로)

만약 1과 2가 연결돼있다면 graph[1][2] == 1에 True가 될 것이다.
여기서 and visited1[i] == 0으로 2번 노드가 스택에 들어갔던 적이 있는지 확인해주어야 한다.
만약 2번 노드가 스택에 들어간적이 있다면 만들어놓은 방문리스트에서 1값으로 변경되었을 것이다.

즉, 1과 연결된 노드 중 방문기록이 없는 노드를 찾는 코드이다.
if graph[V][i] == 1 and visited1[i] == 0:

1과 연결된 노드 중 방문기록이 없는 노드가 있다면
dfs(i)로 재귀함수를 돌린다.

dfs(2)는 다시 위의 과정을 돌려서 2를 방문처리하고, 2와 연결된 노드를 찾는다.
이렇게 계속 연결된 노드들을 찾아 '깊이우선탐색'을 진행하는 것이다.  

4. BFS 함수 만들기

def bfs(V):
    queue = [V]
    visited2[V] = 1 #방문처리
    while queue:
        V = queue.pop(0) #방문 노드 제거
        print(V, end = ' ')
        for i in range(1, N+1):
            if(graph[V][i] == 1 and visited2[i] == 0):
                queue.append(i)
                visited2[i] = 1 # 방문처리
      
      
bfs는 queue를 이용한다.
탐색 시작 노드 V가 주어진다면
queue = [V] 로 큐에 탐색 노드를 먼저 넣는다.
이 후, 위에서 만들어놓은 방문리스트 visited2[V] = 1로 방문 처리해준다.
V가 1이라면 visited2 = [0,1,0,0]이 될 것이다.
dfs와 같은 원리이다.

이제 while queue: 로 queue에 값이 없을때까지(탐색이 끝날때까지) 반복할 것이다.
먼저 queue.pop(0)을 해준다. 이 코드는 queue에서 0번째 요소를 돌려주고 삭제하라는 것이다.
queue는 선입선출 구조이므로 가장 먼저들어온 0번째 요소부터 빼는 것이다.
그리고 삭제한 요소를 V변수로 돌려받겠다.
위에서 V를 1로 가정했을 때 queue = [1], visited[2] = [0,1,0,0]인 상태이고
여기서 V = queue.pop(0)을 해주면 queue = []이 되고, V = 1이 될 것이다.
1을 뺐으니 1을 출력한다. print(V, end = ' ')

이 후 for문으로 연결된 노드들을 탐색해줄 것이다.
원리는 위에 설명한 dfs와 같다.
V와 연결되고, 방문한 적이 없는 노드가 있다면
큐에 넣어줄 것이다.


bfs과정을 나열해보겠다.
V = 1 // 1번 노드부터 탐색시작
queue = [1] // 방문 노드 저장
visited2[1] = 1 // visited2 = [0,1,0,0]

while문 들어가서,
queue = []
V = 1 // 1출력
for문 들어가서,
노드 1과 2가 연결되고, 노드 2가 방문된적이 없다면
graph[1][2] ==1 and visited2[2] == 0에 해당하므로
queue = [2]
visited2[2] = 1로 방문처리

노드 1과 3이 연결되고, 노드 3이 방문된적이 없다면
queue = [2,3]
visited2[3] = 1로 방문처리
모든 연결 노드 확인 후 for문 반복 끝

queue에 값이 있으므로
while문 탈출 안하고 다시 반복
V = 2 // 2출력
queue = [3]
graph[2][1] == 1 and visited2[2] ==0에 해당하지 않으므로 큐에 다시 넣지 못한다.(2는 1과 연결돼있지만, 1은 이미 큐에 들어간 기록이 있다.)
graph[2][3] == 1 and visited2[2] ==0 역시 마찬가지로 방문기록이 있으므로 false

이 경우 아무것도 추가되지 않고 for문을 빠져나간다.
queue = [3]으로 아직 값이 있으므로 while문 다시 반복
V = 3 
queue = []

5. BFS 함수 더 이해하기

queue는 pop(0)을 통해 먼저 들어온 요소를 뺀다.
선입선출인 큐가 너비우선탐색을 하게하는 핵심이다.

아래와 같이 연결된 노드가 있다고 가정해보자.
(1-2,1-3,1-4,3-5,4-6,6-7 연결)

1 - 2 
  - 3 - 5 
  - 4 - 6 - 7
  
  
queue에는 시작 노드를 먼저 담고 시작한다.
queue = [1]로 시작해서 1을 뺀 후 출력한다.
// queue = []
// 출력: 1
이 후 1과 연결된 2,3,4 가 queue에 담길 것이다.

// queue = [2,3,4]
0 번째 요소 (가장 먼저들어온) 2번 노드를 빼고 출력한다.
// 출력: 1 2
2와 연결된 노드를 확인한다.
2와 연결된 노드가 없다면 추가되지 않는다.

// queue = [3,4]에서
0 번째 요소 3번 노드를 빼고 출력한다.
// 출력: 1 2 3
3과 연결된 노드를 확인한다.
3과 연결된 5가 queue에 담길 것이다.

// queue = [4,5]
0 번째 요소 4번 노드를 빼고 출력한다.
// 출력: 1 2 3 4
4와 연결된 노드를 확인한다.
4와 연결된 6이 queue에 담길 것이다.

// queue = [5,6]
0 번째 요소 5번 노드를 빼고 출력한다.
// 출력: 1 2 3 4 5
5와 연결된 노드를 확인한다.
5와 연결된 노드가 없다면 추가되지 않는다.

// queue = [6]
0 번째 요소 6번 노드를 빼고 출력한다.
// 출력: 1 2 3 4 5 6
6과 연결된 노드를 확인한다.
6과 연결된 7이 queue에 담길 것이다.

// queue = [7]
0 번째 요소 7번 노드를 빼고 출력한다.
// 출력: 1 2 3 4 5 6 7
7과 연결된 노드를 확인한다.
7과 연결된 노드가 없다면 추가되지 않는다.

queue = [] 빈 문자열이므로 while 반복문을 달출한다.

6
10 20 10 30 20 50

4

처음에 이문제는 그냥 중복 제거후 오름차순으로 구현했었다. 
하지만 이 문제의 가장 큰 문제는 증가된 부분 수열이고 이게 이 문제의 가장 큰 힌트였다.

즉, 이 문제는

1. 리스트 내 하나의 수를 기준으로 잡고 그 뒤에 나오는 값들을 비교하면서 오름차순으로 증가되는 수열을 찾는 것이다. 그래서 만약 주어진 값이 [5,1,6,2,7,3,8] 이렇게 있으면 

2. '5'을 기준으로 증가된 수열을 찾는다면 [5,6,7,8] 이 나올 것이고, '1'을 기준으로 잡는다면 [1,2,3] 나올 것이다.

3. 하지만 이렇게 구현한다면 단점이 생긴다.

만약 주어진 값이 [1,3,4,2,3,4] 일 경우 '1'을 기준으로 잡는다면 [1,3,4] 와 [1,2,3,4]가 나올 것이다.  

4. 그래서 이 문제는 DP를 사용해서 풀어야 겠다고 생각을 했고 DP문제는 거의 max(), min()이 나오기 때문에 코드를 작성했다.

-> DP문제는 이전에 계산된 값을 재사용해서 해결하는 방식이고 나는 상향식 접근법을 이용해 for문으로 구현했다. 그러기 위해서는 결과를 저장하는 TABLE이 필요하다. 이걸 나는 dp라는 리스트를 만들었다. 

5. 기준을 잡은 숫자와 그 이전의 숫자의 DP 배열의 값을 비교하여 문제를 풀면된다.

n = int(input())
a = list(map(int, input().split()))

dp = [0] * n 
for i in range(n):
    for j in range(i):
        if a[i] > a[j] and dp[i] < dp[j]:
            dp[i] = dp[j]
    dp[i] += 1

print(max(dp))

코드 설명

입력값 : n = 6

입력값 : a = [10, 20, 10, 30, 20, 50]

dp = 초기값 : [0, 0, 0, 0, 0, 0, 0]

        for문을 다 돌고 난 뒤 : [1, 2, 1, 3, 2, 4]

1. dp 라는 이름의 리스트를 만들고 0으로 초기화를 한다. => dp = [0,0,0,0,0,0]

2. 첫번째 for문으러 값을 지정해준다 .

3. 두번째 for문으로 지정한 값을 이전값들과 비교해준다.

4. if 문에서 a[i] > a[j]는 지정한 값이 이전 값보다 커야하고 dp[i] < dp[j]는 현재 값이 이전 값보다 작으면 현재 dp리스트에 이전 dp 값을 지정한다.

5. for문이 다 돌면 dp[i]에는 0 또는 i 이전의 j 중 dp 값이 큰 dp[j]의 값이 들어 있을 것이다.

6. 그리고 dp[i]에 1을 더해주고 

7. dp값중 가장 큰 값을 출력해준다.

3번 과정의 자새한 풀이

# i = 0일 때 , a[0] = 10, dp = [1, 0, 0, 0, 0, 0]
# i = 1 , a[1] = 20, a[1] > a[0] 이고 dp[1] < dp[0] 이므로 dp = [1, 2, 0, 0, 0, 0]
# i = 2 , a[2] = 10, a[2] > a[0] 은 거짓이므로 dp = [1, 2, 1, 0, 0, 0]

# i = 3,

.

.

.

이렇게 풀면 결국에 dp =  [1, 2, 1, 3, 2, 4이 남게 될 것이고 이 중 가장 큰 값을 출력해주면 된다.

5
55 185
58 183
88 186
60 175
46 155

2 2 1 2 5

N = int(input()) # 전체 사람 수
people = [] # 사람 정보를 받을 빈 list 생성

for _ in range(N): 
    x, y = map(int, input().split()) # 키와 몸무게 입력
    people.append((x,y)) # 그 값을 people 리스트에 추가

for i in people:
    rank = 1 # 초기값은 전부 1
    for j in people:
        if i[0] < j[0] and i[1] < j[1]: # 키와 몸무게 둘 다 커야한다는 and 조건 
            rank += 1 # 위 조건 만족 시 count + 1
    print(rank, end = " ")

문제 속에 답이 다 나와있는 문제였다.

일단, 자신보다 몸무게와 키 모두 큰 사람의 수 + 1이 자신의 덩치 등수가 되는 것을 알 수 있다.

=> ( 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x, y), (p, q)라고 할 때 x > p 그리고 y > q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다. ) 

따라서 입력받은 몸무계와 키를 각각의 사람마다 묶어서 people 리스트에 저장해준 후,

자신보다 몸무게 그리고 키가 모두 큰 사람의 수를 세는 것으로 쉽게 해결할 수 있다. 

1
3
5
7
9
20
31
42
53
64
 |
 |       <-- a lot more numbers
 |
9903
9914
9925
9927
9938
9949
9960
9971
9982
9993

흠... 일단 문제가 너무 이해가 안갔다... 그래서 끄적끄적 코드를 쳐보니 

natural = set(range(1, 10001)) 
generated = set() 

for n in range(1, 10001):
    for j in str(n):
        n += int(j) 
        
    generated.add(n) 
self_num = sorted(natural - generated) 
for i in self_num:
    print(i)

1. 자연수 1~ 10000을 natural set에 넣어준다. 이 친구는 생성자가 없는 숫자를 골라내기 위한 용도로 쓰인다.

2. generated set는 d(n)들을 넣어줄 set이다. 빈방 상태로 시작한다.

3. 첫 번째 for문을 돌린다. 1부터 10000까지 돌리는 이유는, 1부터 10000 사이에서 나올 수 있는 생성자를 빠짐없이 찾기 위해서다. 문제에 있는 것처럼 d(d(d(... n)))수열식으로 꼬리 물면서 찾으면, 시작점에 따라 수열이 달라지는 셀프 넘버의 특성상 코드가 복잡해진다.

어.. 그래... 1부터 10000까지 계산한다고 하자.... generated set에 들어가는 숫자가 중복될 수 있으면,,, 101 같은 경우는 생성자가 2갠데 어떡해? -> 이는 중복을 허용하지 않는 set으로 해결

4.  그럼 이제 두 번째 for문을 보자. n를 str(n)으로 바꿨다!! -> indexing 해서 자릿수 씹고 뜯고 맛보려고...!

그리고 indexing 되어 한 글자씩 뽑힌 j를 int(j)로 형 변환해준다. -> 사칙연산하려고..!... n += int(j) 하려고...!

이렇게 각 자릿수를 원래 자기 수 n에 더해주면서 d(n)이 생성!

5. 이 d(n)은 set에 인자를 넣어주는 add()를 사용해서 generated에 집어넣어 준다.

6. 그럼 이제 1부터 10000까지의 수가 들어있는 natural에서 생성자가 있는 d(n)들을 모조리 빼준다.

출력할 때 순서대로 나와야 하니까 sorted로 정렬도 해준다.

그럼.. 생성자 없는 self_num set이 완성....

for문으로 self_num 하나씩.. 하나씩 출력하면 끝

Mississipi

?

zZa

Z

z

Z

baaa

A

words = input().upper()
unique_words = list(set(words)) 

cnt_list = []
for x in unique_words :
    cnt = words.count(x)
    cnt_list.append(cnt)  

if cnt_list.count(max(cnt_list)) > 1 :  
    print('?')
else :
    max_index = cnt_list.index(max(cnt_list)) 
    print(unique_words[max_index])

문제를 풀 때 입력받은 문자 중 중복되는 값을 제거한 리스트를 변수에 저장하고서 입력받은 문자열의 알파벳 개수를 세는데 이용했다. 빈 리스트를 생성하고서 개수를 센 수를 리스트에 추가하였고 최종적으로 수로 이루어진 리스트에서 가장 큰 값을 출력하였다. 이때, if-else 조건식을 이용해서 가장 큰 값의 개수가 여러 개인 경우 물음표를 출력하도록 했다. 

level

1

baekjoon

0

n = list(str(input()))
if list(reversed(n)) == n:
    print(1)
else:
    print(0)

10 5
1 6 4
3 9 8
2 10 5
1 3 3
2 6 2

1 4 6 2 3 7 10 5 8 9

n, m = map(int, input().split())
box = [i for i in range(1, n+1)]

for i in range(m):
    i, j, k = map(int, input().split())
    box = box[:i-1]+box[k-1:j]+box[i-1:k-1]+box[j:]
print(*box)

0 1 2 2 2 7

1 0 0 0 0 1

2 1 2 1 2 1

-1 0 0 1 0 7

p = [1, 1, 2, 2, 2, 8]
n = list(map(int, input().split()))

for i in range(6):
    print(p[i] - n[i], end=' ')