전체 글280 1260 DFS와 BFS 💡문제 분석 요약DFS, BFS 기본 문제이다.N개의 정점과 M개의 간선이 주어지고 V 노드에서 탐색을 시작한다.V를 시작으로 방문된 점을 순서대로 출력하면 된다.💡알고리즘 설계정점 탐색을 위한 그래프를 사용한다.DFS는 스택 or 재귀로 풀 수 있다.BFS는 큐를 이용하여 풀 수 있고, 큐는 웬만하면 deque를 선언하는 것이 좋다고 느낀다.💡코드from collections import dequen, m, v = map(int, input().split()) # 정점, 간선, 탐색 시작할 정점의 번호graph = [[False] * (n + 1) for _ in range(n + 1)] # 그래프 선언# 주어진 정보로 정점간 연결하기for _ in range(m): a, b = map(in.. 2024. 7. 15. 필독!!) DFS / BFS 정리 + 인접행렬, 인접리스트 이 포스팅을 함께 보자.https://100won-developer.tistory.com/entry/DFS-BFS-%EC%B0%A8%EC%9D%B4 DFS / BFS 차이두가지 모두 그래프를 탐색하는 방법이다. DFS 가장 깊은 곳까지 탐색을 마치고 돌아와서 탐색하는 방법. 예를들면 미로찾기를 할 때 한 방향으로 쭉 가고, 막다른 길이 나오면 다시 가장 가까운100won-developer.tistory.com BFS, DFS 알고리즘 분석보다는 언제 어떻게 쓰이고, 어떤 개념들이 쓰이는지 적어보았다. DFSDFS는 그래프깊이 우선 탐색법이다. Root 노드에서 시작하여, 최대한 깊이 탐색한 후 다음 branch로 넘어가는 방법을 말한다.def DFS(v): visited1[v] = True # 현재.. 2024. 7. 15. 시간복잡도 요약 시간복잡도란 ?한마디로 알고리즘의 성능이다. 정확히 몇초라는 시간을 의미하는 것이 아니고, 이정도의 입력값과 이런 코드라면 이정도의 시간이 걸릴 것이라는 일종의 예측지표이다. 시간복잡도는 최상, 평균, 최악 3가지 지표가 있지만 보통 코드를 짤 땐 항상 최악의 경우를 상정하고 짜는 것이 일반적이므로 최악의 경우인 Big O notation을 사용한다.왜 시간복잡도를 사용하는가 ?한마디로, 환경에 따라 실행 시간은 다를 수 있기 때문이다. 컴퓨터 HW, 와이파이, 틀어놓은 탭 수 ... 등등 어떤 알고리즘이 실행될 때 사람마다 환경이 모두 다르다. 따라서 이 알고리즘이 나에게는 효과적인데 팀원에게는 안좋을 수 있다. 따라서 더 일반적인 설명을 위해서 시간복잡도를 사용할 수 있고, 이는 환경에 상관없이 알고.. 2024. 7. 15. 프로세스 vs 쓰레드 선 요약프로세스 = 독립적인 실행공간, 쓰레드 = 스택만 독립적이고 나머지는 공유 프로세스 = "프로그램"의 인스턴스 (= HDD에서 메모리로 올라온 프로그램을 의미)독립적인 실행 환경(자신만의 주소 공간)을 할당받는다.여기서 말하는 환경은 Code, Data, Stack, Heap을 의미한다. 즉, 각 프로세스별로 이 4개를 독립적으로 가짐.프로세스간 메모리 독립적이라서 서로 영향을 주지 않아 다른 프로세스의 변수에 접근 불가능.만약 프로세스간의 통신을 해야한다면 IPC(Inter Process Communication)를 이용해야한다.쓰레드 = 프로세스 내에서 실행하는 작은 실행단위 (= 프로세스 내의 물줄기들)가장 큰 차이는, 리소스 공유 여부이다. 프로세스는 리소스를 공유하지 않고 만약 공유해야한.. 2024. 7. 15. Programmers 주식가격 💡문제 분석 요약주식가격이 담긴 배열 prices가 주어진다.각 원소별로 몇초간 떨어지지 않았는지 구한다. 1 2 3이라고 하면 순서대로 2초, 1초, 0초간 가격이 떨어지지 않은 것으로 본다.💡알고리즘 설계이중 for문을 사용해서 첫번째 원소를 나머지 원소와 쭉 비교하는데, 만약 가격이 떨어지는 순간이 나오면 break하고 그때까지의 time을 기록하면 된다고 생각했다. 그런데 이중 for문을 쓰면 시간이 초과될 것 같아서 해보고 오버되면 다르게 하려 했는데 오버되지 않았다.생각해보면, 일단 prices 길이가 10만이었기 때문에 이중for문이면 100억번 계산되는 건가 싶었다.그런데 중간에 자기보다 큰 수가 나오면 바로 break되기 때문에 저정도로 큰 계산이 되지는 않을 것으로 생각했다.💡코드.. 2024. 7. 14. 9093 단어 뒤집기 💡문제 분석 요약문장이 주어졌을 때 띄어쓰기를 기준으로, 단어별로 거꾸로 출력해본다.💡알고리즘 설계각 단어별로 reverse 함수같은 것이 있다면 쓸 수 있어보인다.그게 아니라면 어제 했던 것 처럼, deque을 사용하고 해당 단어의 길이만큼 첫번째원소 pop 후 맨 뒤에 append를 반복해도 될 듯 하다.💡코드for _ in range(int(input())): lst = input().split() for i in range(len(lst)): lst[i] = lst[i][::-1] # 각 원소별 순서 뒤집기 print(lst[i], end=' ')💡시간복잡도 문장의 길이만큼만 반복되므로 O(N)이고, 최대 문장 길이가 1000이므로 문제가 없을 것으로 보.. 2024. 7. 13. 1966 프린터 큐, Programmers 프로세스 💡문제 분석 요약Queue에서 조금 바꿔서 우선순위를 보고 pop 여부를 결정한다.우선순위가 낮은데 앞에 있다면 맨 뒤로 돌아가게 되고, 자신이 제일 높은 우선순위라면 pop된다.💡알고리즘 설계딕셔너리, 우선순위큐 등을 살펴보았다.딕셔너리로 우선순위와 index를 매칭시켜볼까도 생각했는데, index 업데이트 하는 게 매우 번거로울 것 같아서 그만두었다.그리고 우선순위큐를 보았는데 아직은 잘 다루지 못하겠어서 제쳐두었다. 이는 나중에 다시 포스팅해야겠다.💡코드from collections import dequefor _ in range(int(input())): n, m = map(int, input().split()) files = deque(list(map(int, input().sp.. 2024. 7. 12. 9012 괄호 💡문제 분석 요약괄호 문자열의 짝이 맞는지 분석한다. () 이것은 맞고 ()), )( 이런 것은 틀리다.문자열의 길이는 2~50이다.💡알고리즘 설계스택에 넣고 하나씩 빼면서 짝을 맞춰보기또는, ( ) 개수를 보고 짝이 안맞으면 NO 출력💡코드from collections import dequen = int(input())for _ in range(n): dq = deque(input()) compare = 0 if dq.count("(") != dq.count(")"): # 괄호의 개수 자체가 다르면 비교 X print("NO") continue """ (은 )보다 항상 많거나 같아야 한다는 것을 이용 개수를 체크하면서 compare 값을 .. 2024. 7. 11. deque 문제를 풀다가 deque라는 것을 봤는데 스택과 큐의 기능을 한번에 한다고 하니 매우 유용할 것 같다 ! 한번 알아보자 .. deque데크 디큐 덱 뎈.... 그냥 덱 이라고 부르겠다. 덱은 출입구가 양쪽에 있어서 스택과 큐의 기능을 동시에 가진다. 덱은 다음과 같이 선언하거나, 변환한다. 코드를 보면 알 수 있듯, 기존에 선언된 리스트를 덱으로 변환하는 것도 가능하다. from collections import dequetruck = [7, 4, 5, 6]truck = deque(truck) # 덱으로 변환onthebridge = deque([0] * bridge_length) # 덱으로 초기화장점덱은 리스트보다 속도가 빠르다. pop(0)을 할 때 리스트는 O(N)인데, 덱은 앞뒤 모두 접근하기에 O.. 2024. 7. 10. 이전 1 ··· 8 9 10 11 12 13 14 ··· 32 다음
