maker-h / groupstudy_algo_log Goto Github PK

• 아기상어 sorted(list, key=lambda x: (x[0], x[1], x[2])) 로 하면 0번째 오름차순 그 이후 1번째 원소 오름차순 그 이후 2번째 원소 오름차순으로 정렬됨
• main docs 작성자 이름 바꾸기
• 그래프 dfs, bfs 하고 문제 풀기
• 마인크래프트 문제 제외 하고 다른거 하나 추가

• 방문체크와 관련된 문제들 표시 + 특이사항으로 추가
  백준 16509 : 장군 (코드 및 해설)
  -> 상하좌우로 인접한 곳만 가지 않고, 독특한 방법으로 움직일 때 bfs 진행해보기!

6. 백준 2206 : 벽 부수고 이동하기 (코드)
   -> 글에서 '방문체크에 대해 좀 더 써봄'을 쓰게된 계기가 된 문제

7. 백준 14442 : 벽 부수고 이동하기 2 (코드)
   -> '6'에서 좀 더 진화함! 개념은 동일함.

8. 백준 1175 : 배달 (코드)
   -> 요정도 한다면 방문체크로 고생할 일도 앞으로 거의 없을것임.

9. 백준 2424 : 부산의 해적 (코드)
   -> 요정도 한다면 뭐 코테수준에서 bfs로 문제생길일은 없을 것임

https://www.acmicpc.net/board/view/27386

https://velog.io/@kimdukbae/BOJ-2206-%EB%B2%BD-%EB%B6%80%EC%88%98%EA%B3%A0-%EC%9D%B4%EB%8F%99%ED%95%98%EA%B8%B0-Python

~ 2/10

기타연산

join(self, a)

• 리스트 뒤에 a 리스트 결합
• O(1) - splice 사용

def join(self, a):
	if a.size == 0:
		return None

	splice(a.head, a.head.prev, self.head.prev)
	self.size += a.size

split(self, x)

• self를 노드 x 이전과 x 이후의 노드들로 구성된 두 개의 리스트로 분할
• 노드 x 찾기 위해서는 search 메서드 같이 사용
• O(1) - 총 6번의 연결로 이루어짐으로 상수시간 내에 해결

def split(self, x):
	tail = self.head.prev	
	
	# 기존 리스트 분리 후 양 끝단 연결
	x.prev = self.head
	self.head.prev = x.prev

	# 분리된 리스트를 새로운 리스트로 만들어준다
	new_doublylinkedlist = DoublyLinkedList()
	
	new_doublylinkedlist.head.next = x.next
	x.next.prev = new_doublylinkedlist.head

	new_doublylinkedlist.head.prev = tail
	tail.next = new_doublylinkedlist.head

	# size 조정은 아래로

size 수정 방법 (미해결)

1. 각 리스트 안 노드의 개수가 몇 개 인지 찾은 다음에 빼기 혹은 더하기. → w.c에 따르면 O(n)이 된다
2. 위의 기능을 search_idx 함수로 분리
3. 노드에 인덱스를 나타낼 수 있는 변수 추가 → O(1) 내에 가능

• #105

• #106

• #107

• #133