코딩 공부하는 코딩류

N개의 숫자 묶음이 주어질 때 숫자 묶음들을 비교하려면 최소 몇 번만 비교하면 되는지 구하는 문제 문제의 조건 1. 정렬된 두 숫자 묶음이 있다. 두 묶음을 각각 A, B라 하면 두 묶음을 비교하는데 필요한 횟수는 A+B번이다. 2. 10장, 20장, 40장 처럼 2개보다 많은 숫자 묶음이 있을 때 2개씩 골라서 비교를 하는데 묶음들을 고르는 순서에 따라서 횟수가 달라진다. 10장과 20장을 먼저 합친 뒤(10+20=30), 남은 40장을 합치는 경우의 수를 더했을 때 (10+20)+(30+40)=100 총 100번의 비교가 필요하다. 하지만 10장과 40장을 합친 뒤(10+40=50), 남은 20장을 합치는 경우를 더하면 (10+40)+(50+20)=120 총 120번의 비교가 필요해서 100번보다는 ..

정수가 주어질 때 주어진 정수를 1, 2, 3의 합으로 나타낼 수 있는 경우의 수를 구하는 문제 문제의 조건 1. 합을 나타낼 때엔 1개 이상의 수를 사용해야 한다. 정수 4를 1, 2, 3의 합으로 나타낸다면 다음과 같은 방법들로 나타낼 수 있다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 2. 주어지는 정수는 양수이며 11보다 작다. 즉 1 ~ 10 사이 숫자만 나온다. 3. 첫째줄에 테스트 케이스의 갯수 T가 주어지며 다음 줄부터 T 갯수만큼 한 줄마다 정수가 주어진다. 풀이 과정 DP를 연습하려고 푼 문제인데 아직 DP를 잘 못 해서 문제를 봤을 땐 당연히 풀이가 떠오르지 않았습니다. 그래서 또 구글링... 후 알게 된 이 문제의 풀이법 1-1. 정수 1을 만들 수 있는 ..

비가 내렸을 때 물에 잠기지 않을 지역의 최대 갯수를 구하는 문제 문제의 조건 1. 어떤 지역의 높이 정보가 위와 같이 주어진다. 2. 비가 4만큼 오면 위와 같이 높이가 4 이하인 지역은 모두 물에 잠긴다. 3. 이 때 하얀 부분을 물에 잠기지 않는 안전 영역이라 할 수 있는데 같은 안전 영역의 범위는 상하좌우로 맞닿은 영역들만 포함한다. 즉 이런 경우처럼 대각선 방향으로 맞닿아 있는 영역은 같은 안전 영역이라 할 수 없다. 2번의 경우에서 안전 영역의 갯수는 5개이다. 4. 6만큼 비가 와서 높이가 6 이하인 지역이 모두 물에 잠긴다면 위와 같이 나타낼 수 있다. 이 때 안전 영역의 갯수는 4개이다. 이 지역에서 비가 오는 양 별로 안전 영역의 갯수를 모두 확인해 봤을 때 최대 갯수는 5개이다. 5...

알고리즘 문제 풀다가 급 궁금해져서 찾아본 find와 find_if의 차이점 1. find, find_if 둘 다 algorithm 헤더에 정의되어 vector 안에 특정 값이 존재하는지 찾아주는 함수입니다. 하지만 find는 찾고자 하는 값의 타입에 operator== 가 정의되어 있어야 사용가능하고 그렇지 않다면 find_if에 비교식을 만들어 넣어야 한다는 점이 다르다고 볼 수 있습니다. 이렇게만 적으면 무슨 소리인가 싶으실 테니 각 함수의 정의를 보겠습니다. find template InputIterator find(InputIterator first, InputIterator last, const T& val); 맨 마지막 val 인자의 타입 T에 operator== 가 정의되어 있어야 사용 가..

민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다. 단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다. 예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다. N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오. 입력 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 ..

2021.10.24 - [코딩 공부/C 언어] - [C언어 기초] 반복문 while [C언어 기초] 반복문 while 2021.10.16 - [코딩 공부/C 언어] - [C언어 기초] 조건문 switch [C언어 기초] 조건문 switch 2021.10.10 - [코딩 공부/C 언어] - [C언어 기초] if ~ else와 else if [C언어 기초] if ~ else와 else if 2021.10.05.. hgu-can.tistory.com 오늘은 반복문 while과 함께 보면 좋은 do ~ while에 대해서 알아보려고 합니다. 1. do ~ while과 while의 차이점 이전에 배웠던 while문은 while (조건) { } 에서 while 옆의 () 소괄호 속에 쓴 조건을 만족하는 동안 실행하..

2021.04.16 - [코딩 공부/C 언어] - C 언어 기초 : 연산자 3 - 비트 연산자 C 언어 기초 : 연산자 3 - 비트 연산자 2021.04.14 - [코딩 공부/C 언어] - C 언어 기초 : 연산자 1 C 언어 기초 : 연산자 1 2021.02.07 - [코딩 공부/C 언어] - C 언어 기초 : scanf 로 원하는 데이터 입력 받기 C 언어 기초 : scanf 로 원하는 데이터.. hgu-can.tistory.com 연산자 파트에서 얘도 같이 설명하고 갔어야 했는데 까먹고 있다가 생각나서 다시 돌아왔어요..ㅎㅎ;; 2021.10.05 - [코딩 공부/C 언어] - [C언어 기초] 조건문 if [C언어 기초] 조건문 if 2021.04.16 - [코딩 공부/C 언어] - C 언어 기초 ..

주어진 수를 1로 만드는 데 필요한 최소 연산 횟수를 구하는 문제 문제의 조건 1. 1보다 크거나 같고 10^6보다 작거나 같은 정수 N이 주어진다. 2. 정수 N에 사용할 수 있는 연산은 3가지이다. 1) 3으로 나누어 떨어지면 3으로 나눈다. 2) 2로 나누어 떨어지면 2로 나눈다. 3) 1을 뺀다. 3. 위 세 가지 연산을 적절히 사용할 때 주어진 N을 1로 만들 수 있는 최소 연산 횟수를 구해서 출력하기 풀이 과정 아직 DP를 잘 몰라서 문제를 봐도 감이 잘 안 와서 풀이를 찾아봤습니다. 여러 블로그를 보고 이해한 풀이 1. DP 중에서 타뷸레이션(상향식 접근) 방식을 사용해 배열 인덱스에 해당 값을 1로 만드는 데 필요한 연산 횟수를 기록한다. 각 숫자별로 필요한 연산 횟수를 기록할 1차원 배열..