https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 주어진 N개의 숫자 중 부분수열의 합이 S를 만족시키는 수열의 개수를 찾는 문제이다. 백트래킹을 이용해 모든 경우의 수의 수열을 뽑아낸뒤 그 수열의 합이 S를 만족시킨다면 카운트를 하는 방식으로 접근하였다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #..
Koala - 2기/A반
www.acmicpc.net/problem/1969 1969번: DNA DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오 www.acmicpc.net 이 문제는 주어진 DNA들에대해 Hamming Distance의 합이 가장 작은 DNA하나를 찾고, 그, Hamming Distance의 합을 구하는 문제입니다. *Hamming Distance : 두 DNA가 있을 때 각 위치의 뉴클오티드 문자가 다른 것의 개수 입력받은 DNA들과의 Hamming Distance 합이 최소가 되기 위해서는 각 열 별로 빈도가 가장 ..
www.acmicpc.net/problem/14620 14620번: 꽃길 2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므 www.acmicpc.net 이 문제는 가능한 씨앗의 배치를 모두 검색한 뒤, 씨앗을 중심으로 4방향이 화단에 들어오면서, 겹치지 않는 경우에 따라 세 개의 꽃을 배치하고 해당 위치의 가격을 모두 더한 값 중 최소값을 찾는 문제입니다. 이 문제를 나눠보면 첫 번째로 씨앗을 배치하는 것, 두 번째로 씨앗이 꽃이 피었을 때 겹치지 않는지 판단하는 것, 겹치지 않는 경우에서 화단의 최소값을 찾는 것으로 나눌 수 있습니다. 가장 먼저 씨앗을 배..
www.acmicpc.net/problem/1051 1051번: 숫자 정사각형 N*M크기의 직사각형이 있다. 각 칸은 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 www.acmicpc.net N*M크기의 직사각형이 있다. 각 칸은 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 단순한 브루트포스 알고리즘 문제입니다. 완전탐색을 이용해 각 칸의 숫자를 확인하고 정사각형의 꼭짓점에 해당하는 칸을 탐색하여 4개의 수가 모두 같을 시에 가장 큰 정사각형의 길이를 +1 추가하는 방식으로 풀었습니다. 전체 소스코드 더보기 #i..
www.acmicpc.net/problem/2160 2160번: 그림 비교 N(2≤N≤50)개의 그림이 있다. 각각의 그림은 5×7의 크기이고, 두 가지 색으로 되어 있다. 이때 두 가지의 색을 각각 ‘X’와 ‘.’으로 표현하기로 하자. 이러한 그림들이 주어졌을 때, 가장 비슷 www.acmicpc.net 단순 브루트포스 알고리즘 문제입니다. 5 * 7 크기의 그림 N개를 받아 두 개의 그림을 골라 서로 다른 칸의 개수가 가장 작은 경우를 찾는 문제입니다. 입력 더보기 int N; cin >> N; string map[255]; for (int i = 0; i > map[i]; 그림 2개를 뽑아서 비교 더보기 int m = 9876543, ans = 0, res = 0;..
www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 각 사람의 (몸무게, 키) 배열, 등수 배열, 등수를 세는 변수를 선언해줍니다. int num[51]; // 등수 배열 pair member[51]; // (몸무게, 키) 배열 pair를 사용하면 몸무게 배열과 키 배열을 따로 선언해주지 않아도 됩니다. 변수에 접근은 첫 번째는 first, 두 번째는 second로 하면 됩니다. pair가 익숙하지 않다면 typedef struct { int wei..
# '출석'은 정상적으로 3문제 푸신 분들이고, '보류'는 한문제 이상 푸신분들, '불이행'은 0문제 푸신 분들 입니다. # '보류'로 표시된 분들은 다음날 오전 12시까지 마무리 하시면 '출석'으로 바꿀수 있습니다. # '불이행' 3번일시 퇴출입니다. 1주차 1.11 1.12 1.13 1.14 1.15 1.16 1.17 박재병 O O O O O O O 오혁진 O O O O O O O 손수연 O O O O O O O 김강윤 O O O O O O O 서민철 O O O O O O O 오상훈 O X X X X X 2주차 1.18 1.19 1.20 1.21 1.22 1.23 1.24 박재병 O O O O O O O 오혁진 O X O O O O △ 손수연 O O O O O O O 김강윤 O O O O O O O ..
www.acmicpc.net/problem/3085 3085번: 사탕 게임 첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다. www.acmicpc.net 애니팡, 캔디 크러쉬 등의 퍼즐 알고리즘과 비슷한 문제입니다. 우선 블록이 이동(교환)할 수 있는 범위를 알아보겠습니다. 가장자리가 아닌 블록들은 4가지 방향(상, 하, 좌, 우)으로 교환될 수 있습니다. 모서리를 제외한 가장자리 블록들은 3가지 방향으로 교환될 수 있습니다. 모서리 블록들은 2가지 방향으로 교환될 수 있습니다. 위 조건을 지키면서 모든 블록을 교환하고, 점수를 계산한 뒤 최대 캔디 개수를 구하면 됩니다. 저 같은 경우에는 row, col 값을 넣으면 해당 블록을 중심으로 상하, 좌우에 연속된 같은 캔디 개수를 세는 함수를..
