데일리디벨롭

📚 문제 입력 출력 예제 입력 3 John 1.75 Mary 1.64 Sam 1.81 2 Jose 1.62 Miguel 1.58 5 John 1.75 Mary 1.75 Sam 1.74 Jose 1.75 Miguel 1.75 0예제 출력 Sam Jose John Mary Jose Miguel🧑🏻‍💻 풀이 과정 n만큼 이름(name)과 키(height)를 입력받아 리스트(names, heights)에 저장하자. 키 리스트(heights)에서 가장 큰 값을 변수(max_val)에 저장해두자. 키 리스트(heights)를 반복하면서 max_val과 같은 값을 가진 사람의 이름(name)을 ans에 저장하자. join을 사용해서 이름을 반환하자. def tall_person(n): names = [] height..

collision 이전 포스트에서 알아본 Hash table에서 발생한 collision을 해결하는 방법에는 대표적으로 2가지 방법이 있다. open addressing 방식은 collision이 발생하면 미리 정한 규칙에 따라 hash table이 비어있는 slot을 찾는다. 빈 slot을 찾는 방법에 따라 Linear Probing, Quadreatic Probing, Double Hashing으로 나뉘게 된다. separete chaining방식은 linked list를 이용한다. 만약 collision이 발생하면 linked list에 노드(slot)를 추가하여 데이터를 저장한다. Open addressing Open addressing방식은 collision이 발생하면 미리 정한 규칙에 따라 h..

📚 문제 입력 출력 예제 입력 3 Betty Boolean Alison Addaway Carrie Carryon 1 B 2 A 3 B 3 A 1 A 2 Helen Clark Margaret Thatcher 1 B 2 B 2 A 0예제 출력 1 Alison Addaway 2 Helen Clark🧑🏻‍💻 풀이 과정 학생 수 n만큼 이름을 입력 받자. 귀걸이를 돌려받은 학생을 파악하기 위해 ring_names를 만들어 인덱스 + 1(a)을 key로 입력 받아 1로 초기화하자. ring_names에 중복되는 key가 나오면 +1를 해서 2로 만들어두자. (ring_names[a] = ring_names.get(a, 0) + 1) 귀걸이를 돌려받지 못한 학생은 value가 1일 것이므로, ring_names를 반..

📚 문제 입력 출력 예제 입력 3 7 2 10 0 20 29 31 0 42 41 40 37 20 0예제 출력 134 17744 Too expensive🧑🏻‍💻 풀이 과정 moeny는 파이썬의 거듭제곱 기호 **를 이용하여 초기화해두자. 가장 적은 금액으로 부지를 구입하기 위해 입력받은 요소를 가장 큰 수부터 내림차순 정렬하자. 그래야 큰 수의 거듭 제곱을 줄일 수 있기 때문. sum을 arr[0]요소로 초기화 하고, arr[1]부터 반복하며 거듭 제곱한 결과를 계속 더하자. sum += (2 * (j ** cnt)) 거듭 제곱의 수를 1 증가시키자 cnt += 1 sum의 결과가 가진 돈 보다 크다면 Too expensive, 적다면 sum을 출력하자. def input_numbers(): numbers..

Hash table hash table은 효율적인 탐색(빠른 탐색)을 위한 자료구조로써, key-value쌍의 데이터를 입력받는다. hash function h에 key값을 입력으로 넣어 얻은 해시값 h(k)를 위치로 지정하여 key-value 데이터 쌍을 저장한다. Direct-address Table hash table을 알아보기에 앞서, Direct-address Table을 알아보자. Direct-address Table(직접 주소화 테이블)이란, key값으로 k를 갖는 원소는 index k에 저장하는 방식이다. 즉, 아래 데이터를 기준으로 key값을 index로 설정하여 index 3번에는 맹짱구를 저장하고, 5번에는 김철수, 6번 정훈이, 7번에는 남맹구를 저장한다. key: 출석번호, val..

priority queue Queue 자료구조는 먼저 집어 넣은 데이터가 먼저 나오는 선입선출(FIFO) 구조로 저장하는 형식이다. 이와 다르게 우선순위큐(priority queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다. Queue의 operation 시간복잡도는 enquque O(1), dequeueO(1)이고, priority queue는 pushO(logn), popO(logn)으로, 이는 이진완전트리를 활용한 Heap 자료구조의 push와 pop과 동일하다. Heap Heap은 완전이진트리 구조이며, 우선순위큐의 구현과 일치한다. 이러한 Heap이 되기 위한 조건은 아래와 같다. Max Heap root node에 저장된 값이 가장 큰 값이며, 각 node에 저장된 값은..

Linked List Linked List는 Node라는 구조체로 이루어져 있는데, Node는 데이터 값과 다음 Node의 address를 저장한다. Linked List는 물리적인 메모리상에서는 비연속적으로 저장되지만, 이를 구성하는 각각의 Node가 다음 Node의 address를 가리킴으로써 논리적인 연속성을 갖는 자료구조이다. 또한, 데이터가 추가되는 시점에 메모리를 할당하기 때문에 메모리를 좀 더 효율적으로 사용 할 수 있다는 장점이 있다. 데이터 삽입/삭제 Array List의 경우, 중간에 데이터를 삽입/삭제하게 되면 해당 인덱스의 뒤에 있는 모든 원소들을 shift 하기 때문에 O(n)의 시간복잡도를 갖게 된다. 하지만 Linked List는 물리적으로 옮길 필요없이 next address..

📚 문제 입력 출력 예제 입력 1 5 JOE BOB ANDY AL ADAM예제 출력 1 DECREASING예제 입력 2 11 HOPE ALI BECKY JULIE MEGHAN LAUREN MORGAN CARLI MEGAN ALEX TOBIN예제 출력 2 NEITHER예제 입력 3 4 GEORGE JOHN PAUL RINGO예제 출력 3 INCREASING🧑🏻‍💻 풀이 과정 입력 받은 names를 오름차순 정렬한 값과 일치하면 INCREASING names를 내림차순 정렬한 값과 일치하면 DECREASING 둘 다 해당 안 되면 NEITHER def line_up(names): if names == sorted(names): print("INCREASING") elif names == sorted(name..

📚 문제 입력 출력 예제 입력 1 5 11 baekjoononlinejudge startlink codeplus sundaycoding codingsh baekjoon codeplus codeminus startlink starlink sundaycoding codingsh codinghs sondaycoding startrink icerink예제 출력 1 4🧑🏻‍💻 풀이 과정 검사할 문자를 반복하며 하나씩 꺼내서 검사할 문자열과 일치하는 문자가 있으면 cnt를 1 증가시키자. def set_words(check_word): cnt = 0 for i, str in enumerate(check_word): if str in s: cnt += 1 return cnt n, m = map(int, input()..

📚 문제 입력 출력 예제 입력 1 3 1 3 2 6예제 출력 1 16예제 입력 2 4 2 4 2 3 1예제 출력 2 19🧑🏻‍💻 풀이 과정 입력받은 카드를 y만큼 반복하며, 시작마다 sort로 오름차순 정렬하자. 카드의 0번째와 1번째를 더한 뒤(오름차순 정렬했으니, 가장 작은 값임), 0번째와 1번째에 각각 대입해주자. 반복이 끝나면, 카드의 값을 모두 더하고 출력하자. #include "iostream" #include "vector" #include "algorithm" using namespace std; int x, y; vector v; void inputCards() { for (int i = 0; i > num; v.push_back(num);..