본문 바로가기

전체 글

DFS, BFS
알고리즘/기본 문법 2022. 8. 2. DFS, BFS 이번주차는 그래프이론과 DFS(깊이우선탐색), BFS(너비우선탐색) 그리고 트리순회인 preorder, inorder, postorder를 다루겠습니다. 그래프이론 그래프이론은 오일로경로, SCC, 단절점 등의 어려운 개념들도 많고 넓은 범위를 다루는 이론이지만 이 주차에서는 코딩테스트에 자주 나오며 그래프이론의 기본을 배워보겠습니다. ​ 정점과 간선 "어떠한 곳이나 어떠한 사람"으로 부터 "무언가로 간다"라고 했을 때 "어떠한 곳이나 어떠한 사람"은 정점(Vertex)이 되고 "무언가로 간다"는 간선(Edge)이 됩니다. 필자가 위 그림처럼 어떤 아파트로 간다고 해봅시다. 저와 아파트는 하나의 정점이고 거기로 가는 길은 간선이 됩니다. 필자가 어떤 사람을 좋아한다고 해봅시다. 필자와 어떤 사람은 정점이..
<백준 4375번> 1
알고리즘/백준 2022. 7. 29. <백준 4375번> 1 문제 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다. 출력 1로 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력한다. 예제 입력 1 3 7 9901 예제 출력 1 3 6 12 문제 분석 이 문제는 나머지 연산의 원리를 알아야 시간초과가 안나고 풀 수 있다. 만약 1부터 11111...1111까지를 대입해서 풀다보면 당연히 시간초과가 날 수 밖에 없다. 나머지 연산은 다음과 같다. '(A+B)%C와 (A%C + B%C)%C는 같다' 위 공식을 해당 문제에 대입하여 풀 경우, 1. N=7 2. 1..
<백준 1629번> 곱셈
알고리즘/백준 2022. 7. 29. <백준 1629번> 곱셈 문제 자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. 출력 첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다. 예제 입력 1 10 11 12 예제 출력 1 4 접근방법 예를 들어 2를 10번 곱한다면 2를 10번 곱하는 것은 2를 5번 곱하는것과 2를 5번 곱하는 것의 곱이다. 계속 쪼개나간다. 즉, 쪼개서 표현할 수 있고 겹치는 부분은 메모이제이션으로 이미 계산한 것을 저장해둔다. (분할 정복) 1. 반으로 쪼개는 것을 생각 2. 재귀함수 활용 3. 기저 사례 확인 ..
<백준 3986번> 좋은 단어
알고리즘/백준 2022. 7. 29. <백준 3986번> 좋은 단어 문제 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 깨고 말았다. 안타깝게도 자는 동안 키보드가 잘못 눌려서 보고서의 모든 글자가 A와 B로 바뀌어 버렸다! 그래서 평석이는 보고서 작성을 때려치우고 보고서에서 '좋은 단어'나 세보기로 마음 먹었다. 평석이는 단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓기로 하였다. 만약 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 그 단어는 '좋은 단어'이다. 평석이가 '좋은 단어' 개수를 세는 것을 도와주자. 입력 첫째 줄에 단어의 수 N이 ..
알고리즘/백준 2022. 7. 29. <백준 1940번> 주몽 문제 주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다. 갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,0..
알고리즘/백준 2022. 7. 29. <백준 1213번> 팰린드롬 만들기 문제 임한수와 임문빈은 서로 사랑하는 사이이다. 임한수는 세상에서 팰린드롬인 문자열을 너무 좋아하기 때문에, 둘의 백일을 기념해서 임문빈은 팰린드롬을 선물해주려고 한다. 임문빈은 임한수의 영어 이름으로 팰린드롬을 만들려고 하는데, 임한수의 영어 이름의 알파벳 순서를 적절히 바꿔서 팰린드롬을 만들려고 한다. 임문빈을 도와 임한수의 영어 이름을 팰린드롬으로 바꾸는 프로그램을 작성하시오. 입력 첫째 줄에 임한수의 영어 이름이 있다. 알파벳 대문자로만 된 최대 50글자이다. 출력 첫째 줄에 문제의 정답을 출력한다. 만약 불가능할 때는 "I'm Sorry Hansoo"를 출력한다. 정답이 여러 개일 경우에는 사전순으로 앞서는 것을 출력한다. 예제 입력 1 AABB 예제 출력 1 ABBA 예제 입력 2 AAABB ..
자료구조 정리
CS/자료구조 2022. 7. 27. 자료구조 정리 자료구조와 C++ 자료 구조(data structure)는 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합 #include // --- (1) using namespace std;// --- (2) string a;// --- (3) int main(){ cin >> a;// --- (4) cout
데이터베이스의 기본
CS/데이터 베이스 2022. 7. 27. 데이터베이스의 기본 - 데이터베이스 : 일정한 규칙, 혹은 규약을 통해 구조화되어 저장되는 데이터의 모음 SQL(관계형 데이터베이스)과 NoSQL(비 관계형 데이터베이스)로 나뉨 - 관계형 데이터베이스(RDBMS) : 행과 열을 가지는 표 형식 데이터를 저장하는 형태의 데이터베이스를 가리키며 SQL이라는 언어를 써서 조작함. - NoSQL 데이터베이스 : SQL을 사용하지 않는 데이터베이스를 말하며 유연한 스키마, 확장성이 특징 SQL(관계형 데이터베이스) SQL을 사용하면 RDBMS에서 데이터를 저장, 수정, 삭제 및 검색 할 수 있음 관계형 데이터베이스에는 핵심적인 두 가지 특징이 있다. 데이터는 정해진 데이터 스키마에 따라 테이블에 저장된다. 데이터는 관계를 통해 여러 테이블에 분산된다. 데이터는 테이블에 레코드로 저..

티스토리툴바