[코딩테스트 합격자 되기 06] 스택 Q&A

목차질문실전 문제질문1. 스택을 이용하여 주어진 문자열을 뒤집는 알고리즘을 설계하고 구현해 보세요.이 알고리즘의 시간 복잡도와 공간 복잡도는 각각 어떻게 되나요? 스택을 사용하지 않고도 문자열을 뒤집을 수 있는 다른 방법을 설명해 보세요.- **stack 을 이용한 방법** : 주어진 문자열을 스택에 넣고, 스택에 넣은 문자열을 다시 꺼내면서 새로운 문자열을 만든다. - 시간복잡도 : 문자열의 각 문자를 한 번씩 처리하므로,m n은 문자열의 길이. - 공간복잡도 : 스택에 모든 문자를 저장하므로 O(n)의 공간 필요- **그 외 방법** : reversed 함수를 이용한다 (추후 .join()으로 각 문자열 연결 필요)2. 스택이 재귀적인 함수 호출과 어떻게 관련이 있는지 설명해 보세요.재..

• format_list_bulleted 알고리즘
• · 2024. 9. 11.
• textsms

[코딩테스트 합격자 되기 06] 스택

스택스택의 어원은 'stack' , '쌓는다' 이다. 스택은 어원에서 짐작할 수 있듯이 먼저 입력한 데이터를 가장 나중에 꺼낼 수 있는 자료구조 이다. 이때 스택에 삽입하는 연산을 푸시 push , 꺼내는 연산을 팝 pop 이라고 한다.  ADT : acstract data type추상 자료형이란 인터페이스만 있고 실제로 구현은 되지 않은 자료형이다. 일종의 자료형의 설계도. 그렇다면 스택은 어떤 정의가 필요한 자료구조일까? 언어에 따라 표준 라이브러이에서 스택 제공 여부는 다르다. 파이썬의 경우 스택을 제공하진 않지만 대안으로 리스트 메서드인 'append():가장 마지막에 원소를 넣음' 로 스택을 대체할 수 있다. 덱(deque)은 한쪽으로만 데이터 삽입, 삭제할 수 있는 스택과 다르게 양쪽에서 데이..

• format_list_bulleted 알고리즘
• · 2024. 9. 8.
• textsms

[코딩테스트 합격자 되기 05] 배열 : Q&A

기본 배열 질문파이썬에서 리스트의 장점 및 단점에 대해 말해주세요. 단점이 있다면 이를 해결할 수 있는 방법은 무엇이 있을까요? 장점 : 리스트는 한 개의 리스트에 혼합하여 다양한 자료구조를 포함할 수 있으며 확장이 쉽다. 또한 숫자나 문자열 등의 변수를 선언하지 않고도 간단하게 표현할 수 있다. 단점 : 파이썬에서는 리스트도 객체에 해당하기 때문에 복사를 하게되면 바로보는 객체가 동일하기 때문에 두 개의 리스트 중 하나만 변경해도 나머지 하나가 동일하게 수정되는 현상이 발생한다.예를 들어 a라는 변수를 선언하고 리스트를 만들어 a에 할당하면 리스트 객체의 주소가 저장된 변수가 된다. 그럼 a라는 변수의 값을 b 인자에 할당하였을 경우, b는 a와 같은 객체의 주소가 저장된 변수가 된다. 따라서 b를 불..

• format_list_bulleted 알고리즘
• · 2024. 9. 1.
• textsms

[코딩테스트 합격자 되기 05] 배열

배열 배열은 인덱스와 값을 일대일 대응해 관리하는 자료구조 이다. 데이터를 저장할 수 있는 모든 공간은 인덱스와 일대일 대응하므로 어떤 위치에 있는 데이터든 한 번에 접근할 수 있다. 배열 선언일반적인 방법 arr = [0, 0, 0, 0, 0, 0] arr = [0] * 6 리스트 생성자 사용arr = list(range(6)) #[0,1,2,3,4,5] 리스트 컴프리헨션을 활용하는 방법arr = [0 for _ in range(6)] # [0, 0, 0, 0, 0, 0]  배열과 차원배열은 2차원, 3차원 배열과 같이 다차원 배열을 사용할 때도 많다. 하지만 컴퓨터 메모리의 구조는 1차원이므로, 2차원, 3차원 배열도 실제로는 1차원 공간에 저장한다. 다시 말해 배열은 차원과는 무관하게 메모리..

• format_list_bulleted 알고리즘
• · 2024. 9. 1.
• textsms

[코딩테스트 합격자 되기 04] 코딩 테스트 필수 문법 : Q&A

챕터 질문 답변1. 리스트의 기본 개념- 리스트의 개념에 대해 정리해주세요순서가 있는 요소들의 집합. 가변적(mutable)인 데이터 타입으로 선언 이후 추가, 제거, 수정할 수 있다. 대괄호로 정의하며 각 요소를 쉼표로 구분함. 2. 리스트의 효율성- 리스트의 임의 접근의 시간 복잡도는 무엇인가요?인덱스를 이용한 임의 접근의 시간 복잡도는 O(1) 이다. 즉 상수 시간. - 리스트의 맨 앞이나 중간에 데이터를 삽입할 때 시간 복잡도가 어떻게 달라지는지 설명해주세요.삽입 위치 이후의 모든 요소들을 한 칸씩 뒤로 이동시켜야 한다. 이로 인해 시간복잡도는 O(n)이 된다. 리스트의 맨 뒤에 데이터를 삽입하는 경우는 O(n)의 복잡도를 가진다. 3. 튜플- 튜플의 개념과 리스트와의 차이점을 설명해주세요.튜플은..

• format_list_bulleted 알고리즘
• · 2024. 8. 25.
• textsms

[코딩테스트 합격자 되기 04] 코딩 테스트 필수 문법

빌트인 데이터 타입정수형 :양의 정수, 음의 정수, 0사칙연산(+ ,- ,* ,/) 외 많은 연산(비교연산, 비트연산, 논리연산 등) 가능print(a / b) # 나누기 (소수점 포함) / 3.25print(a // b) # 나누기 (소수점 제외) / 3 부동소수형 : 소수를 저장할 때 사용. 사칙연산과 정수형 나누기, 모듈러(%), 제곱 연산(**), 논리 연산 등 가능print(10.0 // 3.2) # 정수형 나누기 / 3.0print(10.0 % 3.2) # 모듈러 / 0.39999999999999947print(2.0 ** 3.2) # 제곱 연산 / 9.18958683997628 부동소수형 코드 실행 결과를 보면 10 % 3.2의 연산 결과를 보면 결괏값이 0.4가 아니라 0...

• format_list_bulleted 알고리즘
• · 2024. 8. 25.
• textsms