'항해 중/알고 보면 알기 쉬운 알고리즘' 카테고리의 글 목록 (2 Page)
본문 바로가기

항해 중/알고 보면 알기 쉬운 알고리즘19

Array(배열), Linked List(리스트), 둘의 차이점 자료구조와 알고리즘은 왜 배워야 하는 것일까? : 특정 자료구조는 삽입/삭제가 빠르고, 특정 자료구조는 조회가 빠릅니다. 이처럼 어떤 경우에는 이 자료구조가 좋고, 어떤 경우에는 저 자료구조가 좋은 것 처럼 경우에 따라 다양한 자료구조와 알고리즘을 사용 해야 합니다. 비유를 하자면 못을 박을 때 망치가 필요하고, 나사를 뺄 때는 뺀치가 필요한 것처럼 다양한 공구들을 하나하나 배워 나가는 것이라고 생각하면 됩니다. 1. 어레이(Array), 배열 상황으로 어레이를 설명 해보자면! 상황에서 언급된 "캡슐 호텔'이란 바로 Array, 배열을 의미합니다. 👀 여러분이 캡슐 호텔을 만들었습니다! 총 8명이 잘 수 있는 호텔입니다. 와 그런데 이게 무슨일일까요? 오늘 밤에 소녀시대 8명 전원이 와서 숙박할 계획이라.. 2021. 11. 13.
소수 나열하기, 문자열 뒤집기 [소수 나열하기] 문제설명 정수를 입력 했을 때, 그 정수 이하의 소수를 모두 반환 하시오. (소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다.) 의사코드(수도코드) - 소수를 담을 배열 -> primeArr = [] - for문을 사용하여 소수인 지 아닌 지 판별 https://inten.tistory.com/entry/Python-3x-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%86%8C%EC%88%98-%EA%B5%AC%ED%95%98%EA%B8%B0 [Python 3.x] 파이썬 소수 구하기 오늘은 파이썬으로 소수 구하는 방법을 구현 할 것입니다. 소수란 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. 여기서 소수를 구하.. 2021. 11. 12.
곱하기 or 더하기, 반복되지 않는 숫자 [곱하기 or 더하기] 문제설명 0 혹은 양의 정수로만 이루어진 배열이 있을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 '✕' 혹은 '+' 연산자를 넣어 결과적으로 가장 큰 수를 구하는 프로그램을 작성하시오. 단, '+' 보다 '✕' 를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서 순서대로 이루어진다. 의사코드(수도코드) - 총합을 구하는 변수 -> sum = 0이 필요 - 반복문을 돌면서 요소를 하나씩 빼온다. - sum에 요소를 더하거나 곱할 때 sum이 더 큰 연산을 실행한다. (0, 1에는 무조건 + 연산을 해야 한다.) (0, 1에 곱하기 연산을 진행 하는 것보다 더하기 연산을 하는 게 sum이 더 크기 때문에) - 총합을 return 한다. 문제 풀이 i.. 2021. 11. 12.
점근 표기법(+배열에서 특정 요소 찾기) 점근 표기법이란? 알고리즘의 성능을 수학적으로 표기하는 방법이다. 알고리즘의 "효율성"을 평가하는 방법이다. (아 이 알고리즘 좋던데? 이렇게 말하는 게 아니라 점근 표기법을 사용해서 얼마나 효율적인 지 얼마나 비효율적인 지에 대해서 평가를 쉽게 할 수 있는 방법이다.) 점근 표기법(asymptotic notation)은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다. 지금까지 이 함수는 N 정도의 시간과 공간이 걸리겠구나 하면서 분석 했던 게 점근 표기법의 일종이라고 할 수 있다. 점근 표기법의 종류에는 빅오(Big-O)표기법, 빅 오메가(Big-Ω) 표기법이 있습니다. 빅오 표기법은 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴 것인지, 빅오메가 표기법은 최선의 .. 2021. 11. 12.
공간 복잡도 판단하기 공간 복잡도란? : 입력값과 문제를 해결하는 데 걸리는 공간과의 상관 관계를 말한다. (입력값과 결과값이 나오는 데까지 사용하는 공간을 말한다.) 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 공간은 몇 배로 늘어나는 지 보는 것이다. 우리는 공간이 적게 걸리는 알고리즘을 좋아하니 입력값이 늘어나도 걸리는 공간이 덜 늘어나는 알고리즘이 좋은 알고리즘이다. 공간 복잡도를 계산 할 때는 저장하는 데이터의 양이 1개의 공간을 의미합니다. 첫번째 방법에서 공간 복잡도를 계산 해보자면 def find_max_occurred_alphabet(string): alphabet_array = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", ".. 2021. 11. 12.
시간 복잡도 판단하기 시간 복잡도란? : 입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계를 말한다. (입력값과 결과값이 나오는 데까지 걸리는 시간을 말한다.) 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 시간은 몇 배를 늘어나는 지 보는 것이다. 우리는 시간이 적게 걸리는 알고리즘을 좋아하니 입력값이 늘어나도 걸리는 시간이 덜 늘어나는 알고리즘이 좋은 알고리즘이겠죠? 시간 복잡도를 계산 할 때 입력값은 함수의 크기가 변경 될 수 있는 값을 말한다. 그렇기 때문에 다음 문제에서는 array가 입력값이다. 보통 array(입력값)의 길이는 N으로 표현하고, 각 줄이 실행되는 걸 1번의 연산이 된다라고 표현한다. 최댓값 찾기 알고리즘의 시간 복잡도를 판단 해보자면 첫번째 방법의 시간 복잡도는 input = [3, .. 2021. 11. 12.
최빈값 찾기 알고리즘과 친해지기 2 - 최빈값 찾기 : 위에서 풀었던 알파벳의 빈도수 세기를 활용해서 가장 많은 빈도수의 문자를 반환하는 문제이다. 1) 의사코드(수도코드) - 최대값을 담을 변수 생성 => max - 알파벳의 빈도 수를 담은 배열 생성 alphabet_occurrence_array = [0] * 26 - 문자인 지 아닌 지 구별하는 함수 => str.isalpha()를 사용해서 문자이면 true를 반환, 문자가 아니면 false를 반환 - 문자를 숫자(아스키 코드)로 변환하는 함수 => ord("문자") - 해당 문자의 index 위치를 찾아서 1씩 더한다. => ord('a') - ord('a')를 하면 0이라는 index 값이 나온다. - 배열을 돌면서 가장 큰 값을 가진 인덱스 위치를 찾는다... 2021. 11. 12.
알파벳 빈도수 세기 알고리즘과 친해지기 2 - 알파벳 빈도수 세기 : 문자열을 입력 받았을 때 어떤 알파벳이 가장 많이 포함되어 있는 지 반환한다. -> 문자인 지 확인하는 방법 : 파이썬의 내장 함수 str.isalpha()를 이용하면 해당 문자열이 알파벳인 지 확인 할 수 있다. -> 알파벳 별로 빈도수를 리스트에 저장하기 : 우선 알파벳 빈도수를 저장하기 위한 길이가 26인 0으로 초기화된 배열을 만든다. -> 아스키 코드를 사용해서 문자를 숫자로 변환 하거나 숫자를 문자로 변환 할 수 있다. 문자를 아스키 코드로 변환 할 때는 "python char to ascii code"라고 검색을 해보면 ord 함수를 사용하라고 나온다. 1) 의사코드(수도코드) - 알파벳의 빈도 수를 담은 배열 alphabet_occurren.. 2021. 11. 12.
최댓값 찾기 알고리즘과 친해지기 1 - 최댓값 찾기 문제 : 배열 안에 있는 요소 중에서 최댓값을 찾아 반환하는 문제 1) 의사코드(수도코드) - 최댓값을 담을 변수 => max - 배열의 요소들을 하나씩 빼온다. => for 반복문 - 값을 비교해서 더 큰 값을 max 변수에 담는다. => if문 - 최댓값을 담은 max 변수의 값을 return 한다. 2) 코드 구현 input = [3, 5, 6, 1, 2, 4] def find_max_num(array): # 큰 값을 담을 변수 max = 0 # or max = array[0]도 가능하다. # 배열에 값들을 하나씩 뽑아온다. for num in array: # 값을 비교해서 더 큰 값을 변수에 담는다. if(max < num): max = num return .. 2021. 11. 12.
728x90

티스토리툴바