ABC 344 E번 복기 - 원소에 바로 접근할 수 있는 연결리스트 구현하는 법

E - Insert or Erase (atcoder.jp) E - Insert or Erase AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 수열 A의 원소들이 모두 서로 다른 원소이며, 삽입하는 연산과 삭제하는 연산을 수행한다. 연산을 수행할 때마다 A의 원소들은 모두 서로 다르다는 것이 보장된다. 연산은 2가지이다. x 원소 바로 뒤에 y를 삽입하는 연산 x를 삭제하는 연산 연결리스트로 접근해야지 생각하긴 했는데... x를 어떻게 바로 찾아야 하나 고민하다가 실패했다.. 연결리스트는 접근하는데 O(N)이라서.. 분명..

• format_list_bulleted 연결리스트
• · 2024. 3. 14.
• textsms

파이썬을 이용한 연결리스트 기본 구현 테크닉 배우기

31423번: 신촌 통폐합 계획 (acmicpc.net) 31423번: 신촌 통폐합 계획 첫 번째 줄에 대학교의 개수 $N$이 주어진다. $(2 \leq N \leq 500 \, 000)$ 다음 $N$개의 줄의 $i$번째 줄에 대학교 이름을 의미하는 알파벳 소문자로 이루어진 문자열 $s_i$가 주어진다. 주어지는 대학교 www.acmicpc.net 문제는 단순한데 s[i] 뒤에 s[j]를 그대로 붙이고, s[j] = 0으로 만든다. 이를 n-1번 순서대로 반복해서 얻은 결과를 출력하면 된다 from sys import stdin n = int(stdin.readline()) s = [0] for _ in range(n): c = stdin.readline().rstrip() s.append([c]) fo..

• format_list_bulleted 연결리스트
• · 2024. 2. 29.
• textsms

ABC 335 C번 복기 - 놓치기 쉬운 deque를 사용할 때 주의할 점(deque indexing is O(N)) + 배열과 연결리스트 접근 시간복잡도 차이

1. 문제 C - Loong Tracking (atcoder.jp) C - Loong Tracking AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 1번부터 N번까지 좌표가 있고, 1번 좌표는 쿼리에 의해 움직이게 된다. 1번 좌표가 움직이면, 2번,3번,4번,...,N번 좌표는 각각 1번,2번,3번,...,N-1번 좌표가 된다. 쿼리가 20만개이고 좌표수도 최대 100만개라 단순하게 접근하면 시간초과를 받을 것인데 그림으로 생각해보면 접근법을 생각할 수 있다 처음에 배열에 1번부터 N번까지 좌표가 있는데, ..

• format_list_bulleted Atcoder
• · 2024. 1. 7.
• textsms

자바 자료구조2 -이중 연결리스트(LinkedList)

1. 단일 연결리스트의 한계 단일 연결리스트는 결국 한방향으로만 이동할 수 있다는 한계점이 있어서 다른 방향으로 탐색하는 것이 불가능하다 때로는 다른 방향으로도 탐색하고 싶을 수 있는데 이런 문제를 해결하기 위해 next를 확장해서 특정 노드의 뒷 노드만 이어주는 것이 아니라, 앞 노드까지 이어질 수 있도록 한다. 2. 이중 연결리스트 단순히 단일 연결리스트에 새로운 노드로 prev를 추가한 것 뿐이다. 이중 연결리스트 역시 단일 연결리스트와 마찬가지로 삽입, 삭제, 탐색이 모두 가능하다. 탐색은 방향성이 양쪽에서 있다고는 하지만 어쨌든 일일이 확인해야하므로 O(N) 하지만 삽입, 삭제의 경우 해당하는 위치를 알고있다면 그냥 선을 끊고 연결해주는 작업만 하면 되므로 O(1) 이때 이중연결리스트는 한방향이..

• format_list_bulleted Java 기초
• · 2023. 2. 24.
• textsms

핵심 자료구조 기본인 단일 연결리스트(linked list) 개념파악하기

1. 연결리스트(linked list) 배열의 시간복잡도는 삽입과 삭제가 O(N)이다. 삽입과 삭제가 자주 일어나는 상황에 배열에 들어있는 원소의 수가 매우 많다면 단순한 배열은 비효율적이다. 이런 문제를 해결하기 위해 등장한 자료구조가 연결리스트(linked list) 연결리스트는 탐색은 느리지만(O(N)) 삽입과 삭제 연산이 매우 빠르다(O(1)) 따라서 삽입과 삭제가 잦은 경우에 연결리스트를 이용하면 효과적으로 문제를 해결할 수 있다. 2. 노드(node) 노드는 데이터를 담는 곳이다. 연결리스트는 여러개의 노드들의 모임이다. 연결리스트에서 하나의 노드는 데이터와 다른 노드로 이동하는 경로를 갖는다. 노드를 정의하는 방법에 따라 앞 뒤로 이동할 수 있다. 3. 단일 연결리스트 단일 연결리스트는 연결..

• format_list_bulleted Java 기초
• · 2023. 2. 24.
• textsms