인간 같은 원숭이

https://school.programmers.co.kr/learn/courses/30/lessons/86491

def solution(sizes):
    temp = []
    for i, j in sizes:
        if i >= j :
            temp.append([j,i])
        else:
            temp.append([i,j])
            
    wi, hi = sorted(temp, reverse=True), sorted(temp, key=lambda x:x[1], reverse=True)
    
    return wi[0][0] * hi[0][1]

https://school.programmers.co.kr/learn/courses/30/lessons/42840

n1 = [1, 2, 3, 4, 5] * 2000
n2 = [2, 1, 2, 3, 2, 4, 2, 5] * 1250
n3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5] * 1000

def solution(answers):
    
    c1,c2,c3 = 0,0,0
    for i1,i2,i3,ans in zip(n1, n2, n3, answers):
        if i1 == ans: c1 += 1          
        if i2 == ans: c2 += 1           
        if i3 == ans: c3 += 1
    
    result = [c1,c2,c3]
    maxi = max(result)
    answer = []
    
    for i, j in enumerate(result):
        if maxi == j:
            answer.append(i+1)
            
    return answer

깔끔한 예시 정답코드

def solution(answers):
    pattern1 = [1,2,3,4,5]
    pattern2 = [2,1,2,3,2,4,2,5]
    pattern3 = [3,3,1,1,2,2,4,4,5,5]
    score = [0, 0, 0]
    result = []

    for idx, answer in enumerate(answers):
        if answer == pattern1[idx%len(pattern1)]:
            score[0] += 1
        if answer == pattern2[idx%len(pattern2)]:
            score[1] += 1
        if answer == pattern3[idx%len(pattern3)]:
            score[2] += 1

    for idx, s in enumerate(score):
        if s == max(score):
            result.append(idx+1)

    return result

• score 하나로 변수 3개 쓸필요가 없다는 점
• " if answer == pattern1[idx%len(pattern1)]" 이유는
  • pattern 들마다 순환주기가 다르니까 각각 순환주기로 나눠준것
  • 7%4 -> 나머지 3이지만
  • 1 % 5 ->  1,  2%5 -> 2,  3%5 -> 3, 4%5 -> 4, 5%5 -> 0 이렇게 남는다
  • 이를 통해 내가 직전에 짠 코드처럼 *1000 이렇게 할필요가 없어짐

https://school.programmers.co.kr/learn/courses/30/lessons/42839

• 순열 문제
• "".join(i) -> 튜플과 리스트를 일반 문자열 또는 숫자형태로 변환 무조건 외워야됨!
• 두번 째 "from itertools import permutaions" 라이브러리 또한 순열을 위해서 외워야됨

1. 순열의 조합 찾음 -> 소수 찾기

from itertools import permutations

def permutation(x):
    # 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로 나누어떨어지지 않는 자연수
    if x < 2: # 연산속도 줄이기 위함?!
        return False
    else:
        for tt in range(2, x):
            if x % tt == 0:
                return False
    return True

def solution(numbers):
    count = 0
    test_case =[]
    
    for i in range(len(numbers)):
        data = list(permutations(numbers, i+1)) # 1자리수 2자리수 전부 조합
        rdata = list(set(map("".join, data))) # 중복제거 및, 튜플에서 리스트 형태 변환
        for j in rdata: # 개별로 리스트에 정수로 추가
            test_case.append(int(j))
    
    test_case = list(set(test_case)) # 재중복 체크
    for t in test_case: # 개별적으로 소수인지 아닌지 체크
        if permutation(t) == True:
            count += 1 # 소수면 count+=1
    return count

https://school.programmers.co.kr/learn/courses/30/lessons/42842

더보기

어떤 수를 나누어떨어지게 하는 수를 그 수의 약수라고 합니다.

8을 1, 2, 4, 8,로 나누면 나누어떨어집니다.

1, 2, 4, 8은 8의 약수입니다.

[출처] [5-1][1. 약수와 배수] 약수란? 배수란? (구체물로 개념 익히세요~)|작성자 세가지소원

https://siloam72761.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4Python-%EC%B9%B4%ED%8E%AB

 

[프로그래머스][Python] 카펫

1. 문제설명 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의

siloam72761.tistory.com

 

def solution(brown, yellow):
    answer = []

    # 10, 2
    for i in range(1,yellow+1): # 3 -> 0,1,2 
    	#yellow의 약수를 이용해 row를 더 길게 설정한다.
        if(yellow % i ==0): # i가 2일 때
            yellow_row = (yellow /i) # 1.0
            yellow_col = i # 2
            if (2 * (yellow_row + yellow_col) + 4 == brown): # (2 * (1.0 + 2) + 4 == 10)
                return [yellow_row +2, yellow_col+2]

https://school.programmers.co.kr/learn/courses/30/lessons/87946

from itertools import permutations

def solution(k, dungeons):
    answer = 0
    
    for permute in permutations(dungeons, len(dungeons)):
        count = 0
        hp = k
             
        for pm0, pm1 in permute:

            if hp >= pm0:
                count += 1
                hp -= pm1
                       
        answer = max(count, answer)
    
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/42748

def solution(array, commands):
    answer = []
    
    for i, j ,k in commands:
        temp = array[i-1:j]
        temp.sort()
        answer.append(temp[k-1])
    
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/42746

def solution(numbers):

    strn = list(map(str, numbers))
    sr1 = sorted(strn, key=lambda x:x*3,reverse=True)
    result = str(int(''.join(sr1))) # -> 리스트 탈출 시 유용할듯
    
    return result

• int(''.join(sr1)) -> 리스트 제거 시 엄청 유용한듯.
• key=lambda x:x*3 -> 자기 자신을 3번 곱해줌 ex) str3 -> 333

