본문 바로가기

알고리즘 온라인 저지/BOJ

 (34)
BOJ 14890번 경사로 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 백준 14890 경사로 문제는 오래간만에 풀어보는 구현 문제였다. 사실 깡구현에 가깝기 때문에 한 경로가 경사로 건설을 통해 이동 가능한지 판별하는 아이디어 부분만 설명하고자 한다. 특별한 알고리즘을 요구한다는 느낌이 없었기 때문에 이러한 느낌으로 직접 구현했다. 만약 더 좋은 아이디어가 있다면 가르침을 바랍니다. code: GitHub - YoungWoo93/algorithmOnlineJudge: 알고리즘 온라인 저지 알고리즘 온라인 저지. Contribute to YoungWoo93..
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번 통나무 자르기 문제는 이분 탐색에 미숙하던 과거의 나에게 충격을 줬던 문제다. 과거 이분 탐색을 사용할 때 에는 정해진 크기의 배열 (또는 벡터 등)이 있을 때, 저장된 데이터에 대하여만 이분 탐색을 수행했었다. 하지만 이런 유형의 문제를 풀고 난 뒤, 하나의 고정관념이 사라졌다. 저장되있지 않은 대상에게도 이분 탐색을 적용할 수 있다는 깨달음을 얻은 것이다. 우선 문제 자체는 이분 탐색을 이용하면 간단한 문제이므로 이분탐색 알고리즘 자체에..
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 사실 덱만 사용하면 정말 간단한 문제이다. 우선 덱에 순서대로 값을 ..
BOJ 9527번 1의 개수 세기 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net 이 문제는 이진수에 대한 이해와, DP를 잘 응용할 수 있는지를 묻는 문제라고 느꼈다. 동적 계획법, 또는 DP 에 대해 잘 모른다면 아래의 더보기 포스팅을 참고하자. 더보기 알고리즘 : 동적 계획법 (Dynamic Programming, DP) 동적 계획법은 메모리를 추가로 사용하여 속도를 향상시키는 일종의 테크닉이다. 동적 계획법(이하 DP)은 코딩 테스트 등의 알고리즘 문제를 풀 때 강한 위력을 보이는데 사실 DP 개념은 단지 알 ..

티스토리툴바