IT 꿈나무 참다랑어

동적계획법(dynamic programming, dp)는 큰 문제를 작은 문제로 나누어서 푸는 방법을 일컫는 말이다. 분할정복(Divide and Conquer)와 비슷하지만 분할정복은 큰문제를 작은 문제로 나누어 해결하고 나누어진 작은 해결법들을 다시 합쳐가면서(작은 문제에서 반복이 일어나지 않음) 문제를 해결하고, 동적계획법은 작은 부분문제들이 답이 바뀌지 않고 같은 값을 가지며 큰 문제를 해결해 나가는 것에 차이가 있다. 반복되는 규칙(점화식)을 가지고 문제를 풀어나가는 경우가 많으며 작은 수부터 차례로 접근하며 규칙을 찾아 이를 해결해야한다. 구현법은 bottom-up과 top-down 방식이 있는데, bottom-up은 반복문을 통해 처음부터 문제를 풀어나가고, top-down방식은 재귀함수를 ..

이번 주는 그래프 이론과 깊이 우선탐색(dfs), 넓이 우선 탐색(bfs)에 대해서 살펴보았다. 먼저 그래프는 사물이나 개념 간의 연결관계를 수학적 모델로 단순화하여 표현한 것으로 프로그래밍으로 이를 표현하기 위한 방법으로는 대표적으로 인접 행렬과 인접 리스트 방식이 있다. 문제의 조건에 따라 효율적인 방식을 골라 이용하는 것이 중요하다. 인접 행렬은 인접 리스트보다 비교적 dense한 조건 하에 사용하는 것이 더욱 효율적이고 반대로 인접 리스트는 sparse한 조건 하에 사용하는 것이 더욱 효육적이라고 볼 수 있다. 그리고 각각의 방식으로 표현된 그래프는 그 탐색을 위해 dfs와 bfs 방식을 사용할 수 있다. 먼저 dfs(깊이 우선 탐색) 방식은 가지 하나를 길게 탐색에 이용하는 방식으로 이해했다. ..

https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net https://www.acmicpc.net/problem/11025 11025번: 요세푸스 문제 3 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000,000) www.acmicpc.net 요세푸스 문제는 n명의 사람이 ..

https://www.acmicpc.net/problem/4641 4641번: Doubles 2~15개의 서로 다른 자연수로 이루어진 리스트가 있을 때, 이들 중 리스트 안에 자신의 정확히 2배인 수가 있는 수의 개수를 구하여라. 예를 들어, 리스트가 "1 4 3 2 9 7 18 22"라면 2가 1의 2배, 4가 2의 www.acmicpc.net #include using namespace std; void findDouble(int* num); int main() { int num[15] = { 0, }; int temp = -2, i = 0; //초기값을 0으로 주니까 while 에서 함수를 실행하길래 //입력값은 자연수만 주니까 -2로 temp를 선언 while (temp != -1) { cin >..

https://www.acmicpc.net/problem/2999 2999번: 비밀 이메일 정인이는 원래 "bombonisuuladici"를 보내려고 했다. 이 메시지는 16글자이므로, 정인이는 1*16, 2*8, 4*4 행렬을 선택할 수 있다. R이 가장 큰 것은 4*4이므로, 4*4를 선택한다. 정인이가 만든 행렬은 다음과 www.acmicpc.net 아직 이차원 배열의 indexing 이 익숙하지 않아서 인덱싱 순서를 생각하는데 가장 오래걸렸다. 예시는 n*n 짜리 이차원 배열을 이용하는데 n*m짜리 배열을 돌려보니 문자가 이상하게 나왔다. 그래서 어디가 틀렸는지 디버거 이용해서 하나하나 본다고 좀 오래걸렸다. #include #include using namespace std; int main()..