https://markdung.tistory.com/manage/newpost/303?type=post&returnURL=https%3A%2F%2Fmarkdung.tistory.com%2Fmanage%2Fposts

def solution(citations):
    citations.sort(reverse=True)
    
    for idx , citation in enumerate(citations): # 0부터 가져가면 이전 인덱스를 계속비교할 수 있음 즉 더쉽게 비교가능
        print(idx , citation)
        if idx >= citation:
            return idx
    return len(citations) # 예외처리라 보면 될듯

https://school.programmers.co.kr/learn/courses/30/lessons/1845.

# my -> pass
from collections import deque

def solution(nums):
    q = deque(nums)
    result = []
    
    while len(q) != 0:
        data = q.popleft()
        if data in result:
            continue
        else:
            result.append(data)
            
    if len(result) >= len(nums) //2: 
        return len(nums) //2
    else:
        return len(result)

# 다른 사람이 짠거
# set을 사용하면 자동으로 줄여주니까

def solution(ls):
    return min(len(ls)/2, len(set(ls)))

https://school.programmers.co.kr/learn/courses/30/lessons/42576

# 출력문 문제로 작동이 안됨;
from collections import deque


def solution(participant, completion):
    p, c = deque(participant), deque(completion)
    has = {}
    
    # while len(p) != 0:
    for i in range(len(p)):
        player = p.popleft()
        if player in c:
            c.remove(player)
        else:
            p.append(player)
    
    s = list(p)
    has[1] = s[0]
    print(has.values())

def solution(participant, completion):
    participant.sort()
    completion.sort()
    print(participant, completion)
    for i, j in zip(participant, completion):
        if i != j:
            return i
        
    return participant[-1]

• "return participant[-1]" 하는 이유

• 만일 순차적으로 전부 다 확인했는데 뒤에 complection 기준으로 끝나면 participant의 마지막 사람이 들어온 사람이기 떄문.

# 이게 문제 출제의 의도인 것 같음

def solution(participant, completion):
    data = {}
    h_val = 0
    for i in participant:
        data[hash(i)] = i
        h_val += hash(i)
    for j in completion:
        h_val -= hash(j)

    return data[h_val]

• 해시 함수는 임의의 값을 고정된 길이의 데이터로 변환하는 함수임.
  • 즉 딕셔너리를 생성  및 변환된 해시의 값을 알기위한 h_val 생성 ->  data, h_Val
  • 처음 참가자들을 확인하면서 딕셔너리에 각각의 해시값을 입력함. -> data[hash(i)] = i
  • 완주자와 비교하기 위해 h_val에 추가한 해시값을 전부다 sum함
  • 이후 완주자(complection)의 값에 해시값을 하나씩 뺴주면서 마지막에 남은 h_val의 해시값을 기존에 추가하였던 data 딕셔너리에서 불러옴
  •  

더보기

https://school.programmers.co.kr/learn/courses/30/lessons/42577

# startswith
def solution(phone_book):
    phone_book.sort()
    for i, j in zip(phone_book, phone_book[1:]):
        if j.startswith(i):
            return False
    return True

• 정렬하고 start Swith 함수를 사용한다 -> 앞 뒤랑 비교를 하는데 만일 뒤에 문자 기준으로 j.starswith(i)를 사용하면 문자 시작이 i 기준으로 시작했을 때 True로 반환하므로 False로 처리

# 해시를 사용한 문제

def solution(phone_book):
    phone_book.sort()
    answer = True
    dic = {}
    for i in phone_book:
        dic[i] = 1
    for j in phone_book:
        temp = ""
        for nums in j:
            temp += nums
            print(dic, temp, j)
            if temp in dic and temp != j:
                return False
    return answer

• 처음 딕셔너리에 전부 다 추가-> dic = {}
• 이후에 폰북에서 하나씩 전화번호를 꺼내고 이후 꺼낸 전화번호를 하나씩 비교하기 시작함
  • "temp" 라는 값에 번호를 개별적으로 대입하고 이 때 현재 딕셔너리에 존재하는지를 비교함
    • 즉 "if temp in dic" 
    • 또한 위에 상태로 두면 자기 자신의 번호랑 비교하므로 조건을 추가함
    • "and temp != j" 
    • "if temp in c and temp != j"

https://school.programmers.co.kr/learn/courses/30/lessons/42578

# 해시를 사용한 정석적인 문제
def solution(clothes):
    dic = {}
    for _, t  in clothes:
        if t not in dic:
            dic[t] = 2
        else:
            dic[t] += 1
    cnt = 1
    for i in dic.values():
        cnt *= i
    return cnt -1

• 처음에 딕셔너리 값에 전부 저장함. # int는 저장되는데 str은 저장 안됨
  • "dic[t] = 2"를 해준이유는 이후 확률 계산을 할 때 (본인 입었을 때, 안입었을 때)를 위해서 미리 2를함
    • 위처럼 아니면 "dic[t] = 1"로 두고 아래서 "cnt *= i+1" 해도 상관은 없음
  • 이후 values 값만 불러와서 확률 계산
    • ex) 3 * 2 
    • 이 때 마지막 리턴 값은 -1을 해줌.

https://school.programmers.co.kr/learn/courses/30/lessons/42579

더보기

문제 설명

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

제한사항

• genres[i]는 고유번호가 i인 노래의 장르입니다.
• plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
• genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
• 장르 종류는 100개 미만입니다.
• 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
• 모든 장르는 재생된 횟수가 다릅니다.

입출력 예genresplaysreturn

입출력 예 설명

classic 장르는 1,450회 재생되었으며, classic 노래는 다음과 같습니다.

• 고유 번호 3: 800회 재생
• 고유 번호 0: 500회 재생
• 고유 번호 2: 150회 재생

