Look and Find what i've done.
동전1, 동전2, 사탕가게 유사한 문제라서 모아서 풀이해보기 동전2 n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다 여기서 dp[k]는 합이 k가 되는 동전의 최소개수이다. 따라서 합이 0이 되는 동전의 최소개수는 0이기 때문에 dp[0]=0으로 세팅한다. 또한 최소값이 dp에 들어가야하기 때문에 max값으로 세팅해준다. 핵심 로직은 k가 1000원이고 100원의 동전이 있다고 했을 때 1000-100원의 동전 최소개수에 100원 동전 1개를 더하는준 것과 기존 dp[1000]을 비교하여 최소 개수를 구해준다는 것이다. #include using namespace std; int n,k..
1로 만들기 2 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 문제는 두개로 나눌 수 있다. 1. 주어진 n을 1로 만드는 최소연산횟수를 구하는 것과 2. 최소연산횟수로 1을 만드는 과정에 있는 수(경로)를 구하는 것이다. 변수 설명 dp : n을 1로 만드는 최소연산횟수 pre: n을 1로 만드는 과정에서 n에서 1개의 연산을 하고 난 후의 수. 대충 짜보자면 1 ) dp[n] = min( n%3 == 0 ? dp[n/3] + 1 : MAXN, n%2 == 0 ? dp[n/2] + 1 : MAXN, dp[n-1] + 1) 그런데 여기서 pre[n]에 들어갈 후보가 n/3, n/2, n-1 이므로 최소값인 시점에 셋 중에 무엇인지..
비트마스킹은 신기해 비트마스킹에 대해서 매일 깔짝깔짝 배우다가 예제랑 같이 배워서 이해가 뽷 됐다 비트마스킹 이용해서 백트랙킹 같은 거는 효율적으로 풀 수 있도록 연습해야겠다! 비트마스킹을 이용한 백트랙킹 비트마스킹을 이용한 백트랙킹. GitHub Gist: instantly share code, notes, and snippets. gist.github.com
백준 2583 영역 구하기 1. 좌표값으로 주어진 직사각형들을 배열에다가 표시하기 * 좌표값은 왼쪽 아래(0,0)에서부터 시작하지만 배열은 왼쪽 위부터 (0,0)이 시작한다. 내가 코드를 짜기 쉽게 처음에는 복잡한 방식으로 접근했다. 위아래 반전시켜서 좌표값이 왼쪽위부터 시작할 수 있도록 하기 위해 가로, 세로 길이를 구하고 반전시켰다. 시작점만 있으면 가로, 세로를 알 수 있기 때문에 시작점을 pair start = {m -(y1+h), x1}; // m은 배열의 세로 길이, h는 직사각형의 세로 이렇게 잡아서 직사각형을 색칠했다. => 하지만 정확한 좌표값 등을 원하지 않기 대문에 이렇게까지 할 필요가 없었다. 어차피 y값만 달라지지 커넥티드 컴포넌트의 영역과 개수, 그리고 사이즈는 달라지지 않는다. *기억해야할 것: 좌표값 ..
스택 수열, 백준 1874번 사실 스택 문제니까 좀 만만하게 봤는데 생각보다 꽤 어려웠고, 로직 외에도 다른 부분에서 신경써야할 게 많아서 까다로운 문제였다. (출력을 저장하는 부분을 주의해야한다. 처음에는 출력 저장하는 것도 push로 저장했는데, 문자열이기 때문에 +=로 추가하는 것이 성능에 좋고, 또 console.log로 한줄씩 출력해주는 게 아니라 개행문자를 사용하여 하나의 문자열로 만들어 출력해야한다. ) 특히 javascript로 된 블로그 포스트가 거의 없어서 java 코드를 참고하기도 했다. 문제: 1~n까지의 수를 오름차순으로 스택에 쌓아갈 때(push). 주어진 수열과 비교하여 수열의 인덱스 순서대로, 수열 현 인덱스와 일치하는 숫자가 스택 탑에 있을 때, 스택에서 꺼내서(pop) 수열을 만드는 문제이다. 물론 ..
동적계획법, dynamic programming 기본 동적계획법이란 하나의 문제를 한 번만 풀도록 하는 알고리즘으로. 하나의 복잡한 문제를 여러 서브문제로 나누어서 그 결과값을 저장함으로써 하나의 서브문제는 한 번만 풀도록 하여 같은 계산을 줄이는 방법이다. 그러면 동적계획법으로 풀어야한다는 것을 어떻게 판단할까? 동적계획법에는 두드러지는 두 가지 특징이 있는데 먼저 Overlapping Subproblems와 Optimal Substructure라는 특징이 있다. 아래 두 글을 번역하였다. Overlapping Subproblems Property in Dynamic Programming | DP-1 - GeeksforGeeks A Computer Science portal for geeks. It contains well written, well tho..
[DFS/BFS] 타겟 넘버 DFS/BFS 문제를 처음 풀어봤는데 알고리즘 자체는 알고 있었지만 접근 방법이 어려웠다. 1. 문제에 대한 접근을 DFS/BFS로 할 수 있다는 것을 떠올리는 게 어려웠고 처음에는 조합 공식을 이용해서 factorial을 재귀함수로 구현해서 풀었다. 하지만 런타임 에러,,, Time Complexity 문제였던 것 같은데 아직 문제를 풀 때 어떤 알고리즘이 효과적인지 감이 안 오는 것 같다. Time Complexity 생각하는 것도 다시 한 번 봐야할 듯. 2. 그래프를 나타내는 인접 리스트나 인접 행렬이 주어지지 않은 상태에서 인접 리스트나 인접 행렬을 가정하는 것이 어려웠다. 참고로 DFS/BFS 모두 적용하여 만들 수 있긴 하다. 하지만 DFS는 BFS보다 구현이 간단하고 어떤 노드에서 시작해서..
[완전탐색] 카펫 문제조건: 카페는 가로 > 세로 중간에 노란색 바닥이 있고 노란색 바닥을 갈색 바닥을 1줄로 감싸는 형태. 해결 방법: 노란색 바닥의 개수는 가로(a) => 세로(b) 가정 하에 a*b개이고 갈색의 개수는 2a + 2b + 4이다. 따라서 이 공식을 이용하면 문제를 풀 수 있다. 완전 탐색이 쓰인 부분은 a*b의 약수를 구하는 부분이다. 완전 탐색 주말엔 꼭 정리해야겠다!! function solution(brown, yellow) { let answer = new Array(2); for (let i = 1; i

티스토리툴바