728x90 반응형 알고리즘문제풀이26 [알고리즘/python] input() 과 sys.stdin.readline()의 차이 알고리즘을 풀다 보면 식이랑 답은 제대로 나오는데 시간초과가 날 때가 있다. 나는 주로 input()을 많이 사용하여 문제를 푸는데 이럴때는 바로 sys.stdin.readline()으로 변경해서 다시 제출해본다. 그럼 거의 시간초과가 해결될 때가 있다.(아직 내가 어려운 문제는 안풀어서 이걸로 해결이 가능한듯) 그러다 궁금해져서 둘의 차이점을 찾아봤다. input() - 사용자가 값을 입력하여 제출한다. - 문자열변환, 줄바꿈 등 추가과정이 있다. - 데이터가 버퍼에 하나씩 입력된다. *버퍼 : 데이터를 한곳에서 다른 한곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 메모리의 영역 sys.stdin.readline() - input()과 같은 추가과정이 없다. - 데이터가 버퍼에 한번에 입력된다... 2023. 3. 21. [알고리즘/Python] 시간복잡도(time complexity) 알고리즘은 일반적으로 인풋의 크기에 따라 소요되는 시간이 달라진다. 보통 인풋 크기가 커질수록 알고리즘이 실행되는데 더 오래 걸린다. 인풋은 컴퓨터의 성능이나 프로그래밍 언어 등 환경적인 것들에 따라서 달라진다. 그래서 정해진 것이 점근표기법, 빅오(Big-O)표기법이다. 점근 표기법은 n이 엄청 큰 수라는 가정하에 사용된다. n이 별로 크지 않으면, 안 좋은 알고리즘을 써도 프로그램이 돌아가는데엔 문제가 없기 때문이다. 또한, 점근 표기법은 절대적인 시간이 아닌 성장성을 보기 때문에 예를들어 2n²+8n+34라는 시간이 든다고 가정해보자. 처음에는 2n² 이 8n+34 보다 그래프가 낮을 순 있지만 n이 커지다 보면 2n²이 압도적으로 값이 커지는 것을 알 수 있다. 그렇기에 더 영향력이 있는 2n² .. 2023. 2. 24. [알고리즘/Python] 재귀함수와 팩토리얼 재귀적으로 문제를 푼다는것 = 같은 형태의 더 작은 문제를 풀고 부분 문제의 답을 이용해서 기존 문제를 푸는 것. 재귀함수의 예시로 팩토리얼을 한번 보자. 팩토리얼 n의 팩토리얼은 n!이라고 표시한다. 이는 1부터 n까지의 정수를 곱하는 단순한 연산을 말한다. 재귀로 풀땐 항상 경우를 나눠줘야하는데 기본적인 base case와 조건이 다른 recursive case가 있다. 0!=1이라고했으니 n =0인 경우는 무조건 n!=1이 된다. 이렇게 바로 답이 나오는 경우를 base case라고 한다. 하지만 n != 0 인경우, n >0인 경우엔 재귀적으로 문제를 풀어야한다. 즉, 같은 형태의 더 작은 문제를 풀고 부분 문제의 답을 이용해서 기존 문제를 푸는 것이다. 위에 그림처럼 5!은 1x2x3x4x5 =.. 2023. 2. 23. [백준/Python][Silver V] 요세푸스 문제 0 - 11866 [Silver V] 요세푸스 문제 0 - 11866 문제 링크 성능 요약 메모리: 116112 KB, 시간: 148 ms 분류 자료 구조(data_structures), 구현(implementation), 큐(queue) 문제 설명 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램.. 2023. 2. 16. [알고리즘/Python] BFS(너비우선탐색) BFS (너비우선탐색) Breath-First Search, 그래프에서 가까운 부분을 우선적으로 탐색하는 알고리즘이다. 너비 우선 탐색이라고도 한다. 데이터가 N개 있을때 O(N)시간 복잡도를 가진다. 일반적인 경우 실제 수행시간은 DFS보다 좋은편이다. [DFS vs BFS] 동작 방식 동작 원리 구현 인접한 노드가 여러개라면? DFS 멀리 있는(깊게 있는)노드 부터 탐색 스택 재귀 함수 이용 한개씩 넣음 BFS 가까운 노드부터 탐색 큐 큐 자료구조 이용 한번에 다 넣음 BFS 동작과정 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 2. 큐에서 노드를 꺼내 해당 노드의 인접노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 한다, 3. 2번과정을 더이상 수행할 수 없을 때까지 반.. 2023. 1. 18. [알고리즘/Python] 깊이우선탐색 (DFS) 그래프 탐색 알고리즘 : 시작 정점에서 간선을 타고 이동할 수 있는 모든 정점을 찾는 알고리즘 깊이우선탐색 (Depth-First Search, DFS) 그래프의 깊이를 우선으로 탐색하기 위해 스택의 개념을 활용한다. 너비우선탐색 (Breadth-First Search, BFS) 그래프의 너비를 우선으로 탐색하기 위해 큐의 개념을 활용한다. 깊이우선탐색(Depth-First Search, DFS) 시작 정점으로부터 갈 수 있는 하위 정점까지 가장 깊게 탐색하고, 더 이상 갈 곳이 없다면 마지막 갈림길로 돌아와서 다른 정점을 탐색하며 결국 모든 정점을 방문하는 순회 방법 깊이우선탐색(DFS)의 특징 모든 정점을 방문할 때 유리하다. 따라서 경우의 수, 순열과 조합 문제에서 많이 사용 한다. 너비우선탐색(B.. 2023. 1. 18. [알고리즘/Python] 그래프(Graph) (인접행렬,인접리스트) 그래프(Graph) 정점(Vertex)과 이를 연결하는 간선(Edge)들의 집합으로 이루어진 비선형 자료구조 소셜 네트워크와 지하철 노선도 같이, 현실에 있는 개체 간의 관계를 나타내기 위해 사용한다. 2023. 1. 18. [알고리즘/Python] 에라토스테네스의 체 에라토스테네스의 체 -> 여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표적인 알고리즘. -> N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다. 소수란? 1과 자신 자신 외의 약수를 가지지 않는 1보다 큰 자연수를 말한다. > 동작 과정 2부터 N까지의 모든 자연수를 나열한다. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다. 남은 수 중에서 i의 배수를 모두 제거한다. (i는 제거하지 않는다.) 더 이상 반복할 수 없을 때까지 2번과 3번 과정을 반복한다. > 장단점 에라토스테네스의 체 알고리즘의 시간 복잡도는 O(NloglogN)으로 사실상 선형 시간에 동작할 정도로 빠르다. 그래서 다수의 소수를 찾아야 하는 문제에서 자주 사용된다. 하지만 알고리즘을 수행할 때 N의 .. 2023. 1. 18. [프로그래머스/Python][level 1] 소수 만들기 - 12977 [level 1] 소수 만들기 - 12977 문제 링크 성능 요약 메모리: 10.3 MB, 시간: 0.01 ms 구분 코딩테스트 연습 > Summer／Winter Coding（～2018） 채점결과 정확성: 100.0 합계: 100.0 / 100.0 문제 설명 주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요. 제한사항 nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다. nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다... 2023. 1. 13. 이전 1 2 3 다음 728x90 반응형
