문제 www.acmicpc.net/problem/15685 알고리즘 implementation 풀이 드래곤 커브들이 주어졌을 때, 네 모서리가 모두 드래곤 커브인 1x1 사각형의 갯수를 구하는 문제입니다. 다음 세대가 시작할 때, 이전세대에서 사용했던 방향 + 1로 드래곤 커브를 진행합니다. 이때 이전세대의 마지막 부분부터 이전세대의 첫 부분 순으로 다음 세대의 처음부터 다음 세대의 마지막부분의 방향을 결정합니다. 이를 관찰하여 구현해 풀면 되는 문제입니다. 코드 #include #define rep(i, n) for (int i = 0; i N; rep(i, N) { int x, y, d, g; cin >> x >> ..
문제 www.acmicpc.net/problem/15663 알고리즘 back tracking 풀이 N개의 자연수에서 M개를 고른 수열을 출력하되, 중복한 수열을 출력해서는 안됩니다. 재귀로 푸는 문제입니다. M개의 숫자를 고르는 것을 각 단계라고 생각해보겠습니다. 수열을 완성하기 위해서는 M개의 단계마다 수를 선택해야 합니다. 현재가 $i$번째 단계일 때, 당연하게도 이전에 고른 수를 선택해서는 안됩니다. 이를 확인하기 위해서 $used$배열을 사용했습니다. $used$배열은 다른 단계에서 선택한 수를 중복하지 않게 고르기 위함입니다. 다음으로 고려해야할 부분은 같은 단계에서 중복되는 선택입니다. $N$과 $M$이 각각 3, 2이고 숫자로 2 4 4 가 주어졌다고 해봅시다. 첫 번째 2와 두 번째 4를 ..
✔ INSERT 테이블에 데이터를 넣는 SQL입니다. 기본형식은 다음과 같습니다. INSERT INTO VALUES MEMBER 테이블의 모든 COLUMN에 값을 넣으려면 다음과 같이 작성해야합니다 INSERT INTO MEMBER VALUES('A','B','C',.....) 하지만 회원가입때도 필수로 요구하는 정보도 있지만 그렇지 않은 정보도 있습니다. 특정 COLUMN만 넣으려면 다음과 같이 작성하면 됩니다. 이때 나머지 부분에는 null이 들어가게 됩니다. INSERT INTO MEMBER(ID,PWD) VALUES('DEVBELLY','111') ✔ SELECT 테이블의 데이터를 조회하는 SQL 입니다. 기본형식은 다음과 같습니다. SELECT * FROM MEMBER; -- 에스터리스크를 사용..
✔ CREATE 사용하게 될 데이터 형식을 정의하는 것. 다른 언어에서 구조체, 클래스와 비슷한 개념입니다. CREATE TABLE MEMBER( ID VARCHAR2(50), -- COLUMN이름, 데이터 형식 PWD VARCHAR2(50), NAME VARCHAR2(50), GENDER VARCHAR2(50), AGE NUMBER, BIRTHDAY VARCHAR2(50), PHONE VARCHAR2(50), REGDATE DATE ); MEMBER 라는 이름의 TABLE을 정의 하는 예시입니다. 일반적인 프로그래밍 언어에서는 데이터 형식 뒤에 변수명을 정의하지만 SQL에서는 반대로 적습니다. ✔ ALTER 테이블의 구조를 변경하기 위해 사용합니다. ALTER TABLE MEMBER MODIFY ID ..
문제 www.acmicpc.net/problem/13512 알고리즘 HLD 풀이 트리 위에서 두 가지 쿼리를 진행해야 합니다. 첫 번째는 $i$번째 정점의 색을 바꾸는 것. 두 번째는 1번 정점에서부터 $v$정점까지 가는 경로 중 첫 번째로 만나는 검은 정점의 번호를 출력하는 것입니다. 트리에서는 문제를 풀기가 어려우므로 HLD를 이용해서 쭉 펴도록 합시다. 일자 상태로 만들었다면 세그먼트 트리의 사용이 가능해집니다. 세그먼트 트리에서 인덱스가 작을수록 트리 위에서는 루트에 가깝습니다. 이러한 이유 때문에 $query$함수에서 세그먼트 트리 쿼리를 처리할 때, 왼쪽에 검은 정점이 있다면 바로 리턴을 했습니다. 오른쪽에 있는 구간은 왼쪽보다 루트로부터 멀기 때문입니다(처음으로 만나는 검은 정점이 아님). ..
문제 www.acmicpc.net/problem/17025 알고리즘 dfs 풀이 아이스크림의 형태가 주어질 때, 가장 큰 조각와 둘레의 길이를 구하는 문제입니다. 단, 가장 큰 조각이 여러 개 일때는 가장 작은 둘레를 출력해야합니다. 기초 dfs 문제입니다. 정답 pair의 갱신을 쉽게하기 위해 $cmp$함수를 작성하여 풀었습니다. 코드 #include #define rep(i, n) for (int i = 0; i N; REP(i, N) REP(j, N) { char x; cin >> x; if (x == '#') board[i][j] = 1; } REP(i, N) rep(j, N) { if (!visited[i][j..
문제 www.acmicpc.net/problem/17024 알고리즘 Greedy 풀이 인접한 지역과 거의 인접한 지역에 다른 종류의 풀을 심어야 할 때, 풀 종류의 최솟값을 묻는 문제입니다. 주어진 예제말고도 그림을 그려 특징을 파악하며 풀면 됩니다. 한 노드 A에 인접한 노드 B, C, D가 있다고 가정해봅시다. 이 노드들은 A와는 무조건 다른 종류의 풀을 사용해야만 합니다. 하지만 A를 제외한 B의 인접 노드에 풀을 심을 때는 A와 다른 종류의 풀을 심어야 하지만(A는 두칸이 떨어져 있어 거의 인접한 지역이므로) C, D에 심었던 풀을 심을 수 있음을 관찰하면 됩니다. 일반화하면 노드 중 최대 indegree값 + 1 이 정답입니다. 코드 #include #define rep(i, n) for (in..
문제 www.acmicpc.net/problem/17408 알고리즘 segment tree 풀이 점 갱신과 구간 사이의 두 값의 합의 최댓값을 묻는 문제입니다. 두 번째 쿼리는 세그먼트 트리에 최댓값을 저장하면서도 추가적으로 최댓값의 인덱스를 저장한다면 해결가능합니다. 주어진 범위가 $l, r$일 때, $query(l,r)$을 사용해서 최댓값 $M$과 인덱스 $idx$를 얻었다면 $query(l,idx-1)$와 $query(idx+1,r)$을 사용해 두 번째로 큰 값을 구하면 됩니다. 코드를 간결하게 하려고 $cmp$함수를 작성해 사용했습니다. 코드 #include #define rep(i, n) for (int i = 0; i < n; ++i) #define REP(i, n) for (int i = 1..
- Total
- Today
- Yesterday
- dfs
- sweeping
- spring
- Oracle
- 이분매칭
- 2-SAT
- DP
- bfs
- 좌표압축
- implementation
- 세그먼트트리
- spring boot
- knapsack
- 정렬
- 트라이
- dijkstra
- union find
- greedy
- 펜윅트리
- Segment tree
- kmp
- SCC
- 동적계획법
- string
- Suffix Array
- sorting
- hld
- 스위핑
- 이분탐색
- Fenwick
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |