본문 바로가기

알고리즘/자료구조와 알고리즘5

2주차_링크드 리스트 구현 링크드 리스트 자료구조 구현방법! class Node: def __init__(self, data): self.data = data self.next = None node = Node(3) first_node = Node(4) node.next = first_node """ node #[3] node.next #[4] node.next.data #4 """ print(node.next.data) #4 print(node.data) #3 클래스의 생성자에 data를 인자로 받아서 self.data에 저장하고 현재는 다음 이어진 노드가 없기 대문에 self.next에는 None을 넣어둔다. 그리고 노드를 만들어서 연결을 해준다. 노드가 많다면 저 코드를 그만큼 쳐줘야 하는데 너무 비효율적이기 때문에 Link.. 2022. 9. 19.
2주차_어레이, 링크드리스트, 클래스 Array 와 LinkedList 1. Array 이야기 여러분이 캡슐 호텔을 만들었습니다! 총 8명이 잘 수 있는 호텔입니다. 와 그런데 이게 무슨일일까요? 오늘 밤에 소녀시대 8명 전원이 와서 숙박할 계획이라고 합니다. → 배열은 크기가 정해진 데이터의 공간입니다. 한 번 정해지면 바꿀 수 없어요! 떨리는 마음으로 체크인을 받고, 각 호수에 있는 멤버들의 방에 방문해 웰컴 드링크를 전달했습니다. → 배열은 각 호텔방(원소)에 즉시 접근할 수 있습니다 rooms[0] 처럼요! 여기서, 원소의 순서는 0부터 시작하고 이를 인덱스라고 부릅니다. 이 때, 즉시 접근 가능하다는 말은 상수 시간 내에 접근할 수 있음을 의미합니다. 즉, O(1) 내에 접근할 수 있다고 말하곤 합니다. 앗 그런데, 제일 끝방에 있.. 2022. 9. 19.
1주차_알고리즘 더 풀어보기 Q. 다음과 같이 0 혹은 양의 정수로만 이루어진 배열이 있을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 '✕' 혹은 '+' 연산자를 넣어 결과적으로 가장 큰 수를 구하는 프로그램을 작성하시오. 단, '+' 보다 '✕' 를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서 순서대로 이루어진다. def find_max_plus_or_multiply(array): multiply_sum = 0 for number in array: if number 2022. 9. 17.
1주차_시간 복잡도, 공간 복잡도, 점근표기법 시간 복잡도 입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계! 입력값이 늘어나도 시간이 덜 늘어나는 알고리즘을 짜기 위해 알아야 함!! 각 줄이 실행되는걸 1번의 연산이 된다고 생각하여 계산!! for num in array: # array 의 길이만큼 아래 연산이 실행 for compare_num in array: # array 의 길이만큼 아래 연산이 실행 if num < compare_num: # 비교 연산 1번 실행 break else: return num 위에서 연산된 것들을 더해보면, (array의 길이) X (array의 길이) X (비교 연산 1번) array(입력값)의 길이는 보통 N이라고 표현하면 N^2라고 할 수 있다.이 함수는 N^2 만큼의 시간이 걸렸다! 한가지 예를 더 보자.. 2022. 9. 17.
1주차_알고리즘과 친해지기 최댓값 찾기 첫 번째 방법 각 숫자마다 모든 다른 숫자와 비교해서 최댓값인지 확인한다. 만약 다른 모든 값 보다 크다면 반복문 중단한다. 이중 for문을 이용해서 구현 input = [3, 5, 6, 1, 2, 4] def find_max_num(array): for num in array: for compare_num in array: if num < compare_num: break else: return num print("정답 = 6 / 현재 풀이 값 = ", find_max_num([3, 5, 6, 1, 2, 4])) print("정답 = 6 / 현재 풀이 값 = ", find_max_num([6, 6, 6])) print("정답 = 1888 / 현재 풀이 값 = ", find_max_num([.. 2022. 9. 16.
728x90

티스토리툴바