본문 바로가기

코딩테스트

(18)
[문제풀이] 백준 2252번 줄 세우기 문제 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다. 일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오. 문제..
[문제풀이] 백준 1922번 네트워크 연결 문제 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.) 그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용..
[알고리즘] - 위상정렬 Topology Sort 정렬 알고리즘의 일종인 위상정렬 알고리즘은 '순서가 정해져 있는 일련의 작업을 수행할때' 사용하는 알고리즘이다. 즉 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 정렬하는 것을 위상정렬이라고 한다. 예를들면 선수과목을 생각하면 편하다. B라는 과목을 듣기 위해서 A라는 과목을 필수로 들어야 한다는 것과 동일하다. 즉 순서가 정해져있는 일련의 작업을 의미하게 된다. Toplogy Sort Algorithm 위상정렬 알고리즘은 다음 순서로 동작한다. - 진입차수가 0인 노드를 큐에 넣음 - 큐가 빌때까지 다음 과정을 반복 - 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거 - 새롭게 진입차수가 0이 된 노드를 큐에 넣음 만약 이 과정에서 모든 원소를 ..
[알고리즘] 서로소 집합 - Disjoint Sets 서로소 집합 서로소 집합은 공통 원소가 없는 두 집합을 의미한다. 예를 들어 {1, 2}와 {3, 4}의 집합이 있다면 두 집합은 서로 서로소 관계이다. 만약 여기에 {2, 3} 의 관계를 나타낸다면 모두 서로소 관계가 아닌 것을 확인할 수 있다. 서로소 개념은 그래프 알고리즘에서 중요하게 사용되는 경우가 있어서 잘 알아두어야 한다. 그래서 서로소 집합 자료구조 (union-find 자료구조)는 서로소 부분 집합들로 나누어진 원소들을 처리하기 위한 자료구조라고 할 수 있다. 이는 union과 find 두 개의 연산자를 사용한다. union은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산을 담당하고 find 연산은 특정한 원소가 속한 집합을 찾는 연산을 담당한다. 서로소 집합 알고리즘 기본적으로..
[알고리즘] 그래프 이론 그래프 이론 코딩테스트에서 그래프이론을 활용하는 문제들은 대부분 난이도가 좀 있는 편이라고 생각한다. 지금까지 공부한 내용 중에서 DFS, BFS, 최단경로 알고리즘 모두 그래프를 이용하는 개념들이다. 알고리즘 문제에서 서로 다른 객체가 연결되어있다라는 내용이 내포되어있으면 가장 먼저 그래프 알고리즘 적용 여부를 판단해보아야 한다. 그래프 그래프는 정점과 간선으로 이루어진 자료구조 형태이다. 트리 또한 그래프의 일종이지만 트리는 방향성이 존재하고, 수직적인 관계를 가지고 있지만 그래프는 수직개념, 루트노드 등과 같은 개념이 없다. 즉 그래프는 네트워크 모델에 대한 관계를 나타낼때 효율적으로 사용될 수 있다. 대표적으로 지하철 노선도를 생각할 수 있다. 정점 - vertice : 노드라고 불리며 데이터가 ..
[SQL] 레코드 삭제, 수정하기 (DELETE, UPDATE, TRUNCATE) DELETE DELETE 문은 테이블에 삽입되어있는 레코드 (행)을 삭제할때 사용되는 구문이다. DELETE FROM 테이블 WHERE 조건; DELETE문의 경우는 WHERE 뒤에 오는 조건에 해당하는 모든 레코드들을 삭제해버리기 때문에 조건문의 설계가 그만큼 중요하고, 그냥 대충 적고 쿼리 날리면 난리나는 경우가 생길 수도 있다. CREATE TABLE CUSTOMER( ID INT NOT NULL, NAME VARCHAR(20) NOT NULL, AGE INT ); 위와 같은 테이블이 있고 여기에 몇개의 레코드가 삽입되어있다고 가정해본다. 그 중에 AGE가 50이 넘는 레코드들은 모두 삭제해보도록 한다. DELETE FROM CUSTOMER WHERE AGE>50; 위 처럼 작성하게 되면 CUSTO..
[SQL] 레코드, 로우 삽입 (INSERT INTO) INSERT 테이블에 행을 추가하는 구문이다. 레코드를 추가한다고도 표현하기도 한다. INSERT INTO 테이블 (필드 목록) VALUES (값 목록); 위와 같은 구조로 만들어져 있다. INSERT INTO 뒤에 삽입하고 싶은 테이블명을 작성한다. 그리고 (필드 목록) 안에다가 내가 하나의 레코드를 삽입하는데, 이때 대입할 값들의 컬럼명(필드명)들을 쭉 나열해주면 된다. 그리고 VALUES 뒤에 (값 목록)에다가 앞에서 적은 필드 목록 순서대로 값들을 적어주면 된다. 이때 필수로 앞에서 적은 필드 목록의 순서와 개수에 맞춰서 적어주어야 한다. CREATE TABLE CUSTOMER( ID INT NOT NULL, NAME VARCHAR(20) NOT NULL, AGE INT ); 위와 같은 테이블을 ..
[SQL] 테이블 생성, 삭제하기 (CREATE TABLE, DROP TABLE) SQL (Structed Query Language) SQL은 관계형 데이터베이스 관리 시스템(RDBMS)의 데이터를 관리하기 위해 설계된 특수 목적의 프로그래밍 언어이다. 기본적으로 RDBMS에서 데이터 검색과 관리, 데이터베이스 스키마 생성과 수정, 데이터베이스 객체 접근 조정 관리를 위해 만들어졌다. CREATE TABLE SQL에서 CREATE 문은 데이터 정의 언어(DDL)에 속한다. CREATE TABLE 테이블명 ( 컬럼명 데이터타입 조건, 컬럼명 데이터타입 조건, 컬럼명 데이터타입 조건 ); 위와 같은 구조를 따라가게 된다. CREATE TABLE CUSTOMER( ID INT NOT NULL, NAME VARCHAR(20) NOT NULL, AGE INT ); 예시로 CUSTOMER라는 ..