pop 장르는 3,100회 재생되었으며, pop 노래는 다음과 같습니다.

• 고유 번호 4: 2,500회 재생
• 고유 번호 1: 600회 재생

따라서 pop 장르의 [4, 1]번 노래를 먼저, classic 장르의 [3, 0]번 노래를 그다음에 수록합니다.

• 장르 별로 가장 많이 재생된 노래를 최대 두 개까지 모아 베스트 앨범을 출시하므로 2번 노래는 수록되지 않습니다.

※ 공지 - 2019년 2월 28일 테스트케이스가 추가되었습니다.

def solution(genres, plays):
    answer = []

    dic1 = {} # 가장 많이 재생된 장르
    dic2 = {} # 장르 내 많이 재생된 노래 수록
    
    for i, (g,p) in enumerate(zip(genres, plays)):
        if g not in dic2:
            dic2[g] = p
        else: dic2[g] += p
        
        if g not in dic1:
            dic1[g] = [(i,p)] # 리스트로 선언해줘야함
        else:
            dic1[g].append((i,p))
            
    s_dic2 = sorted(dic2.items(), key=lambda x:x[1], reverse = True)

    for k,_ in s_dic2: # 순차적으로 확인하는 거임 pop -> classic
        s_dic1 = sorted(dic1[k], key=lambda x:x[1], reverse = True)[:2]
        for i,_ in s_dic1:
            answer.append(i)
   
    return answer

• 개인적인 생각으로는 구현문제에 가까움
• 처음 dic1, dic2 생성 -> 가장 많이 재생된 장르, 장르 내 가장 많이 재생된 고유번호 
• dic1, dic2
  • for i, (g,p) in enumerate(zip(genres, plays)):
    • #  가장 많이 재생된 장르
    • if g not in dic1:
      • dic1[g] =1
    • else:
      • dic1[g] +=1
    • # 장르 내 가장 많이 재생된 고유번호
    • if g not in dic2:
      • dic2[g] = [i, p] -> 여기서 핵심은 리스트를 사용해줘야 튜플형태로 추가가 가능함
    • else:
      • dic2[g].append((i,p))

• 이후에는 가장 많이 재생된 장르를 찾기위해 정렬을 해줌. -> 횟수 기준으로
  • s_dic1 = sorted(dic1.items(), key=lambda x:x[1], reverse = True)

• for i, _ in s_dic1: -> 장르 내 가장 많이 재생된 고유번호도 찾기위해 반복문 사용 -> 또한 반복문을 통해 가장 재생이 많이 된 순서로 진행할 수 있음
  • s_dic2 = sorted(dic2[i], key=lambda, reverse=True)[:2] -> 현재 dic2는 각 장르마다 리스트로 생성되어 있음. 따라서 그 리스트를 두번 째 재생횟수 기준으로 재정렬함
  • 여기서 "[:2]"를 해주는 이유는 문제에서 각 장르별 최대 2개씩을원 했으므로 만약 하지 않는다면
  •  

 "[:2]" 입력 이후 

• for k, _ in s_dic2:
  • anwer.append(k)

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

더보기

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


def bfs(x):
    q = deque([x])
    # 처음 노드는 빨강색으로 칠하기
    visited[x] = 0 # (0: 빨강 / 1: 파랑)
    while len(q) != 0:
        x = q.popleft()
        # 인접한 노드 하나씩 체크
        for y in graph[x]:
            if visited[y] == -1: # 빨강 <-> 파랑
                visited[y] = (visited[x] + 1) % 2
                q.append(y)

# 이분 그래프(bipartite graph) 판별함수
def is_bipartite():
    for x in range(1, v+1): # 하나씩 노드를 확인
        for y in graph[x]: # 인접 노드를 하나씩 확인
            # 같은 색상인 경우가 있따면
            if visited[x] == visited[y]:
                return False
    return True

# 입력
for _ in range(int(input())):
    # 정점의 개수(v)와 간선의 개수(e)
    v, e = map(int, input().split())
    # 그래프 정보 입력받기
    graph = [[] for _ in range(v + 1)]
    # 간선의 정보(e)
    for i in range(e):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    visited = [-1] * (v+1) # 방문 정보
    # bfs를 이용해 그래프 색칠하기
    for x in range(1, v+1):
        if visited[x] == -1:
            bfs(x)
    if is_bipartite(): print("YES")
    else: print("No")

더보기

ref:

https://codingopera.tistory.com/67

 

깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) [초등학생도 이해하는 파이썬]

안녕하세요 '코딩 오페라'블로그를 운영하고 있는 저는 'Master.M'입니다. 저는 현재 '초등학생도 이해하는 파이썬'이라는 주제로 파이썬(python)에 대해 포스팅을 하고 있습니다. 제목처럼 진짜 핵

codingopera.tistory.com

깊이 우선 탐색(DFS)

깊이 우선 탐색(DFS)

깊이 우선 탐색은 영어로 DFS(Depth Frist Search)으로 깊이를 우선으로 탐색하는 방법입니다. 위 그림과 같이 DFS는 최대한 깊이 내려간 뒤 더 이상 내려갈 곳이 없으면 옆으로 이동하는 방식을 의미합니다. 

 

DFS는 다음과 같은 특징을 가지고 있습니다.

• 모든 노드를 방문하고자 할때 사용되는 방법
• DFS는 BFS(너비 우선 탐색)에 비해 비교적 간단함 
• 검색 속도는 DFS가 BFS에 비해 느림
• 스택이나 재귀함수를 이용하여 구현

 

너비 우선 탐색 (BFS)

너비 우선 탐색 (BFS)

