맞왜틀

문제 해결 완전탐색 시뮬레이션 1. 먼저 CCTV의 위차와 방향들을 따로 리스트에 저장해둔다 2. 각각의 CCTV마다 감시할 수 있는 방향들이 다르기 때문에 하드코딩이지만 방향을 다 설정해준다. (1) 여기서 5번 CCTV는 방향을 바꿀수 없기 때문에 처음부터 탐색할 수 있는 곳들을 모두 표기해준다. 3. DFS를 통해 모든 경우의 수를 계산해 준다. 4. 경우의 수를 하나 찾을 때마다 감시하는 영역을 표시해주어 사각지대가 최소인 부분을 찾는다. -> 뭔가 하드코딩한 것 같지만 시뮬레이션문제라 어쩔 수없는 것같다. 시뮬레이션 문제를 풀면 진이 빠지는 것 같다. 항상 너무 길다...😵 소스 코드 from copy import deepcopy def dfs(idx, maps): # idx : 몇 번째 cct..

문제 해결 부르트포스 1. 크게 다리를 놓는 것과 사다리를 타는 것으로 나눈다. 2. 먼저 시작점은 (1, 1)이고 out of index 문제를 미리 방지하기 위해 배열을 적당히 넉넉하게 만들어준다. 3. 사다리를 0개 ~ 3개 짓는 경우를 만들어주고, 완전탐색으로 모든 경우의 수를 다 구해준다. 4. 그때 그때 마다 사다리타기를 해 결과 조건에 부합하는 지 확인해준다. -> 파이썬은 항상 시간초과 문제와의 싸움이다. 이번에도 pypy로 통과했다. 오늘은 시작부터 힘들었다. 문제 이해부터 예제 이해까지.... 하지만 역시 이웃님이 해결해줬다. 🔨 소스 코드 # 사다리 타기 def down(): # 1,1 부터 시작! for start in range(1, N+1): y = start # 시작점 인덱스를..

문제 해결 1. 방향이 있는 그래프에서 최단거리를 구하는 문제 | 보통 다익스트라 알고리즘을 사용한다. 2. 인접리스트, 가중치 배열, 힙큐를 준비한다. (1) 인접행렬보다 인접리스트가 조금 더 빠르다(?) (2) 가중치 배열: 인덱스 번호에 도착할 때의 가중치를 항상 최솟값으로 업데이트 해준다. (3) 힙큐는 항상 최솟값을 리턴해준다. 3. ex)a - c 와 a- c 로 갈 때의 가중치를 항상 비교하여 최솟값을 넣어줘야 한다. -> selected배열(출발했었는지 확인)을 만들어서 했는데 어짜피 단방향이라 필요가 없었다. python으로 제출 시 시간초과가 나서 pypy로 제출했더니 통과 했다. python으로 통과한 사람과의 코드를 비교해봤는데 차이가없었다..... 후😭 왜때문인지 모르겠다. 소스 ..

문제 해결 1. 암호는 알파벳 순서로 짜야하므로 오름차순 정렬 2. 모음의 포함 유무를 확인하기 위해 aeiou를 생성 3. 자음이 1개이상, 모음이 2개이상일 때 result에 추가 소스 코드 def bt(idx, word): # 암호의 길이가 L이 됐을 때 if len(word) == L: vowel_cnt = 0 consonant_cnt = 0 for w in word: if w in vowel: vowel_cnt += 1 else: consonant_cnt += 1 # 자음이 1개 이상, 모음이 2개 이상일 때만 result에 추가해 준다. if vowel_cnt >= 1 and consonant_cnt >= 2: result.add(word) break return # 함수에 들어갈 때 이전 선..

문제 해결 1. 완전탐색을 이용해 풀 수 있는 간단한 문제 2. 단순하게 자신보다 덩치가 큰 사람들의 숫자를 세어준다. -> 처음에 정렬하는 것으로 접근 방법을 선택해서 많은 시간을 날렸다.....후💨 소스 코드 N = int(input()) hulk = [list(map(int, input().split())) for _ in range(N)] # 자신보다 큰사람 숫자세기 cnt_list = [0] * N for i in range(N): cnt = 1 # 등수는 1등부터 있으므로 1부터 시작 for j in range(N): # 무게와 키가 자신보다 크다면 +1 if hulk[i][0] < hulk[j][0] and hulk[i][1] < hulk[j][1]: cnt += 1 else: cnt_lis..

문제 해결 1. 오늘 배운 최소 신장 트리(MST)를 사용하는 그래프 문제다. ( + heapq 모듈 사용 ) 💨 그래프에서 사이클을 제거하고 모든 노드를 포함하는 트리를 구성할 때, 가중치의 합이 최소가 되도록 만든 경우를 최소신장트리라고 한다. (1) 먼저 간선과 가중치를 인접리스트로 만든다. (2) key, mst, pq | 최소 가중치를 갱신하는 배열, 방문 배열, 힙큐( 최소값을 뽑는 모듈 ) 2. 시작점( 노드중 아무거나 )을 힙큐에 넣어주고 시작 - 이 문제에서는 모든 노드를 연결할 수 있다. (1) 힙큐 안에서 가중치가 가장 낮은 정점을 pop (2) 방문했는지 확인 | 이미 방문을 했다면 continue 를 통해 힙큐에서 다시 뽑고, 아니라면 True로 바꿔주고 가중치를 결과에 더해준다...