내 이야기 (70) 썸네일형 리스트형 BOJ 13334번 철로 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 백준 13334번 철도 문제는 우선순위 큐를 이용한다면 의외로 간단하게 풀 수 있는 문제다. 우선순위 큐에 대하여 잘 모른다면 아래의 더보기 포스팅을 참고하자. 더보기 자료구조 개념 : 우선순위 큐 (Priority Queue) + 힙 (Heap) 우선순위 큐는 일반적인 선입 선출형의 큐에 우선순위를 추가한 개념이다. 비유하자면 에버랜드나 롯데월드 등 에서 놀이기구를 타기 위해 줄을 선 것이 일반적인 큐라고 하자.. BOJ 1937번 욕심쟁이 판다 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 백준 1937번 욕심쟁이 판다 문제는 정답을 구하기 위한 DFS와 속도를 늘리기 위한 DP를 조합하여 풀 수 있다. 깊이 우선 탐색(DFS)과 동적 계획법(DP)에 대해 잘 모른다면 아래의 더보기 포스팅을 참고하자. 더보기 알고리즘 : 깊이 우선 탐색(DFS) 우선 그래프, 트리, 스택 자료구조에 대해 모르고 있다면 아래의 포스팅을 우선 확인하는 것이 좋다. 더보기 2022.06.27 - [알고리즘 온라인 저지/알고리즘 | 자료구조] - 자료구조 그래.. BOJ 1114번 통나무 자르기 1114번: 통나무 자르기 첫째 줄에 두 개의 수를 출력한다. 첫 번째 수는 가장 긴 조각의 길이이고, 두 번째 수는 그 때 처음 자르는 위치를 출력한다. 만약 가능한 것이 여러 가지라면, 처음 자르는 위치가 작은 것을 출 www.acmicpc.net 백준 1114번 통나무 자르기 문제는 이분 탐색에 미숙하던 과거의 나에게 충격을 줬던 문제다. 과거 이분 탐색을 사용할 때 에는 정해진 크기의 배열 (또는 벡터 등)이 있을 때, 저장된 데이터에 대하여만 이분 탐색을 수행했었다. 하지만 이런 유형의 문제를 풀고 난 뒤, 하나의 고정관념이 사라졌다. 저장되있지 않은 대상에게도 이분 탐색을 적용할 수 있다는 깨달음을 얻은 것이다. 우선 문제 자체는 이분 탐색을 이용하면 간단한 문제이므로 이분탐색 알고리즘 자체에.. 자료구조 개념 : 우선순위 큐 (Priority Queue) + 힙 (Heap) 우선순위 큐는 일반적인 선입 선출형의 큐에 우선순위를 추가한 개념이다. 비유하자면 에버랜드나 롯데월드 등 에서 놀이기구를 타기 위해 줄을 선 것이 일반적인 큐라고 하자. 모든 손님은 먼저 온 순서대로 놀이기구에 탑승할 수 있다. 그런데 언제부터인가 Q패스, 매직 패스의 개념이 생기며 대기열에도 우선순위가 생겼다. 이제 놀이기구 대기열은 아래와 같이 우선순위 큐처럼 동작한다. 1. 일반 손님은 먼저 온 순서대로 놀이기구에 탑승할 수 있다. 2. Q패스, 매직 패스처럼 일반 대기열을 쓰지 않고 빠르게 탑승할 수 있는 대기열이 존재한다. 즉 우선순위 큐를 이해하기 위해서 큐에 대한 이해가 선행되어야 한다. 또한 일반적인 우선순위 큐를 구현하데 가장 효율적이라 평가되는 힙을 설명할 것 이기 때문에 트리에 대해서.. BOJ 2342번 Dance Dance Revolution 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 이 문제는 너비 우선 탐색과, DP를 응용할 수 있는지를 묻는 문제라고 느꼈다. 너비 우선 탐색, 또는 DP에 대해 잘 모른다면 아래의 더보기 포스팅을 참고하자. 더보기 알고리즘 : 너비 우선 탐색(BFS) 우선 그래프, 트리, 큐 자료구조에 대해 모르고 있다면 아래의 포스팅을 우선 확인하는 것이 좋다. 더보기 2022.06.27 - [알고리즘 온라인 저지/알고리즘 | 자료구조] - 자료구조 그래프 (graph) 자료구 dev-.. BOJ 10815번 숫자 카드 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 해당 숫자가 존재하는지 탐색하면 되는 문제이다. 하지만 숫자의 개수가 매우 많기 때문에 선형 탐색으로는 시간 초과를 받게 된다. 그렇다면 더 빠른 탐색 알고리즘을 사용하면 되는데 대표적으로 이진 탐색 알고리즘을 이용할 수 있다. 이진 탐색에 대하여 잘 모른다면 아래의 더보기 링크를 확인하자. 더보기 알고리즘 : 이진 탐색 (=이분 탐색, binary search) 이진 탐색은 정렬이 되어있는 N개의 데이터를 대상으로 log(N) 시간.. BOJ 5430번 AC 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 이 문제는 덱에 대하여 알고 있는지를 묻는 문제라고 느꼈다. 덱 자료구조에 대하여 잘 모른다면 아래의 더보기 포스팅을 참고하자. 더보기 자료구조 덱(deque, dequeue) 자료구조 덱은 Double Ended QUEue의 축약어로, "deck"으로 발음하게 되어있다. 하지만 데크, 디큐 등의 표기나 발음이 존재할 수 있기 때문에 문맥에 맞는 내용을 선택하자. (사실 '디큐'는 값을 꺼내는 dev-game-standalone.tistory.com 사실 덱만 사용하면 정말 간단한 문제이다. 우선 덱에 순서대로 값을 .. 자료구조 덱(deque, dequeue) 자료구조 덱은 Double Ended QUEue의 축약어로, "deck"으로 발음하게 되어있다. 하지만 데크, 디큐 등의 표기나 발음이 존재할 수 있기 때문에 문맥에 맞는 내용을 선택하자. (사실 '디큐'는 값을 꺼내는 디큐잉이랑 혼동되기 때문에 거의 본 적이 없다.) 덱의 풀네임인 double ended queue에서 알 수 있듯 기본적으로 큐의 동작을 양방향으로 지원하는 자료구조이다. 우선 큐에 대하여 잘 모른다면 더보기의 큐를 선행 학습하고 돌아오자. 더보기 자료구조 큐 (queue) 큐는 선입 선출(First In First Out : FIFO) 형태의 자료구조이다. 큐는 들어온 순서를 이용하는 기능에서 적절하게 사용할 수 있다. 더보기 들어온 순서를 이용하기 위해 큐를 이용한 예시 : 2022... 이전 1 2 3 4 5 ··· 9 다음
