전체 글 (70) 썸네일형 리스트형 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-.. 알고리즘 : 이진 탐색 (=이분 탐색, binary search) 이진 탐색은 정렬이 되어있는 N개의 데이터를 대상으로 log(N) 시간 탐색을 할 수 있는 알고리즘이다. 이진 탐색의 대상은 트리(특별히 이진 탐색을 위한 트리를 이진 탐색 트리, binary search tree라고 부른다.)가 될 수도 있고. 배열이 될 수 도 있다. (이경우 배열은 비교하기 위한 기준에 의해 정렬되어있어야 한다.) 심지어는 임의의 정수 영역에 대한 이진 탐색을 수행할 수도 있다. 만약 정렬이 되어있지 않으면 이진 탐색이 불가능하기 때문에, 이진 탐색 트리, 수 영역에 대한 이진 탐색이 아니라면 탐색의 대상을 정렬하는 행위가 선행되어야 한다. (이진 탐색 트리는 삽입 시점에서 정렬을 하면서 삽입을 한다, 수 영역은 개념적으로 정렬이 되어있다.) 포스팅의 예시는 배열을 대상으로 진행하며.. 알고리즘 : 깊이 우선 탐색(DFS) 우선 그래프, 트리, 스택 자료구조에 대해 모르고 있다면 아래의 포스팅을 우선 확인하는 것이 좋다. 더보기 2022.06.27 - [알고리즘 온라인 저지/알고리즘 | 자료구조] - 자료구조 그래프 (graph) 자료구조 그래프 (graph) 그래프는 입력된 자료들을 특정한 규칙을 이용해 관계를 맺어 줄 수 있는 형태의 자료구조이다. 예를 들면 사람들의 지인 관계는 그래프로 나타내기 좋은 형태이다. 그래프는 다양한 방법으로 dev-game-standalone.tistory.com 2022.06.27 - [알고리즘 온라인 저지/알고리즘 | 자료구조] - 자료구조 트리 (tree) 자료구조 트리 (tree) 트리는 그래프의 일종으로서 순환 관계 (= cycle)가 존재하지 않으며, 노드 간의 부모 자식 관계가.. 22년 8월 07일 해야할일 1. 운동 2. c# 공부 1) 프로퍼티 2) 델리게이트 3) 이벤트 4) 널어블 5) 리플렉션 3. DFS 제작, 포스팅 4. DP 제작, 포스팅 5. 그리디 제작, 포스팅 22년 7월 18일 해야할일 1. data struct deque 1) 구현 2) 테스트 2. ip기준 domain name 조회 domain 기준 ip 조회 함수 구현 3. stack 영역 포스팅 준비 1) 텍스트 만들기 2) 테스트 이미지 만들기 이전 1 2 3 4 5 6 ··· 9 다음