너비 우선 탐색은 영어로 BFS(Breadth Frist Search)으로 너비를 깊이보다 우선적으로 탐색하는 방법입니다. 위 그림과 같이 BFS는 최대한 옆으로 넓게 이동한 뒤 더 이상 옆으로 갈 수 없으면 아래로 이동하는 방식을 의미합니다.

 

BFS는 다음과 같은 특징을 가지고 있습니다.

• 최단 경로를 찾고자 할때 사용 : 위 그림과 같이 BFS는 수평으로 탐색하는 방법이기 때문에 [1-3-7], [1-4-8]과 같은 최단 경로를 중간에 찾을 수 있습니다.
• 예를 들어 A와 B 사이의 관계를 알고 싶을 때 DFS의 경우 모든 경우를 고려해야 될 수도 있지만, BFS는 가까운 관계부터 탐색을 할 수 있습니다. 
• 큐를 이용하여 구현

지금까지는 DFS와 BFS의 개념에 대해 알아보았습니다. 이제부터는 이 부분의 이해를 돕고자 파이썬 예제를 보여드리겠습니다. 

 

그래프

먼저 위와 같은 그래프가 있을 때, 이를 파이썬 딕셔너리로 표현하면 다음과 같습니다.

 

myGraph = {
    'A': ['B', 'C', 'D'],
    'B': ['A', 'E'],
    'C': ['A', 'F', 'G'],
    'D': ['A', 'H'],
    'E': ['B', 'I'],
    'F': ['C', 'J'],
    'G': ['C'],
    'H': ['D'],
    'I': ['E'],
    'J': ['F']
}

"""
DFS(Depth-First Search)
"""

def my_dfs(graph, start_node):
    visited = list() # 방문한 노드를 담을 배열
    stack = list() # 정점과 인접한 방문 예정인 노드를 담을 배열

    stack.append(start_node) # 처음에는 시작 노드 담아주고 시작하기.

    while stack: # 더 이상 방문할 노드가 없을 때까지.
        node = stack.pop() # 방문할 노드를 앞에서 부터 하나싹 꺼내기.

        if node not in visited: # 방문한 노드가 아니라면
            visited.append(node) # visited 배열에 추가
            # stack.extend(graph[node]) # 해당 노드의 자식 노드로 추가
            stack.extend(reversed(graph[node]))

    print("dfs - ", visited)
    return visited
    
# 함수 실행
my_dfs(myGraph, 'A')
dfs -  ['A', 'B', 'E', 'I', 'C', 'F', 'J', 'G', 'D', 'H’]

1. 대표적인 DFS 코드 -> 스택과 재귀함수로 구현됨.
   1. 처음 방문했는지 확인하기위한 변수 Visited, 연관성을 알기위한 stack을 생성
   2. stack에 알고싶은 문자를 대입하고시작
   3. while stack을 도는데 이 때 x = stack.pop해서 담겨저 있는 문자를 뺴서 비교하기 시작함
      1. if x not in visited:이면 visited에 추가
      2. stack.append(reversed(array[x])) -> pop 함수는 뒤에서 부터 불러오므로 다음과 같이 해줘야함

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

더보기

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())

graph = []  # 입력받을 그래프를 담을 리스트 선언
result = []  # 결과를 담을 리스트 선언
count = 0

for _ in range(N):
    graph.append(list(map(int, input().rstrip())))

# 한 점을 기준으로 (위 아래 왼쪽 오른쪽) 으로 한칸 씩 이동할 좌표 설정
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def dfs(x, y):
    global count

    if x < 0 or x >= N or y < 0 or y >= N:
        return

    if graph[x][y] == 1:
        count += 1
        graph[x][y] = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            dfs(nx, ny)


# 그래프의 원소가 1일때만 dfs로 집을 방문한다.
for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:
            dfs(i, j)
            result.append(count)
            count = 0

result.sort()  # 오름차순으로 정렬

print(len(result))  # 총 단지수 출력
for k in result:  # 각 단지마다 집의 수 출력
    print(k)

import sys
input = sys.stdin.readline
# graph = [[0, 1, 1, 0, 1, 0, 0], [0, 1, 1, 0, 1, 0, 1], [1, 1, 1, 0, 1, 0, 1], [0, 0, 0, 0, 
# 1, 1, 1], [0, 1, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1, 0], [0, 1, 1, 1, 0, 0, 0]] 

# 변수 생성, 주변 집체크용 count, 그래프, 그래프 결과값 리턴용 result
count = 0
graph, result = [], []

# 입력
N = int(input())
for _ in range(N):
    yarray = list(map(int, input().strip()))
    graph.append(yarray)

dx = [0,0,1,-1] # x방향
dy = [1,-1,0,0] # y 방향

# 주변 연결된 집찾기
def dfs(x, y):
    global count

    if x < 0 or y < 0 or x >= N or y >= N:
        return
    
    if graph[x][y] == 1:
        count += 1
        graph[x][y] = 0
        for tt in range(len(dx)): # 0, 1, 2, 3
            nx = x + dx[tt]
            ny = y + dy[tt]
            dfs(nx, ny)

for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:
            dfs(i, j)
            result.append(count)
            count = 0

result.sort()

print(len(result))
for t in result:
    print(t)

• 알고리즘을 작성할 때는 처음 메인 입력과 출력까지 전부 작성해둔 뒤 마지막으로 세부알고리즘을 구현해야함.
  • 여기서 핵심은 dfs 문제 이해가 어느정되 되었지만 반복학습이 필요예정
  • 처음 dfs 정하기 전에 방향을 dx, dy 방향을 설정함 dx[0 0 1 -1] ,dy [1 -1 0 0]
  • 이후 입력받은 dfs 그래프 값을 개별 노드로 대입함.
    • def dfs(x, y):
      • if x < 0 or x >= N or y < 0 or y >= N 거리 벗어나면 -> 예외처리 
        • return
      • if graph[x][y] == 1:
        • count +=1            -> 방문 카운트
        • graph[x][y] = 0     -> 방문했으면 0으로 처리
        • for t in range(len(dx)):             -> 4가지 방향 체크
          • nx = x + dx[i]              -> 다음 x 방향
          • ny = y + dy[i]                 -> 다음 y 방향
          • dfs(nx,ny)                       -> 다음방향을 받아서 주변에 1을 체크하는 재귀함수로 체크

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

