코딩기록

📌 내 코드 function solution(my_string) { const arr = my_string.toLowerCase().split("") return arr.sort().join("") } - 매개변수 문자열을 소문자로 바꿔주고 배열로 만들어 준 다음 - 오름차순으로 정렬하고 다시 문자열로 합쳐서 반 📌 다른 사람 코드 function solution(s) { return [...s.toLowerCase()].sort().join('') } - 배열과 소문자로 변경하는 것을 간단하게 전개 연산자를 이용해서 해결했다. - 변수 선언 없이 한 줄로 간결하게 작성한 것 같아 좋아보인다.

트리의 표현 방법 : 이진 트리의 각 노드는 왼쪽 또는 오른쪽 자식을 갖고 있으므로 위와 같이 표현 가능. **** 완전 이진 트리의 경우 배열로 간단하게 구현 **** 각 정점에 순서대로 번호를 붙일 수 있다. 어떤 정점의 번호가 n이면 왼쪽 자식은 2n, 오른 쪽 자식은 2n + 1 배열로 완전 이진트리 표현 트리 순회하기 트리의 모든 노드를 방문하는 순서 트리에 들어있는 자료에 접근하기 위해 순회를 해야함. 비선형 구조 트리는 정해진 순서가 존재하지 않는다. DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 방문 순서로 두가지가 있음. DFS 종류 전위 순회 중위 순회 후위 순회 DFS는 재귀호출을 사용하는 알고리즘으로, 트리의 재귀적 특성을 알아야함. 스택을 이용한다고 볼 수 있음. 서브 트리 ..

정렬된 상태를 유지하는 배열의 시간 복잡도 📌 임의의 자료들을 담고 있는 자료구조 A가 있다고 가정할 때, A는 항상 정렬된 상태를 유지해야 한다. 만약 A가 배열이라면 자료의 추가, 삭제, 탐색은 다음과 같다. 정렬된 상태를 유지하는 배열의 추가와 삭제 연산은 O(n)의 시간 복잡도를 가진다. 이진 탐색을 이용하면 정렬된 배열 내에서으 자료 탐색을 o(logn)만에 수행할 수 있다. 📌 이진 탐색 정렬된 배열의 중간값과 찾는 값의 크기를 비교하고 중간값보다 작은 경우에는 중간값을 기준으로 좌측, 중간값보다 큰 경우에는 우측을 대상으로 다시 탐색 ex) 상대방이 생각하고 있는 숫자 맞추기(업 다운 게임) : o(log100) = 6.64…이므로 숫자 맞히기까지 걸리는 횟수로 최악의 경우 7회임 📌 이진 ..

트리 : 트리는 그래프의 특수한 형태 중 하나 그래프 정점과 간선으로 이루어져 있는 자료구조간선 - 정점 간의 관계를 나타냄 정점 - 자료, 상태 등 뭔가를 담고 있음. (노드라고도 표현) 어떤 정점에서 간선을 통해 다른 정점으로 이동할 수 있음. 다른 정점으로 이동하기 위해 거치는 모든 정점을 경로라고 함. 정점 4에서 정점 6으로 이동하는 경로들 중 하나는 4→5→3→6이 될 수 있음. - 그래프의 간선은 방향이 있을 수도, 없을 수도 있다. - 방향이 있는 간선이 있는 그래프를 유향 그래프 라고 함. - 처음시작한 정점으로 다시 돌아오는 경로를 ‘사이클’ 이라고 함. - 3 → 6 → 7 → 3 은 사이클 트리 : 그래프 중 특별한 성질을 갖는 그래프를 트리라고 함. = 사이클을 갖지 않는 그래프 ..

주문 처리하기 : 주문을 들어온 순서대로 처리. 단 vip의 주문은 우선 순위가 높음 : 주문에 대한 정보는 (t, d) 형태로 주어지 며 t는 주문이 접수되는 시각, d는 주문을 처리하는 데 드는 시간 요세푸스 순열 1번부터 n번까지 번호를 가진 n명이 있다. 1번부터 순서대로 세었을 때 k번째 사람을 원에서 제거 제거된 사람의 다음 사람부터 k번째 사람을 원에서 또 제거 ..반복 제거된 사람들의 번호를 순서대로 나열한 것을 요세푸스 순열이라고 함. 💡 요세푸스 순열 과정 💡 원을 k - 1번 반시계 방향으로 회전 시켰을 때 12시 위치에 있는 사람이 제거되는 걸로 바꾸기 12시에 있는 사람을 시작으로 보고, 1번부터 n번까지 큐에 저장. 큐에 저장된 자료가 모두 제거될 때까지 아래 작업 반복 (a) ..

