※ 사용언어 : 자바 ※ ▼ 문제 링크 ▼ https://www.acmicpc.net/problem/18119 문제 접근 1. 완전 탐색을 이용, 각 쿼리가 이루어질 때마다 각 단어의 알파벳을 다 기억하고 있는지 검사하면 시간 초과로 문제를 풀 수 없습니다. 그러므로 비트마스킹을 이용해 알고리즘 수행 시간을 감소시켜야 합니다. 2. 비트마스킹이란 정수의 이진수 표현을 자료구조로 이용하는 방식입니다. 3. 접근 1) 준석에는 처음에 모든 알파벳을 기억하고 있는 상태입니다. 모든 알파벳을 기억하는 변수(allAlphabet)를 하나 만들어줍니다. 알파벳은 총 26개로 0부터 시작한단 가정 아래 25개의 숫자열이 탄생하게 됩니다. 초기에는 전부 기억하고 있으니 아래 첨부된 표처럼 26개의 1이 나열된 숫자열이..

※ 사용언어 : 파이썬 ※ ▼ 문제 링크 ▼ https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 접근 1) K이 동전으로 만들어야하는 가치의 합이면, 이번 문제의 점화식은 dp[K]+=dp[K-동전의 액수] 이다. 어떤 방식으로 이런 점화식이 탄생하게 되었는지 천천히 알아보도록 하겠다. 예시) 동전의 종류=[1원, 2원, 3원]이고 가치의 합 K=5 인 경우 K를 1부터 5까지 하나씩 증가시키며, 가지고있는 동전을 점진적으로 늘려가며(처음에는 ..

※ 사용언어 : 파이썬, 자바 ※ ▼ 문제 링크 ▼ https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제 접근 1) 다이나믹 프로그래밍 알고리즘을 이용해, (1,1)부터 시작해 각 구간의 누적 합을 구한다. EX) (1,1) ~ (3,4) 까지의 구간 누적합 구하기 (3,4) 까지의 누적합은 (1,1)~(3,3) 누적합과 (1,1)~(2,4)까지 누적합을 더하고 배열[3][4]을 더하면 된다. 하지만 ..

※ 사용 언어 : 자바, 파이썬 1. O(N) 시간 복잡도의 소수 판별 소수인지 판별할 수 N의 이전 값(=N-1)까지 2부터 for 문을 돌리는 방식이다. 해당 알고리즘은 N의 값 만큼 돌아간다. 『파이썬』 N=int(input()) if(N

※사용언어 : 파이썬 ※ ▼ 문제 링크 ▼ https://programmers.co.kr/learn/courses/30/lessons/84021 코딩테스트 연습 - 3주차 [[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]] [[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]] 14 [[0,0,0],[1,1,0],[1,1,1]] [[1,1,1],[1,0,0],[0,0,0]] 0 programmers.co.kr 문제 접근 문제가 상당히 복잡합니다. 접근 방식을 그림과 함께 설명할 예정이니 차근차근 집중하여 보..

※ 사용언어 : 파이썬 ※ ▼ 문제 링크 ▼ https://www.acmicpc.net/problem/16206 16206번: 롤케이크 오늘은 재현이의 생일이다. 재현이는 친구 N명에게 롤케이크를 1개씩 선물로 받았다. 롤케이크의 길이는 A1, A2, ..., AN이다. 재현이는 길이가 10인 롤케이크만 먹는다. 따라서, 롤케이크를 잘라서 www.acmicpc.net 문제 접근 1. 자를 롤케이크의 크기가 10보다 작은 경우 자를 이유가 없기 때문에 넘겨준다. 2. 크기가 작은 롤케이크 먼저 자른다. 만약 롤케이크의 크기가 10 20 20 30 50 이 있고, 자르는 횟수 제한이 4인 경우 IF : 크기가 작은 롤케익롤케이크 먼저 자를 경우 10 사이즈의 롤케이크는 8개가 생김 IF : 크기가 큰 롤케익..