개발자 꿈나무의 블로그

코딩테스트 연습 - 타겟 넘버 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr * 문제 설명 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버..

* 개요 Stack(스택)은 후입선출(Last In First Out - LIFO) 특성을 가지는 자료구조이다. 즉, 데이터의 삽입과 삭제가 메모리의 한 쪽 끝에서만 나타난다고 할 수 있다. 메모리에 새로 들어오는 데이터(push)의 위치가 메모리의 말단에 위치하고, 이를 '탑 포인터'라고 일컫는다. 내보내는 데이터(pop) 역시 메모리의 말단을 거친다. 스택의 추상 자료형(Abstract Data Type - ADT)을 살펴보면, 입력 연산은 push, 출력 연산은 pop이다. 조회 연산은 peek라고 하는데, 탑 포인터가 가리키는 데이터를 조회만 할 뿐, 인덱스에 변화를 주지는 않는다. 스택은 흔히 크기를 고정해서 사용하기 때문에, 이를 다 사용하면 데이터가 넘치게 된다. 이에 대한 대처방안이 존재하..

* 개요 이번 포스트에서 다룰 내용은 Circular LinkedList(원형 연결리스트)이다. 원형 연결리스트는 단순 연결리스트에서 마지막 노드가 None이 아닌 첫 노드를 참조하는 형태의 자료구조이다. 바로 원형 연결리스트에 대해 알아보도록 하자. * Circular LinkedList(원형 연결 리스트) Circular LinkedList는 리스트가 비어있지 않으면 어떤 노드도 None을 가지고 있지 않기 때문에 프로그램에서 None 조건을 검사하지 않아도 된다는 장점을 지니고 있다. 그러나 이전 노드를 쉽게 참조할 수 있었던 이중 연결리스트와는 달리, 역방향으로 노드를 순회하기 쉽지 않으며, 무한 루프가 발생할 수도 있다는 단점을 가지고 있다. 해당 단점을 보완한 원형 연결 리스트가 존재하긴 한다..

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net * 문제 초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작성하시오. * 입력 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주..

* 개요 이번 포스트에 다룰 내용은 Doubly LinkedList(이중 연결리스트)이다. 이전 노드를 참조할 수 없어 단방향으로만 노드에 접근이 가능했던 SIngly LinkedList(단순 연결리스트)와 달리 Doubly LinkedList(이중 연결리스트)는 이전 노드 참조가 가능하다. 또한 양방향으로 노드에 접근할 수 있어 삽입/삭제/탐색이 단순 연결리스트에 비해 속도가 더 빠르다는 특징이 있다. * Doubly LinkedList(이중 연결리스트) Doubly LinkedList(이중 연결리스트)는 다음 노드의 참조 뿐만이 아니라 이전 노드의 참조도 같이 가리킬 수 있다. 뒤로 탐색하는게 빠르다는 단순한 장점 외에도 한 가지 장점이 더 있는데, 단순 연결리스트는 현재 가리키고 있는 노드를 삭제하..