bright

다음 2주간 목표( ~ 10/14 ) : silver 1 으로 올라가기.. 

solved.ac/problems/level/1

# 3003: 킹, 퀸, 룩, 비숍, 나이트, 폰

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

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

# 3046: R2

r1,s = map(int,input().split())
r2 = 2*s - r1 

print(r2)

# 5337: 웰컴

print(".  .   .") 
print("|  | _ | _. _ ._ _  _") 
print("|/\|(/.|(_.(_)[ | )(/.")

# 5338: 마이크로소프트 로고

print("       _.-;;-._")
print("'-..-'|   ||   |")
print("'-..-'|_.-;;-._|")
print("'-..-'|   ||   |")
print("'-..-'|_.-''-._|")

# 1000: A+B

a,b = map(int,input().split())

print(a+b)

# 1001: A-B

a,b = map(int,input().split())

print(a-b)

# 1271: 엄청난 부자2 

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

print(n//m)
print(n%m)

# 1550: 16진수 

print(int(input(),16))

# 2338: 긴자리 계산

a = int(input())
b = int(input())

print(a+b)
print(a-b)
print(a*b)

# 2475: 검증수 

n = list(map(int,input().split()))
sum = 0 
for i in n:
  sum += i*i

print(sum%10)

# 2557: Hello world! 

print("Hello World!")

# 2558: A+B -2

a = int(input())
b = int(input())

print(a+b)

# 2845: 파티가 끝나고 난 뒤

l,p = map(int,input().split())
data = list(map(int,input().split()))

for i in data:
  print( i - l*p, end=' ')

# 2914: 저작권

a, i = map(int,input().split())

print( a*(i-1)+1 )

팰린드롬 : 앞 뒤가 똑같은 문자열. 

주어진 문자열이 팰린드롬인지 확인할 것. 대소문자 구분 x 영문자와 숫자만을 취급. 

ex ) 

INPUT = "A man, a plan, a canal: Panama"  

OUTPUT = True

INPUT = "0P"
OUTPUT = False 

class Solution:
    def isPalindrome(self, s: str) -> bool:
        real_s = []
        for i in s : 
            if 48<=ord(i)<=57 or 65<= ord(i) <=90 or 97<=ord(i)<=122 :
                real_s.append(i)
        
        for i in range( len(real_s)//2 ):
            if real_s[i].upper() != real_s[ len(real_s)-i-1 ].upper():
                return False 
        return True

tip!  

real_s.append(i)  할 때, real_s.append( i.upper() ) 로 리스트에 추가하면 더 효율적으로 코드를 작성할 수 있다. 

leetcode.com/problems/valid-palindrome/

문자열 n 에서 m 을 제외한 문자열을 출력하시오. 

n = input()
m = input() 
k = 0 
p=''

for i in n : 
  if k == len(m) or i != m[k] :
    p = p + i 
    
  else:
    k += 1 

print(p)

- 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)  )