본문 바로가기

Algorithm42

[BaekJoon] 백준 알고리즘 1759번 / 암호 만들기 / 백트래킹(DFS) / Python import sys sys.stdin = open( "input.txt", "r") l, c = map(int, input().split()) bet = list(map(str, input().split())) bet.sort() #알파벳 오름차순 정렬 vowels = ['a', 'e', 'i', 'o', 'u'] ans = [] def check(ans): mo = 0 #모음 개수 ja = 0 #자음 개수 for i in range(l): #개수 계산 if ans[i] in vowels: mo += 1 else: ja += 1 if mo >= 1 and ja >= 2: #자음모음 개수 충족 return True else: return False def func(j): if len(ans) is l: i.. 2023. 3. 7.
[BaekJoon] 백준 알고리즘 14889번 / 스타트와 링크 / 백트래킹(DFS) / Python import sys sys.stdin = open( "input.txt", "r") def dfs(depth, idx): global minValue team1, team2 = 0, 0 if (depth == N//2): for i in range(N): for j in range(N): if chk[i] == True and chk[j] == True: team1 += graph[i][j] elif not chk[i] and not chk[j]: team2 += graph[i][j] minValue = min( minValue, abs( team1 - team2 ) ) return for i in range(idx, N): if not ( chk[i] == True ): chk[i] = True dfs.. 2023. 3. 7.
[BaekJoon] 백준 알고리즘 1697번 / 숨바꼭질 / BFS / Python """ 1. 아이디어 - x-1, x+1, 2x의 케이스를 나눠서 탐색한다. - 해당 수에 이미 방문했다면 다시 방문하지 않는다. 2. 시간복잡도 - 좌표 200_000개 - 간선 200_000 * 3개 = 600_000개 - 800_000 < 2억개! 가능. 3. 자료구조 - q [] - visited [] 4. 시나리오 1) q [] 생성, v [] 생성 2) 초기 q.append(s), v[s] = 1 3) while q: 4) c = g.pop(0) 5) c-1, c+1, 2c( 허용범위 내, 미방문 ) 6) q 삽입, v[c] 방문처리 """ import sys sys.stdin = open( "input.txt", "r") def bfs(s,e): # 초기 q [] 리스트 생성 q = [] #.. 2023. 3. 4.
[BaekJoon] 백준 알고리즘 1260번 / DFS와 BFS / Python import sys sys.stdin = open( "input.txt", "r") def dfs(c): # 방문정보 v[c] = 1 # 방문기록 ans_dfs.append(c) # 다음 방문지 for i in adj[c]: if v[i] == 0: dfs(i) def bfs(s): # 필요한 q, v[], 변수 생성 q = [] # Q에 초기데이터 삽입 q.append(s) ans_bfs.append(s) v[s] = 1 while q: c = q.pop(0) for n in adj[c]: if v[n] == 0: # q 삽입 q.append(n) # 방문정보 v[n] = 1 # 방문기록 ans_bfs.append(n) # 정점 N과 간선 M의 개수, 시작 정점 번호 V N,M,V = map( int,.. 2023. 3. 3.
[BaekJoon] 백준 알고리즘 14503번 / 로봇 청소기 / 시뮬레이션 / Python """ 1. 아이디어 - 4방향을 확인 하고 청소한다. 2. 시간 복잡도 - 4방향 전부 확인해야하니.. N*M => 50 * 50 = 2500 바라보는 방향을 유지한 채, 후진한다. 2-1-2-2. 벽이라면 => break 2-2. 왼쪽부터 확인했을 때, 빈칸이 있는 경우 2-2-1. 해당 빈 칸으로 이동한다. 2-2-2. 탐색 for문을 빠져나와 그 위치로.. 2023. 3. 2.
[BaekJoon] 백준 알고리즘 14888번 / 연산자 끼워넣기 / 백트래킹 / Python """ 1. 아이디어 - 연산자의 갯수만큼 재귀함수 호출 2. 시간복잡도 - N! 3. 자료구조 - n개의 자연수 저장 : [] - 연산자 저장 : [] """ import sys n = int(input()) value = list(map(int, input().split())) calc = list(map(int, input().split())) maxValue = -(sys.maxsize) minValue = sys.maxsize sum = value[0] # 재귀함수 정의 def recur( index, sum, plus, minus, multi, div ): global maxValue, minValue # n개의 자연수가 조합되었다면( 연산자를 다 조합했다면 ) if index == n: ma.. 2023. 3. 1.

티스토리툴바