백준 문제 11720번에 대한 이야기. string 형태, 즉 char[] 형의 input 이 주어졌을때 이를 어떻게 숫자로 변환해서 합을 구할것인가 나는 처음에 이 문제를 봤을 때 그냥 (int)문자 쓰면 되는 거 아닌가?하고 생각했다. 그리고 아스키코드를 까맣게 잊고 있었기 때문에 출력이 너무 이상하게 나오고 있었다. 입력은 char 배열에 숫자 하나씩 잘 들어가는데 (int)로 형변환만 해주고 나서 sum 으로 합을 구하니 자꾸 합이 255 가 나왔다. 문제는 다음과 같다. 입력 첫줄에 정수의 개수 N이 주어진다. 두번째줄에 0≤x≤9인 정수가 N개 주어진다. ex) 5 54321 출력 입력받은 숫자들의 합을 출력한다 ex) 15 그래서 아스키코드를 다시한번 검색해보았다. 아스키코드표를 살펴보면 아..

요즘 복습 겸 백준 단계별 풀이를 하고 있는데 while을 이용하면서 다른 종료에 대한 조건(ex. a+b 계산에서 a,b가 둘다 0이면 종료) 없이 입력이 끝나면 프로그램을 종료하는 문제(백준 10951번)를 처음 작성하게 되었다. 학교에서 그래도 프로그래밍 수업을 은근 들었는데 한번도 eof를 이용한 종료를 써본 기억이 없다니..ㅋㅋㅋㅋㅋㅋ 아무튼 문제의 조건은 다음과 같다. input - 한 줄에 두 숫자 a, b가 입력된다. - 총 몇 개의 테스트케이스가 있을지는 알 수 없다. output - 입력이 종료될 때까지 a + b를 출력한다. 입력예제 1 1 2 3 3 10 5 1 2 7 2 1 출력예제 2 5 13 6 9 3 처음에 cin >> a >> b를 이용해서 a==EOF일때 프로그램을 종료하..

제약조건 : 데이터의 무결성을 지키기 위해 제한된 조건을 의미한다. 중복을 허용하지 않거나, NULL 값을 허용하지 않거나 등의 데이터를 입력받는 것에 있어 실행되는 검사 규칙을 의미한다. 제약조건의 종류 PRIMARY KEY : 중복 X, NULL X. UNIQUE KEY : 중복 x, NULL o, FOREIGN KEY : 중복 o, 타 자료를 참조(references)하여 사용하는 key. 예를 들어 학생정보 테이블에 수강 정보가 같이 들어있다면 여러 과목을 수강할 때 학생정보를 기본키로 사용할 수 없다(학생 정보가 중복으로 들어가기 때문). 이럴 때는 수강 정보 테이블을 따로 두어 중복을 허용할 수 있다.) NOT NULL : Null을 허용하지 않음 Default CHECK PRIMARY KEY..

ALTER: 이미 생성되어 있는 테이블의 column을 편집할 때 사용. 기본적인 형식은 ALTER table TABLENAME 명령어 column COLUMNNAME 속성; 으로 구성되어 있으며 각 명령어마다 약간씩 속성이 다르기도 하다. 또한 ALTER는 column을 수정하는 명령어이기 때문에 column은 생략해도 상관이 없다. ADD : 새로운 column을 추가할 때 사용하는 명령어. column의 이름과 Type은 필수 입력 대상이고 추가적으로 NULL값이나 Key, Default, Extra 에 대한 설정도 입력할 수 있다. 위치에 대한 default 값은 맨 뒤에 추가되는 것이며 AFTER, FIRST 등으로 추가되는 위치를 조정해줄 수 있다. 동일한 이름을 가진 column을 추가하는 ..

이번에는 약품의 정보를 담은 데이터베이스를 만들고 정보를 조회해보자. 해야할 일은 다음과 같다. 1. 약품의 정보를 담을 데이터베이스(MedicineDB)를 만든다. 2. 약품의 정보를 담을 테이블(MedicineList)를 만든다. - 내부의 정보는 다음과 같다. 약의 이름(MedicineTitle, varchar(20)), 용도(Purpose, varchar(10)), 가격(Price, int), 용량(gram, double) 3. 총 10개의 약품 정보를 입력한다. 4. 다음의 조건들을 적용하여 정보를 조회한다. 1) 약품의 모든 항목 조회 2) 약품의 이름과 가격만 조회 3) 약품의 종류만 중복 없이 조회 4) 감기약 또는 항우울제만 조회 5) 감기약이면서 가격이 5000원 이하인 데이터 조회 1..