# 실험중

import sys

input = sys.stdin.readline

N = int(input())

graph, cgraph= [], []
# graph = [['R', 'R', 'R', 'B', 'B'], ['G', 'G', 'B', 'B', 'B'], ['B', 'B', 'B', 'R', 'R'], ['B', 'B', 'R', 'R', 'R'], ['R', 'R', 'R', 'R', 'R']]

rgb = {}
count = 0

for _ in range(N):
    array = list(map(str, input().strip()))
    graph.append(array)
    cgraph.append(array)



for i in range(N):
    for j in range(N):
        if cgraph[i][j] == "G":
            cgraph[i][j] = "R"

print(graph, cgraph) # 코드는 다작성했고 내일 crgaph 변환만 확인하면 됨.


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

def dfs(x, y, temp):

    if x < 0 or x >= N or y < 0 or y >= N:
        return
    
    if graph[x][y] == temp:
        graph[x][y] = "0"
        for tt in range(len(dx)):
            nx = x + dx[tt]
            ny = y + dy[tt]
            dfs(nx, ny, temp)

def check(graph):
    r, g, b = 0,0,0

    for i in range(N):
        for j in range(N):
            rrr = "R"
            bbb = "B"
            ggg = "G"
            if graph[i][j] == rrr:
                r += 1
                dfs(i, j, rrr)
                rgb["R"] = r
        
            elif graph[i][j] == bbb:
                b += 1
                dfs(i, j,bbb)
                rgb["B"] = b
                
            elif graph[i][j] == ggg:
                g += 1
                dfs(i, j, ggg)
                rgb["G"] = g

# check(graph)
# print(rgb,sum(rgb.values()))

• 실패

더보기

import sys

# 빠른 입력함수
input = sys.stdin.readline
# 재귀 제한 변경 -> 스택 오버플로우 발생 제한을 해결하기위해 깊이 10만정도
sys.setrecursionlimit(int(1e5))

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

def dfs(x, y):
    for tt in range(len(dx)):
        nx = x + dx[tt] # 다음 방향
        ny = y + dy[tt] # 다음 방향

        if nx < 0 or nx >= N or ny < 0 or ny >= N: # 예외처리
            continue
        
        if not visited[nx][ny]: # 방문하지 않았을때
            if graph[x][y] == graph[nx][ny]: # 처음 bfs를 호출 할때의 x, y값으로 주변을 비교 즉 "G"가 들어왔다면 G만 비교하는 것임
                visited[nx][ny] = -1
                dfs(nx,ny)

N = int(input())
graph = []
for _ in range(N):
    array = list(map(str, input().strip()))
    graph.append(array)

# 연결 요소의 개수 세기
answer = 0
visited = [[False] * N for _ in range(N)]

for i in range(N):
    for j in range(N):
        if not visited[i][j]:   
            visited[i][j] = True
            dfs(i, j)
            answer += 1

print(answer, end=' ')

# 초기화
answer = 0
visited = [[False] * N for _ in range(N)]

# R -> G 변환
for i in range(N):
    for j in range(N):
        if graph[i][j] == "G":
            graph[i][j] = "R"

for ii in range(N):
    for jj in range(N):
        if not visited[ii][jj]:
            visited[ii][jj] = -1
            dfs(ii,jj)
            answer += 1

print(answer)

• dfs에서 return 쓰지말고 continue 쓰자
• 재귀함수가 많이 필요할 것 같으면 "sys.setRecursion(int(1e5))" 사용 -> 10만
• 이전 나의 코드와 가장 큰 차이는, 나는 입력받은 "graph"를 건드려서 계속 사용했고, 여기는 "visited"로 방문처리를 하여 사용함
  • 처음 입력을 받고 난뒤 바로 방문처리를 위한 변수를 생성함 [[False] * N for _ in range(N)]
  • 지역을 알기위한 answer 변수또한 생성.
  • 이후 방문을 확인하는데
    • for i in range(N):
      • for j in range(N):
        • if not visited[i][j]: -> 방문하지 않았따면
          • visited[i][j] -> 방문처리
          • dfs(i, j)
          • answer +=1
  • def dfs(i,j):
    • for i in range(len(dx)):
      
      • nx = x + dx[i] -> 다음방향
      • ny = y + dy[i] 
      • if nx < 0 or nx >= N or ny < 0 or ny >= 0: -> 예외처리
        • return
      • if not visited[nx][ny]:
        • if graph[x][y] == graph[nx][ny]:  # 즉 "G"가 들어왔다면 계속 G만 찾는거임
          • visited[nx][ny] = -1  # 방문처리
          • dfs(nx, ny)

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

더보기

 

import sys

# 빠른 입력함수
input = sys.stdin.readline
# 재귀 제한 변경 -> 스택 오버플로우 발생 제한을 해결하기위해 깊이 10만정도
sys.setrecursionlimit(int(1e5))

def dfs(x):
    # x의 인접 노드 하나씩 체크
    for data in graph[x]:
        # print("data:", data)
        y = data[0]
        
        cost = data[1] # x에서 y로 가는 간선 비용
        if not visited[y]:
            visited[y] = True
            distance[y] = distance[x] + cost
            dfs(y) 

# n 노드의 개수, m 간선의 개수
n, m = map(int ,input().split())

# 트리 정보
graph = [[] for _ in range(n+1)] 

