제이슨의 개발이야기

안녕하세요! 오늘은 백준 파이프 옮기기 문제를 풀어봤습니다! https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 이 문제는 그래프 탐색 문제입니다 저는 처음에 BFS 로 풀었는대 BFS로 풀면 시간 초과가 뜹니다 이유는 정확히 잘 모르겠지만 DFS로 풀면 쉽게 풀수 있는 문제 입니다 각 파이프의 오른쪽 끝에 좌표와 해당 파이프의 놓여진 방향을 저장 해 놓고 다음에 놓여진 방향에 따른 파이프의 좌표와 놓여진 방향을 DFS를 ..

https://www.acmicpc.net/problem/17827 17827번: 달팽이 리스트 첫째 줄에 노드의 개수 N(2 ≤ N ≤ 200,000), 질문의 횟수 M(1 ≤ M ≤ 200,000), N번 노드가 가리키는 노드의 번호 V(2 ≤ V ≤ N)가 공백으로 구분되어 주어진다. 둘째 줄에 N개의 정수 C1, C2, …, CN이 공백 www.acmicpc.net 달팽이 리스트 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 256 MB 1877 580 458 34.829% 문제 영진이는 달팽이를 좋아한다. 달팽이를 너무너무 좋아하기 때문에 특정한 모양의 단방향 연결리스트에 달팽이 리스트라는 이름을 붙여주었다. 일반적인 선형 단방향 연결리스트의 각 노드 번호를 연결된 순서대로 1, 2..

안녕하세요! 오늘은 Parcel 과 Parcelable에 대해서 공부하려고 합니다! Parcel은 뭘까? Parcel 은 번역하자면 꾸러미 라는 뜻으로 짐을 싸듯이 객체를 싸는 클래스가 Parcel 클래스 입니다 Parcel 클래스는 직렬화시 Container 역할을 하는 클래스로 말 그대로 꾸러미 입니다 Parcelable 은 뭘까? Parcelable은 Android에서 지원해주는 SDK에 포함되어 있는 인터페이스 입니다 Parcel은 소포, 택배라고 생각하면 쉽고 Parcelable은 택배로 부칠 수 있는 정도로 생각하면 좋을 거 같습니다 Parcelable 의 장점 Parcelable 객체는 Parcel로 만들고 풀 수 있는대 Parcelable을 이용하면 Serializable과 다르게 리플랙션..

AVL 트리 란 무엇인가? AVL 트리( Adelson-Velsky and Landis tree) 는 앞서 설명한 최악의 경우 선형적인 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진트리 입니다 두 자식 서브 트리의 높이는 항상 최대 1만큼 차이 난다는 특징이 있습니다 AVL 트리는 탐색,삽입,삭제 모두 시간 복잡도가 O(logn)이며 삽입, 삭제를 할 때마다 균형이 안맞는 것을 맞추기 위해 트리 일부를 왼쪽 혹은 오른쪽으로 회전 시키며 균형을 잡습니다 레드 블랙 트리란 무엇인가? 레드 블랙 트리는 균형 이진 탐색 트리로 탐색 , 삽입 , 삭제 모두 시간 복잡도가 O(logn)입니다 각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 비트를 저장하며 , 삽입 및 삭제 중에 트리가 균형을 유지하도록 ..