bright

- idea..

1. 내가 지금 있는 위치에서 1 로 표시된 곳을 찾아 이동해야 한다. 

2. BFS 

from collections import deque 

n,m = map(int,input().split())

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

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


def bfs(x,y):

  queue = deque()
  queue.append((x,y))

  while queue:
    x,y = queue.popleft()

    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]


print(bfs(0,0))

- idea.. 

1. 나랑 붙어 있는 모든 0 찾기.

2. 찾기가 끝나면, 얼음 수 1개 늘리기? 

3. DFS 

n,m = map(int,input().split()) 

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

# 나랑 연결된 노드들을 모두 방문하는 dfs 함수 만들기 
def dfs(x, y):

  if x <0 or y < 0 or x >=n or y >=m :
    return False 
  
  if graph[x][y] == 0 :  # 아직 방문되지 않은 노드라면, 
    
    graph[x][y] = 1      # 방문처리 

    dfs(x-1,y)
    dfs(x+1,y)
    dfs(x,y-1)
    dfs(x,y+1)

    return True 
  return False 

cnt= 0 

for x in range(n):
  for y in range(m):
    if dfs(x,y) == True:  # 한 번 True를 뱉고, 함수 내부에서 연결된 모든 노드에 대한 처리가 끝난다. 
      cnt += 1 

print(cnt )

1. DFS  : 깊이 우선 탐색 , 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘.  시간복잡도는 O(N) 

- 인접 행렬 방식  ( 잘 사용 안 함 ) 

: 연결된 것들을 단순지 2차원 배열로 표현한다.  찾는 속도가 빠르지만 크기가 커지면 메모리를 많이 차지함. 

graph = [[] for _ in range(3)]

graph[0].append((1,7))
graph[0].append((2,5))

graph[1].append((0,7))

graph[2].append((0,5))

print(graph)

결과 : [[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]] 

- 인접 리스트 방식  ( 주로 사용 ) 

나와 연결된 것들을 나열한 리스트로 표현한다. 찾는 속도가 늘지만 메모리 효율성이 높다. ( 필요한 정보만 저장하기 때문에 ) 

다음과 같이 재귀함수를 사용하여 구현 가능하다. 

def dfs( graph, v, visited ):

  visited[v] = True 
  print(v, end=' ')

  for i in graph[v]:       # 나랑 연결된 것 중에서 
    if not visited[i]:     # 방문하지 않은 곳이 있다면 
      dfs(graph,i,visited) # 방문한다. 


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

visited = [False]*9 

dfs(graph,1,visited)

결과 : 1 2 7 6 8 3 4 5 

2. BFS : 너비 우선 탐색 , 가까운 노드 부터 탐색하는 알고리즘. 시간복잡도는 O(N) 

큐 자료구조를 이용하여 구현한다. 

from collections import deque 

def bfs(graph, start, visited ):
  queue = deque([start])
  visited[start] = True 

  while 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,8],
  [1,7],
  [1,4,5],
  [3,5],
  [3,4],
  [7],
  [2,6,8],
  [1,7]
]

visited = [False]*9
bfs(graph, 1, visited )

결과 : 1 2 3 8 7 4 5 6 

n = int(input()) # 회의의 수 

data=[]
for i in range(n):
  data.append(list(map(int,input().split())))   # [ 시작시간, 끝나는 시간 ]

data=sorted(data, key = lambda x: (x[1],x[0]) )

cnt= 0
m = 0

for meet in data:
  if meet[0] >= m : 
    cnt += 1 
    m = meet[1]

print(cnt)

step1) 가장 빨리 끝나는 순서로 정렬한 수, 시작 시간 별로 정렬한다. 

step2) 제일 처음으로 , 가장 빨리 끝나는 강의가 포함된다. 

step3) 그 이후로는, 앞의 강의가 끝나는 시간에 가장 가깝게 시작되는 강의를 배치하고 그 강의 끝에 다시 가장 가까운 강의를 배치한다. 

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

1. 정의 

매 순간 최적이라고 생각되는 것을 선택하여 최적 해에 도달하는 기법. 

2. 속성 

- greedy choice propoerty   :  앞의 선택이 이후에 영향을 주지 않음 .

- optimal substructure         :  문제 전체에 대한 최적 해가 부분 문제에서도 최적 해를 만족해야 함. 

3. 대표 예제 

1)  분할 가능한 배낭 문제 ( Fractional knapsack problem ) 

     풀이 방법 :  단위 무게당 값어치가 가장 큰 것 부터 가방에 넣는다. 

                        <--> Dynamic Programming의 '0-1 Knapsack Problem)이랑 차이! 

2)  교실 할당 문제 ( Activity-Selection Problem )  : 한정된 교실 내에 최대 수업을 배정하자. 

     풀이 방법 : 종료 시간이 가장 빠른 수업을 배치하고 이와 겹치지 않는 나머지 수업을 배치함. (  O(n)  ) 

3)  Huffman Coding :  그리디 알고리즘을 사용해서 데이터를 압축하는 기법. 

     풀이 방법 : 문자가 나오는 빈도에 따라 암호화 비트 수를 달리한다. 높은 빈도의 문자열은 짦게, 낮은 빈도의 문자열은 길게. 

                      문자열이 길 수록 더욱 압축률이 좋다. ( O(nlogn)  )