for i in range(n-1): # 항상 트리형식이므로 간선의 개수는 n-1이다.
    # 노드 a와 노드 b가 연결 (간선 비용은 c)
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))

print(graph)

# 각 쿼리마다 매번 dfs를 수행
for i in range(m):
    # x에서 y로 가기위한 최단 거리 계산
    x, y = map(int, input().split())
    # 방문 여부 및 최단 거리 테이블 초기화
    visited = [False] * (n+1)
    distance = [-1] * (n+1)
    visited[x] = True # 시작점 방문 처리
    distance[x] = 0 # 자신까지의 거리는 0 

    dfs(x) # x부터의 치단 거리 계산
    print(distance[y])

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

더보기

 

ref:

https://velog.io/@jsbryan/%ED%9E%99-%EC%B5%9C%EC%86%8C-%ED%9E%99-%EC%B5%9C%EB%8C%80-%ED%9E%99

 

힙 (최소 힙, 최대 힙)

힙(Heap)이란? 최댓값, 최솟값을 빠르게 찾기 위해 고안된 자료형으로 우선순위 큐를 위해 만들어졌다. 완전 이진 트리의 일종으로, 각 노드의 키값이 그 자식의 키 값보다 작지않거나(최대 힙),

velog.io

 

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

• 힙, 자료구조, 그리디

더보기

from collections import deque
import heapq, sys 

n = int(sys.stdin.readline().strip())

data, count = [], 0

for _ in range(n):
    x = int(sys.stdin.readline().strip())
    heapq.heappush(data, x)



while len(data) !=1 :
    x = heapq.heappop(data)
    y = heapq.heappop(data)
    sum_value = x+y
    count += sum_value
    heapq.heappush(data, sum_value)

print(count)

생각해보면 정말 간단한 문제였음

• 최소힙 기준으로 입력을 받고 하나씩 꺼낸다는게 생각의 문제였음
• 힙을 빼낼 때 2개씩 빼내고 2개의 sum 값을 다시 넣어주면됨.

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

• 힙, 위상정렬

더보기

 

• 진입차수(시작노드): 자기자신으로 오는 간선(1, 6) 즉 자기 자신으로 들어오는 간선이 없는 것들
  • 1,6을 큐에 넣고 이후 1, 6을 큐에서 꺼내 간선을 제거 하여 2,4를 다시 큐에 넣음
• 사이클이 존재한다는 의미는 예를 들어 3 -> 1 로 돌아가게 되면 3보다 1이 먼저 풀려야 하는데 1보다 3이 먼저 풀려야 한다는 뜻임 즉 사이클이 존재하면 "위상정렬"이 아니다.

 

• "힙"을 "우선순위 큐"라고도 함.

import sys, heapq

n, m = map(int, sys.stdin.readline().split())
# n+1한 이유는 그냥 for문이 0부터 시작하니까 계산을 용이하게 하려고 n+1 한듯
array = [[] for _ in range(n+1)] # 모든 노드에 대해서 자기가 어떤노드에 연결되어있는지
indegree = [0] * (n+1) # 현재 간선이 이어진 진입차수가 몇인지 확인하기 위해

heap = []
result = []

# 노드 연결 확인
for _ in range(m):
    x, y = map(int, sys.stdin.readline().split())
    array[x].append(y) # x랑 y연결
    indegree[y] += 1 #진입 차수를 확인 하기 위해 
# print(array, indegree)

# 알고리즘 설명처럼 진입차수가 0인 것을 정점을 큐에 삽입
for i in range(1, n+1):
    if indegree[i] == 0:
        heapq.heappush(heap, i) # 큐 삽입
# print(heap)

result = []

while heap: # 여기선 heap = queue 알고리즘의 2와 3을 반복하는 내용
    data = heapq.heappop(heap) # 큐에서 데이터를 하나씩 꺼냄 ---3 
    result.append(data)
    for y in array[data]: # --- 1
        indegree[y] -= 1 # ----1 로된 간선 제거
        if indegree[y] == 0: # 0이 되었으면
            heapq.heappush(heap, y) # 힙에다가 다시 y값 삽입

for i in result:
    print(i, end=' ')

• 알고리즘 구현 순서
  1. n,m 입력 및 간선 연결여부 확인용 array와 진입차수 체크를 위한 indegree 생성
  2. x,y 간선간 연결 확인 입력 받은 후 간선 array에 대입(array[x].append(y)) 및 진입차수 체크를 위한 indegree[y] +=1
  3. heap과 같은 우선순위 큐 생성. ->진입차수 0인 값부터 시작하기 위함. 
     1. for _ in range(1, n+1): if indegree[i] == 0: heapq.heappush(heap, i)
  4. 결과 값을 위한 result 변수 생성 및 while 위상정렬 수행 -> 진입차수가 0부터인 heap으로 시작됨
     1. 기존 heap에서 추출 - > data = heapq.heappush(heap) -> 결과값 어팬드 -> result.append(data)
     2. 연결된 간선 확인 -> for y in array[data] ->  진입차수 1 낮추기 -> indegree[y] -= 1
     3. 만약 진입차수가 0 이면 다시 heap에 추가 - > if indegree[y] ==0: heapq.heappush(data, y)

# 위상자료
import sys, heapq

n, m = map(int,sys.stdin.readline().split())
array = [[] for _ in range(n+1)] # 간선확인
check = [0] * (n+1) # 진입 차수 확인

for _ in range(m):
    x, y = map(int,sys.stdin.readline().split())
    array[x].append(y)
    check[y] += 1

# print(array, check) 

heap = [] # 스택 생성 -> 우선순위 큐
for i in range(1, n+1): # 진입차수를 판단하기 위해 -> 진입차수가 0인 것부터 비교
    if check[i] == 0:
        heapq.heappush(heap, i)

