랄뚜기의 코딩일기

https://www.acmicpc.net/problem/11660 이 문제를 풀기 위해서는 dp[i][j]가 1,1부터 i,j까지 영역의 합을 나타내야 한다. 위와 같은 값이 주어졌다고 가정해보자. 배열의 각 칸에는 1,1부터 i,j까지의 영역의 합을 입력해야 한다. ?에는 1+2+5+7, 즉 15가 와야 한다. 파란 영역(1+5)과 빨간 영역(1+2)을 활용하여 ? 값을 구하기 위해서는 중복되는 부분(1)을 빼줘야 한다. 점화식을 세우면 dp[i][j]=input[i][j]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1] 이란 것을 직관적으로 알 수 있다. 이제 dp 배열을 활용하여 답을 구하면 된다. 초록색 영역의 합을 구해야 된다고 가정하자. 초록색 영역=빨강색 영역-주황색 영역-노..

https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 그냥 LCS문제인줄 알았는데 공통되는 문자열을 구해야하기 때문에 공통된 문자들이 연속적이어야 한다는게 기존 LCS문제와 달랐다. 기존 LCS에서 LCS[i][j]가 나타내는 것이 한 문자열의 i번째와 다른 문자열의 j번째까지 공통된 문자의 개수였다면 이 문제에서 LCS[i][j]가 의미하는 바는 한 문자열의 i번째와 다른 문자열의 j번째까지의 공통 부분 문자열의 크기를 저장해야 한다. ..

지정한 순서대로 쿼리 결과 반환하기 select ename, job,sal from emp where deptno = 10 order by sal asc where절 다음에 order by를 입력하여 결과 값을 정렬해준다.(오름차순이면 asc, 내림차순이면 desc) order by에는 조건이 올 수도 있다. 다중 필드로 정렬하기 select empno,deptno,sal,ename,job from emp order by deptno, sal desc 여러가지 열에 조건을 추가하여 정렬하고 싶다면 order by절에 열에 대한 조건을 , 로 나누어 입력하면 된다. 우선 순위는 order by 뒤에 오는 순서로 결정된다. 부분 문자열로 정렬하기 select ename, job from emp order b..

https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 처음에는 dfs로 풀지 않고 반복문을 돌렸다. 열을 먼저 탐색하면서 오른쪽 대각선 위, 오른쪽, 오른쪽 대각선 아래를 방문할 수 있는지 없는지 확인하고 방문할 수 있다면 check표시를 해주고 check표시가 된 경우에만 탐색을 할 수 있도록 구현하였는데 틀렸다. 반례가 있는거 같은데 못찾겠어서 그냥 모든 열 마다 dfs를 돌렸다. dfs를 돌릴 때 한 번 방문한 점은 다시 방문할 필요가 없다는 것을 주의해야 한..

https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net mst를 구하는 문제이다. 나는 disjoint_set을 이용한 kruskal 알고리즘으로 풀었다. #include #include #include #include #include #include #include #include #include #include #define INF 1000000000 #define endl '\n' #define ll long long using namespace std; vector v; int N,M,ans=0; int parent[1001]; bo..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net bfs로 풀까 고민하였지만 아무리 봐도 dfs가 구현이 쉬울거 같아서 dfs로 구현하였다. 문제는 시간초과였는데 다행히 그래프의 크기도 작고, 중복되는 알파벳은 접근하지 못한다는 조건도 있어서 많은 경우의 수가 제거되어 제 시간 안에 돌아갔다. #include #include #include #include #include #include #include #include #include #..

테이블의 모든 행과 열 검색하기 select * from emp 테이블에서 행의 하위 집합 검색하기 select * from emp where deptno=10 여러 조건을 충족하는 행 찾기 select * from emp where deptno=10 or comm is not null or sal

https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 오늘도 어김없이 문제를 제대로 읽지 않아 시간을 버렸다. 답이 3 초과인 경우를 배제해줬어야 했는데... 잘 읽어야겠다 ㅋㅋ 답이 3 초과인 경우를 배제해줬더니 시간초과가 떴다. 재귀를 돌 때 중복되는 경우가 발생하여 idx를 인자로 줘서 경우의 수를 줄여주었다. #include #include #include #include #include #include #include #include #i..

https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 저번 학기 알고리즘 설계 분석에서 배운 행렬 곱의 최소화 문제와 같은 알고리즘이다. 막상 수업시간에 이해를 하지 못했는데 이번에 다시 문제를 보면서 제대로 이해했다. 이 문제를 풀기 위해서는 위와 같은 방식으로 반복문을 돌 줄 알아야 한다. 위 처럼 반복문을 돌기 위한 코드는 다음과 같다. for(int j=1;j>K; for(int i=1;i>K_[i]; sum_[i]=sum_[i-1]..

CREATE TABLE AS SELECT city 테이블과 똑같은 city2 테이블 생성 CREATE TABLE city2 AS SELECT * FROM city; CREATE DATABASE CREATE DATABASE 문은 새로운 데이터 베이스를 생성 USE문으로 새 데이터베이스를 사용 CREATE TABLE test2( id INT NOT NULL PRIMARY KEY, col1 INT NULL, col2 FLOAT NULL, col3 VARCHAR(45) NULL ) ALTER TABLE ALTER TABLE 문과 함께 ADD문을 사용하면, 테이블에 컬럼을 추가할 수 있음 ALTER TABLE 문과 함께 MODIFY 문을 사용하면, 테이블의 컬럼 타입을 변경 할 수 있음 ALTER TABLE 문과..