전체 글
-
[BOJ 2447, Python 3] 별찍기 - 10알고리즘/BOJ 2021. 9. 21. 13:12
https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 풀이 예제를 보면 $3^n \times 3^n$으로 된 정사각형에서 가운데가 텅 비어있고, $3^{n-1} \times 3^{n-1}$이 텅 비어있고, .... 이렇게 모든 정사각형에서 가운데가 텅 비어있는 정사각형을 그리는 것이 목표입니다. 그래서 분할정복을 사용하여 가운데를 공백으로 만들어주고 -> 이전 정사각형보다 세 배 작은 정사각형들의 가운데를 공백으로 만들어주..
-
[BOJ 5719, Python 3] 거의 최단 경로알고리즘/BOJ 2021. 9. 17. 11:44
https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 클래스 6을 취득했으니 이제 단계별로 풀어보기도 공부해야겠네요 풀이 P의 값이 여러가지이므로 최단경로를 구하는 알고리즘은 다익스트라를 생각해볼 수 있습니다. 거의 최단 경로는 최단 경로에 포함되는 모든 도로들을 제외한 도로로 이루어진 최단경로입니다. 최단 경로에 속하는 모든 도로들을 제외하려면 일단 adj 배열은 2차원 리스트로 하면 도로를 찾는데 O(N), 삭제를 ..
-
[BOJ 16282, Python 3] Black Chain알고리즘/BOJ 2021. 9. 16. 13:07
https://www.acmicpc.net/problem/16282 16282번: Black Chain n개의 블랙 고리가 일렬로 연결된 체인이 있다. 블랙 고리 하나는 무게가 정확히 1g 이다. 이 고리들을 이용하여 1g 부터 ng 까지 가능한 모든 무게를 생성하려고 한다. 이를 위해 고리를 일부 풀어 www.acmicpc.net 풀이 고리를 끊어내서 1g부터 ng까지 모든 무게를 생성해야 한다고 합니다. 이 문제는 보자마자 저울이라는 그리디 문제가 생각났습니다. 블랙 체인 문제는 직접 고리를 끊어내서 1g부터 ng까지 모든 무게를 표현할 수 있어야하는 것이고, 위 그리디 문제는 주어진 추들이 있을 때 이 추들을 사용해서 표현하지 못하는 최소 그램수를 출력하는 문제라 두 문제의 아이디어는 똑같습니다. ..
-
[BOJ 6549, Python 3] 히스토그램에서 가장 큰 정사각형알고리즘/BOJ 2021. 9. 15. 23:56
https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 풀이 이 문제는 다양한 풀이가 있는데 저는 세그먼트 트리를 이용한 분할 정복 풀이를 사용하였습니다. 먼저 arr[0] ~ arr[n-1]의 모든 구간을 잡은 뒤, 세그먼트 트리를 이용하여 가장 낮은 높이의 최솟값을 찾습니다. 그래서 (구간 길이) * (제일 작은 높이)를 구하여 답을 갱신시켜준다음, 이 가장 낮은 높이를 가진 인덱스를 기준으..
-
Ch 05. 기본 SQL학교 수업/2-2 데이터베이스 기초 2021. 9. 14. 18:50
SQL 소개 상업적 관계 데이터베이스의 표준 언어 포괄적인 데이터베이스 언어 데이터 정의, 질의, 갱신을 위한 문들을 가지고 있음(데이터 정의어 DDL과 데이터 조작어 DML을 포함함) 기능 데이터베이스에서 뷰를 정의함 보안과 권한 관리를 명시함 무결성 제약 조건을 정의함 트랜잭션 제어를 명시하는 기능들을 가지고 있음 JAVA와 C/C++ 같은 범용 프로그래밍 언어로 작성된 프로그램에 SQL 문들을 삽입하기 위한 기능도 제공함 SQL의 데이터 정의와 데이터 타입 SQL은 관계 데이터 모델의 릴레이션, 튜플, 애트리뷰트를 각각 테이블(표), 행, 열이라고 부름 SQL 데이터 정의어는 CREATE, ALTER, DROP이 있음 SQL안에는 schema evolution(스키마 진화)이라는 명령어가 있음 테이..
-
[BOJ 13977, Python 3] 이항 계수와 쿼리알고리즘/BOJ 2021. 9. 14. 14:02
https://www.acmicpc.net/problem/13977 13977번: 이항 계수와 쿼리 \(M\)개의 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 참조 다양한 방법의 이항계수 알고리즘 : https://koosaga.com/63 이항계수 (nCr) mod p 계산하기 nCr = n! / (n-r)! * r! 일 때, nCr mod prime을 빠르게 계산하는 방법에 대해서 얘기하려 한다. nCr 한 쿼리는 O(1)에 처리되어야 한다고 가정한다. (즉 전처리 한번 한 이후 nCr을 하나 계산하는데 O(1)) 1. O(n.. koosaga.com 페..
-
2022 KAKAO BLIND RECRUITMENT 1차 코딩테스트 후기후기/활동 후기 2021. 9. 14. 13:32
https://programmers.co.kr/competitions/1571/2022-kakao-blind-recruitment 2022 KAKAO BLIND RECRUITMENT 진행 정보 2022 KAKAO BLIND RECRUITMENT 전체 전형 절차 및 일정 지원 접수 : 8월 19일(목) ~ 9월 6일(월) 17:00 1차 코딩 테스트 : 9월 11일(토) 2차 코딩 테스트 : 9월 25일(토) 2차 코딩테스트는 1차 코딩테스트 programmers.co.kr 여름방학때 토스 코딩테스트를 보고 올해 두 번째 코딩테스트를 봤습니다. 2차 코딩 테스트는 rest api와 json 파싱을 해야한다는데 미리 이런 것을 겪어보는게 큰 도움이 될 것 같네요. 5.5솔을 하였습니다. 1번 문제 예상 티어..
-
[BOJ 1019, Python 3] 책 페이지알고리즘/BOJ 2021. 9. 13. 12:57
https://www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 풀이 1 2 3 4 5 6 7 n = int(input()) arr = [0] * 10 for i in range(1, n+1): x = str(i) for j in range(len(x)): arr[int(x[j])] += 1 print(n, '-', arr) cs 이 코드는 O(N^2)로 답을 구하는 경우인데, 첫번째 자리수의 값을 제외한 나머지 값들을 9로 설정하고 확인해보면 규칙성이 나옵니다. 9 - [0, 1, 1, 1, 1, 1, 1, 1, 1, 1] ..