# print(array, check, heap) 
        
result = [] # 결과 값

while heap:
    x = heapq.heappop(heap) #  0 진입차수 처음부터 뽑기
    result.append(x) # 뽑은 결과 값 추가
    for y in array[x]: # 뽑혔던 집입차수 간선 확인
        check[y] -= 1 # 간선 제거
        if check[y] == 0: # 0이 되면
            heapq.heappush(heap, y) # 다시 연결되었던 힙에 추가

# 뽑고 -> 결과 추가하고 -> 뽑현던거 간선 확인 -> 간선 제거 ->간선 연결된게 남아있으면 반복.
for j in result:
    print(j, end=" ")

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

• 트리, 구현

더보기

• x축을 기준으로 오른쪽으로 출력되는 특징이 있음

# 아래 ref 참조코드

# 한번 재귀할 때마다 탐색을 한번 더 하는 의미로 받아들이자
# 함수 안의 ~~order(tree[root][0]) 재귀함수는 왼쪽으로 끝까지 탐색한다는 의미
# 함수 안의 ~~order(tree[root][1]) 재귀함수는 오른쪽으로 끝까지 탐색한다는 의미
# root -> 출력하면 됨


# 1. 전위 순회 : 루트 -> 왼쪽 자식 -> 오른쪽 자식이므로 재귀함수 순서도 root출력문 -> 왼쪽 재귀함수 -> 오른쪽 재귀함수

def preorder(root): # 루트 -> 왼쪽 자식 -> 오른쪽 자식 순으로 탐색
    if root != '.':
        print(root, end='')  # root
        preorder(tree[root][0])  # left -> left가 새로운 root가 된다.
        preorder(tree[root][1])  # right -> right가 새로운 root가 된다.
        

# 2. 중위 순회 : 왼쪽 자식 -> 루트 -> 오른쪽 자식이므로 재귀함수 순서도 왼쪽 재귀함수 -> root 출력문 -> 오른쪽 재귀함수
 
def inorder(root): # 왼쪽 자식 -> 루트 -> 오른쪽 자식 순으로 탐색
    if root != '.': 
    # TEST CASE를 예로 들면 B에서 tree[root][0] = "D"이고 D의 tree(root[0]) = "."이 돼서 root인 D를 출력하고 right로 넘어간다.
        inorder(tree[root][0])  # left
        print(root, end='')  # root
        inorder(tree[root][1])  # right


# 3. 후위 순회 : 왼쪽 자식 -> 오른쪽 자식 -> 루트이므로 재귀함수 순서도 왼쪽 재귀함수 -> 오른쪽 재귀함수 -> root 출력문

def postorder(root): # 왼쪽 자식 -> 오른쪽 자식 -> 루트 순으로 탐색
    if root != '.':
        postorder(tree[root][0])  # left
        postorder(tree[root][1])  # right
        print(root, end='')  # root

전위순회

더보기

tree = {'A': ('B', 'C'), 'B': ('D', '.'), 'C': ('E', 'F'), 'E': ('.', '.'), 'F': ('.', 'G'), 'D': ('.', '.'), 'G': ('.', '.')}

 

• 처음 root 값에 "A"가 들어왔을 때 tree에서 만들어 뒀던 하위 노드 값을 불러옴.
  • 14라인에서 "A"를 출력하고 15라인에서 " A " 의 노드가  "b", "c"  두 개 인데 먼저 "B"부터 호출함

• "B"가 호출이 되고 이후에 위와 똑같이 15라인에서 "B"의 하위노드 "D"를 호출함

• 현재 D의 하위 노드는 'D': ('.', '.') 둘 다 없다.  
• " preorder(tree[root][0])  # left " 함수가 동작중인 상황에서 입력값으로 "."  이 들어와서 Return value "None"으로 탈출한다. 이후 preorder(tree[root][1])  # righ  값 또한 위와 같은 상황으로 탈출하게 된다.
• 이로써 "D"로 매개변수를 받은 함수는 재귀적으로 자동 탈출하게 된다.

 

• 트리 'B': ('D', '.') 상황
• 직전에 "B"의 좌측 노드 "D"를 탈출하였기 때문에 B의 우측노드"."이 입력으로 받았다 이 또한 해당사항이 없으므로 Return value는 none으로 탈출된다.

• 좌측은 탐색이 끝났으므로 원래 A 우측 탐색이 시작된다. 'A': ('B', 'C')

 

• 좌측부터 반복해서 확인을 한 후 "E" 또한 None을 만나 함수를 탈출하고 다음 함수 즉 우측 하위 노드 탐색을 하며 둘 다 None이므로 "E"또한 마무리된다.

• 이후 F-> 좌측 노드는 None, 이므로 바로 탈출해서 우측 노드 G로 재귀적으로 다시 받아 탐색 후 차례차례 회수되며 끝이난다.

import sys
 
N = int(sys.stdin.readline().strip())
tree = {}
 
for n in range(N):
    root, left, right = sys.stdin.readline().strip().split()
    tree[root] = [left, right]
 
 
def preorder(root):
    if root != '.':
        print(root, end='')  # root
        preorder(tree[root][0])  # left
        preorder(tree[root][1])  # right
 
 
def inorder(root):
    if root != '.':
        inorder(tree[root][0])  # left
        print(root, end='')  # root
        inorder(tree[root][1])  # right
 
 
def postorder(root):
    if root != '.':
        postorder(tree[root][0])  # left
        postorder(tree[root][1])  # right
        print(root, end='')  # root
 
 
preorder('A')
print()
inorder('A')
print()
postorder('A')

ref

