알고리즘 온라인 저지 (48) 썸네일형 리스트형 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... 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 개념은 단지 알 .. 알고리즘 : 탐욕법 (Greedy) 탐욕법은 문제의 특징을 이용해, 탐색 횟수 자체를 줄여 속도를 향상시키는 일종의 테크닉이다. 탐욕법(이하 그리디)은 휴리스틱 알고리즘으로서, 그 순간의 최적을 취해 나가는 형태로 구성된다. 휴리스틱에 대해 아직 공부하지 않은 채로 위 문장을 보면 이해가 가지 않을 것이다. 하지만 DP와 마찬가지로 그리디 또한 우리가 본능적으로 사용할 수 있는 개념이다. 우리가 본능적으로 시행하고 있는 그리디 문제를 하나 제시해 보겠다. 바구니에 구슬이 15개 있는데, 이 구슬에는 1부터 15까지의 숫자가 적혀있다. 당신은 바구니에서 구슬을 하나씩 뽑아 가져 갈 수 있는데, 구슬들에 적힌 숫자의 합이 30 이 되어야 되도록 구슬을 가져갈 수 있다. 예를 들어 9, 10, 11 구슬을 뽑으면 셋 다 가져갈 수 있지만 13,.. 알고리즘 : 동적 계획법 (Dynamic Programming, DP) 동적 계획법은 메모리를 추가로 사용하여 속도를 향상시키는 일종의 테크닉이다. 동적 계획법(이하 DP)은 코딩 테스트 등의 알고리즘 문제를 풀 때 강한 위력을 보이는데 사실 DP 개념은 단지 알고리즘 문제에 국한되지 않는다. 일상생활에서도 우리는 DP를 하고 있다. 계산 중간결과를 적어두거나, 검색해둔 정보를 다시 찾을 필요 없도록 메모장에 모아두는 행위도 DP의 개념이 일부 들어간 행동이라고 할 수 있다. DP의 대표적 예시는 N번째 피보나치수열의 값을 구하거나, N! (N 팩토리얼)의 값을 구하는 것 등이 있다. 이중 N 팩토리얼을 구하는 문제를 통해 DP의 동작을 보이려고 한다. DP의 아이디어는 "반복해서 연산을 해야하는 부분을 어딘가에 저장해 두고 재사용하자!"이다. 위의 예시에서 5 팩토리얼을 .. BOJ 2294번 동전 2 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net DP(= 동적 계획법)를 이용하면 해결 가능한 DP의 기본 문제다. DP에 대해 전혀 모른다면 더보기의 알고리즘 설명 포스팅을 먼저 읽어보자. 더보기 알고리즘 : 동적 계획법 (Dynamic Programming, DP) 동적 계획법 (이하 DP)은 문제를 풀 때 (단지 알고리즘 문제에 국한되지 않는다, 일상생활에서도 우리는 DP를 하고 있다.) 메모리를 추가로 사용하여 속도를 얻는 방법이다. (일상생활에서 메모리 dev-game-.. 이전 1 2 3 4 5 6 다음
