전체 글336 #34 그런 줄 알았다 - 2024.07.18. 안경을 닦을 땐 언제나 완벽히 깨끗하게 닦아야만 하는 줄 알았다.필기를 할 땐 항상 줄에 맞게 또박또박 써야만 하는 줄 알았다.나는 언제나 착한 사람, 모두에게 사랑받는 사람이어야 되는 줄 알았다. 그렇지 않아도 괜찮다는 것을 이제야 알았다. 눈앞이 조금 뿌옇게 보여도글씨가 줄에 안 맞게 삐뚤빼뚤해도때로는 누군가에게 미움받아도그래도 괜찮다는 것을그게 인간적이라는 것을난 이제야 알았다. // 조금 달라도 괜찮습니다. 조금 못해도 괜찮습니다. 기준이 남에게 있다면 내가 다른 것이지만, 인생의 기준이 나에게 있다면 매 순간이 정답입니다. 내 인생의 기준점을 나에게 두는 연습을 해야겠습니다. 2024. 7. 18. 11724 연결 요소의 개수 💡문제 분석 요약방향 없는 그래프에서, "연결 요소"의 개수를 구한다. 연결요소라는 것이 생소했는데, 이는 노드끼리 연결된 묶음의 개수이다.이 말도 이해가 되지 않았지만, 한마디로 DFS가 수행되는 개수를 구하면 된다고 한다.💡알고리즘 설계DFS를 사용하고, 재귀를 이용한다.N의 값이 재귀를 고려하면 꽤 크기 때문에, sys.setrecursionlimit(10**7) 이러한 장치를 걸어줘야한다. (나중에 알게됨)💡코드import sysimput = sys.stdin.readlinesys.setrecursionlimit(10**7)n, m = map(int, input().split()) # 정점개수 n , 간선개수 mgraph = [[False] * (n + 1) for _ in range(n +.. 2024. 7. 17. 2667 단지번호붙이기 💡문제 분석 요약정사각형 모양 지도에 0과 1이 표시되어있고, 1은 집이 있다는 의미이다. 전체 지도에서 1끼리 뭉쳐져 있는 구역이 몇개인지 세고, 각 구역별로 집 개수를 함께 알아내야한다.💡알고리즘 설계처음 생각한 건 인접한 애들끼리 쭉 따라가다가, 1인 애들끼리만 묶고 더이상 없다면 집 전체 개수 + 1 해준다. 인접한 애들이니까 BFS를 사용해야하는 게 아닌가 싶었다. 그렇게 풀다가, 사실은 모든 노드에 대해서 상하좌우를 체크하며 인접노드를 봐야하는 것을 알게 되었다. 결국 두 풀이 모두 가능했고, DFS가 조금 더 편하게 쓸 수 있으니까 DFS를 사용하였다.DFS를 이용해 모든 노드에 대해서 탐색한다.예전에 잠깐 공부했던 경험을 살려, 상하좌우를 dx, dy 리스트로 표현하는 약간의 팁도 살려.. 2024. 7. 16. 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. 이전 1 ··· 14 15 16 17 18 19 20 ··· 38 다음 반응형