https://velog.io/@ohk9134/%EB%B0%B1%EC%A4%80-1991%EB%B2%88-%ED%8A%B8%EB%A6%AC-%EC%88%9C%ED%9A%8C-python-%ED%8A%B8%EB%A6%AC-%EA%B5%AC%ED%98%84

https://kill-xxx.tistory.com/entry/Python-%EB%B0%B1%EC%A4%80-1991%EB%B2%88-%ED%8A%B8%EB%A6%AC-%EC%88%9C%ED%9A%8C-%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98%EC%99%80-%EB%94%95%EC%85%94%EB%84%88%EB%A6%AC-%EC%9D%B4%EC%9A%A9%ED%95%98%EA%B8%B0

https://fastcampus.co.kr/me/course

• 트리, 구현

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

• 이진 탐색

더보기

 

• min, max를 찾고 중간을 돌면서 갱신하는 것이 이진탐색방법 
  • min 값은 배열[1] - 배열[0]을 뺀 값
  • max 값은 배열[-1] - 배열[0]을 뺀 값

• 최소를 1 최대를 8이라 가정하였을 때 중간값은 8+1//2 가 4가된다.
• 1, 2와 1, 4의 거리는 갭에 4이하이므로 1,8밖에 설치가 안되며, 8,9 또한 갭이 1이 안되므로 전체 공유기 개수는 2개 되어 다시 Gap를 감소시킨다.이 때 최대 gap은 이전 mid Gap 보다 1을 줄여서 최대 gap으로 설정한다.

• 현재 미드 gap 값은 다시 계산(min+max //2) 2가 된다.
• 2를 기준으로 아까처럼 1,2는 x 1,4는 o 4,8은 o 8,9는x로 공유기를 3개까지 설치가 가능하다.
• 현재 미드 gap 값을 결과 값에 저장하고 가장 큰 경합값을 찾기 위해 최소 gap 값을 증가 시킨다.

• 서로 만나는 지점의 gap이 되었으므로 미드 gap 또한 3이된다.
• 1,2x 1,4o 4,8 o, 8,9x로 공유기 3개 조건을 만족하므로 결과값에 현재 gap으로 다시 대입한다. 

n, c = map(int, input().split())
array = []
for _ in range(n):
    array.append(int(input()))
# n,c = 5, 3
# array = [1, 2, 8, 4, 9] #
array = sorted(array)
min, max = 1, array[-1] - array[0]
result = 0
while (min <= max): # 이진 탐색
    mid = (min+max) // 2 # 4, 3.....
    value = array[0]
    count = 1
    
    for i in range(1, len(array)): # 각 데이터를 돌면서 mid 간격 비교 
        if array[i] >= mid+value: # 만약 현재 값이 설정한 mid 값 이상이면
            count +=1 # 공유기 추가
            value = array[i] # 다음 데이터 비교를 위한 value 값 대입
            
    if count >= c: # 공유기 개수가 맞으면
        result = mid # 공유기 결과 저장 
        min = mid + 1 # 더 넓은 폭을 찾기 위해 처음 값 mid +1 로 대입
    else:
        max = mid - 1 # 더 좁은 폭을 찾기 위해 end 값 mid-1로 대입

        
print(result)

• min, max 값 "min, max = array[1] - array[0], array[-1] - array[0]" 영번 째 인덱스 기준으로 거리를 최대 최소로 구함.
  • min 값을 array[1] - array[0]으로 하니 정답이 계속 틀리다고 나옴. min 값을 1로 고정해주니 정답 처리됨.
• "while"문은 이진탐색 시 "min", "max" 증 가감하면서 만나기 때문에 그 때까지 반복을 함
  • "mid" 중간 값 설정하고 여기서 중요한건 "value" 값
    • value값이 간격을 계속 체크하기위한 값이 됨
  • "for i in range(1, len(array)): # 각 데이터를 돌면서 mid 간격 비교 "을 통해 각각의 데이터 비교 시작
    • "if array[i] >= mid+value" # 만약 현재 값이 설정한 mid 값 이상이면
                  count +=1 # 공유기 추가
                  value = array[i] # 다음 데이터 비교를 위한 value 값 대입
    • 헷갈린 이유가 계속 "value" 누적이유
      • 1,4,7,10 배열로 계속 들어오는 상황에서 인덱스 비교를 배열[1]부터 시작하며 mid가 3으로 가정을 하면
        • 1,4 비교시 4와 1의 간격이 3이 되었을 때 value 값을 다시 array[i] 로 해줘야 다음 값 4, 7을 현재 간격으로 해서 계속 비교할 수 있음 
  • 비교가 끝난 뒤 만약 공유기 개수가 입력 m 값이면 -> 즉 start 값을 mid+1로 증가 해서 간격을 늘리는게 목적
    • "result = mid # 공유기 결과 저장 "
    • "min = mid + 1 # 더 넓은 폭을 찾기 위해 처음 값 mid +1 로 대입"
  • 개수가 안맞으면 end 값을 mid-1로 해서 현재 mid 간격을 더욱 좁히는게 목적
    •  "max = mid - 1 # 더 좁은 폭을 찾기 위해 end 값 mid-1로 대입"

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

• 이진탐색 문제.

더보기

• 중량 5라고 가정하였을 때 노드 1에서 3까지 이동이 가능하므로 중량을 증가시킴. 
•  이 때 결과값을 5로 저장함

 

• 이 때 최소 중량값을 이전 중량 값(5)에서 +1한 6으로 설정하고 현재 중량은 9와 6의 사이값 7로 설정
• 하지만 현재 중량 값 7은 노드 2에서 3으로 이동할 수 없으므로 중량값을 감소시켜야함.

• 따라서 감소시키기 위해 최대 중량값을 이전 중량 값"7"에서 -1한 값 "6"을 설정한다.

• bfs 강의 듣고 다시 풀어봐야할듯