올바른 괄호인지 판단하기 :짝이 맞는 지 확인하기 각 괄호를 하나씩 처리하기 괄호 문자열 특징 알아보기 특징 나중에 등장한 여는 괄호는 항상 먼저 등장한 여는 괄호보다 먼저 완성 닫히지 않은 괄호가 존재하면 올바르지 않음. 여는 괄호가 남김 없이 모두 완성되어야함. 올바른 괄호인지 판단하기 - 예시 괄호를 처음부터 하나씩 검토하기 여는 괄호라면 스택에 넣고, 닫는 괄호라면 스택에서 하나 제거 괄호 문자열을 처리한 결과에 따라 값 반환= (b) (a)가 아니거나, 스택이 비어있는 상태에서 닫는 괄호가 입력되었다면 올바른 괄호가 아님. = (a) 괄호 문자열을 모두 처리하고 나서 스택이 비어있다면 올바른 괄호 계산 순서 정하기 입력되는 닫는 괄호와 대응하는 여는 괄호를 찾기 스택에 저장하는 값을 ‘여는 괄호..

스택, 큐의 개념 대표적인 자료구조의 예시 선형구조 - 스택, 큐 : 자료가 순서를 가지고 연속되어 있음. 비선형 구조 - 트리, 그래프 : 선형 구조에 해당하지 않는 자료구조 스택 : 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조 스택이 지원하는 연산목록 -push : 자료 넣기 -pop : 자료 빼기 -top : 가장 위에 있는 자료 반환 -empty : 스택 비어있는지 확인 스택 과정 : 나중에 들어간 자료가 먼저 출력되서 후입선출 자료구조라고 함. 큐 : 입구와 출구가 각각 한 쪽 끝에 존재 큐가 지원하는 연산 목록 -push : 자료 넣기 -pop : 자료 빼기 -front : 가장 앞의 자료 반환 -back : 가장 뒤의 자료 반환 -empty : 큐가 비어있는지 반환 : 배열을 이용하여 구..

자료구조는 왜 공부해야하냐!! : 프로그램의 의도에 맞는 자료구조를 사용하여 효율적인 성능으로 구현하기 위해 해시 테이블 : 각 데이터(value)를 고유한 key에 대응하도록 저장하는 개념 좌) key 10101 데려와라! (ex_1학년 1반 1번 학생은 누구냐!) 우) value 데려옴 (ex_ 이름 엘리스, 성적은 100…) / 각각의 고유한 겹치지 않는 key에 대해서 데이터를 묶어줌. key가 정수이고 value 역시 정수인 Key-Value Store를 구현해보자 Key-Value쌍을 입력하는 연산은 put, 특정 Key의 Value를 조회하는 연산은 get이라고 정의 배열의 index를 key로 이용하기 배열에 value를 저장하고, 배열의 인덱스를 key로 이용하는 방식으로 구현해보자! 장..

주문 관리 시스템 : 주문 생성, 주문 제거, 주문 조회의 기능을 가진 주문 관리 시스템을 구현해야한다. 연결리스트로 구현했을 때 처리 속도가 너무 느림. (따라가면서 찾은 후 삭제 : 비효율) 연결리스트의 특정 노드를 삭제하기 위해서 그 특정 노드에 접근하는 과정이 필요. 연결리스트의 특성에 의해 특정 원소에 접근하기 위해서는 시작 원소부터 하나씩 따라가야함. 어떤 노드를 삭제하기 위해선 이전 노드와 다음 노드를 알고있어야함. 이 단점 개선 위해 연결 리스트 내에 딕셔너리를 두고, 모든 노드들의 정보를 저장하고 있도록 함. 딕셔너리: 내부적으로 해시 테이블이라는 자료구조로 동작 어떤 key에 대한 value를 o(1)의 시간 복잡도로 접근 : 주문번호에 대해 각 노드를 대응시키는 딕셔너리를 하나 만들어..

💡 양쪽이 뚫린 파이프에 구슬을 넣을거다 : 이 문제에서는 연결 리스트가 더 좋다. 좋은 해법인지 판단하는 기준은 여러가지가 있다. 코드가 간결한가? 얼마나 빠른가? 리소스를 얼마나 차지하는가? 구현 시간이 짧은가? 등등 문제 해결방법 문제를 파악한다. : 어떤 자료를 담을지, 자료에 어떤 의미가 있는지 파악 자료구조에 필요한 기능을 파악한다. : 자료를 어떻게 사용하는지 파악 문제를 효율적으로 해결하는 자료구조를 설계 및 사용한다. : 목적에 맞는 자료구조로 문제를 해결 시간 복잡도 알고리즘이 문제를 해결하는 데 걸리는 시간을 정량화하여 나타낼 수 있는 방법 일반적으로, 문제에서 주어지는 최악의 경우에 대한 소요 시간을 나타내는 데 사용. 배열 대략 몇 개의 명령이 수행되는가? 구슬을 왼쪽으로 삽입하면..