BangBang's Devlogs

데이터베이스 면접 질문

# 데이터베이스 기본 내용

Q. Database와 DBMS란?

A. Database는 사용자가 필요한 정보를 얻기 위해 논리적으로 연관된 데이터를 모아 구조적으로 통합해 놓은 것입니다.

DBMS는 Database Management System의 약자로 사용자와 데이터베이스를 연결시켜주는 소프트웨어입니다. 즉 DB를 관리하기 위한 시스템입니다. (대표적으로 구성, 조작, 제어 등의 기능을 가집니다.)

Q. SQL이란? SQL의 종류는?

A. SQL(Structured Query Language)는 구조적 질의 언어로 해당 질의 언어를 통해 데이터베이스를 제어하고 관리할 수 있다.

SQL 종류로는 DDL(Data Definition Language), DML(Data ManipulationLanguage), DCL(Data Control Language)이 있다. DDL은 데이터베이스 구조를 정의, 수정, 삭제하는 언어이며 create, alter, drop 등이 있다. DML은 데이터베이스 내의 자료 검색, 삽입, 갱신, 삭제를 위한 언어로 select, delete, update, insert가 있다. DCL은 데이터에 대해 무결성을 유지, 병행 수행 제어, 보호와 관리를 위한 언어로 commit, rollback, grant, revoke가 있다.

Q. DB에서 Index를 사용하는 이유는?

A. 인덱스(Index)는 데이터를 논리적으로 정렬하여 검색과 정렬 작업의 속도를 높이기 위해 사용된다. 예를 들면, 책에서 가장 빨리 내용을 찾는 방법은 책의 뒤편의 색인을 보는 것과 같다.

기본키에 대해서는 항상 DBMS가 내부적으로 정렬된 목록을 관리하기에 특정 행을 가져올 때 빠르게 처리된다. 하지만, 다른 열의 내용을 검색하거나 정렬시에는 하나하나 대조를 해보기 때문에 시간이 오래걸린다. (이를 인덱스로 정의해두면 검색속도가 향상된다.)

단점: 인덱스를 사용하면 데이터를 가져오는 작업의 성능은 향상시킬 수 있지만 데이터 삽입, 변경 등이 일어날 때 매번 인덱스가 변경되기 때문에 성능이 떨어질 수 있다.

사용대상 : 데이터 필터링과 정렬에 사용되므로, 데이터를 특정한 순서로 자주 정렬한다면 인덱스를 사용하기에 적합

# 무결성

Q. 무결성이란?

A. 무결성이란 데이터의 정확성, 일관성, 유효성을 유지하는 것을 말한다. 데이터의 무결성을 유지하기 위해 DBMS에서는 크게 3가지 종류로 구분한다. (개체, 참조, 도메인 무결성 가장 중요)

- 개체 무결성 : 기본키로 선택된 필드는 빈 값을 허용하지 않는다. (PK는 NULL이 되면 안된다.)
- 참조 무결성 : 서로 참조 관계에 있는 두 테이블의 데이터는 항상 일관된 값을 유지한다. (FK의 값은 NULL이거나 참조하고 있는 컬럼에 있는 값이여야 한다.)
- 도메인 무결성 : 테이블에 존재하는 필드의 무결성을 보장하기 위한 것으로 올바른 데이터가 입력됬는지를 체크하는 것이다. (예를 들면 성과 같은 컬럼의 값은 남/여 만 가능)
- 고유 무결성 : 특정 속성에 대해 고유한 값을 가지도록 조건이 주어진 경우 그 속성값은 모두 고유한 값을 가진다. 같으면 안된는 것
- NULL 무결성 : 특정 속성값에 NULL이 올 수 없다는 조건이 주어진 경우 그 속성값은 NULL이 될 수 없다는 제약조건
- 키 무결성 : 한 릴레이션에는 최소한 하나의 키가 존재해야하는 제약조건

Q. 무결성을 유지하려고 하는 이유?

A. 무결성이 유지가 되어야 DB에 저장된 데이터 값과 거기에 해당하는 현실 세계의 실제값이 일치하는지 신뢰할 수 있기 때문이다.

# 트랜잭션 (동시성 제어, 데이터베이스 장애 및 회복)

Q. 트랜잭션이 뭔가요?

A. 하나의 논리적 기능을 수행하기 위한 작업의 단위로, DB의 일관된 상태를 또 다른 일관된 상태로 변환시키는 기능을 수행한다.

트랜잭션은 전체가 수행되거나 또는 전혀 수행되지 않아야한다.

Q. 트랜잭션의 성질을 말씀해보세요.

A. ACID라 불리는 총 네가지 성질을 가지고있습니다.

• Atomicity는 트랜잭션의 연산이 DB에 모두 반영되던지 전혀 반영이되지 않던지 둘중에 하나만 수행해야한다.(원자성)

• Consistency는 트랜잭션이 성공적으로 완료된 후에는 언제나 일관성 있는 DB상태로 변환되어야한다.(일관성)
  (예를 들면 A에서 B로 돈 이체를 할때 A와 B 계좌의 돈의 총합은 같아야한다.)

• Isolation은 수행중인 트랜잭션이 완전히 완료되기 전에는 다른 트랙잭션에서 수행 결과를 참조할 수 없다.(독립성)
  (따라서 트랜잭션이 동시 접근하는 데이터에대한 제어가 필요하다.)

• Durablility는 성공적으로 완료된 트랜잭션의 결과는 시스템이 고장나더라도 영구적으로 반영되어야 한다.(영속성)
  (트랜잭션이 정상적으로 완료(commit)된 경우에는 하드디스크(데이터베이스)에 확실히 기록해야하며, 부분완료된 경우 작업을 취소해야합니다.)

Q. 트랜잭션을 병행으로 처리(동시성 제어)하려고 할 때 발생할 수 있는 문제를 설명해보시오.

A.

• 갱신 내용 손실 : 동시에 하나의 데이터가 갱신될 때 하나의 갱신이 누락되는 경우

• 현황 파악 오류 : 하나의 데이터 갱신이 끝나지 않은 시점에서 다른 트랜잭션이 해당 데이터를 조회하는 경우

• 모순성 : 두 트랜잭션이 동시에 실행될 때 데이터베이스가 일관성이 없는 모순된 상태로 남는 문제

• 연쇄 복귀 : 두 트랜잭션이 하나의 레코드를 갱신할 때 하나의 트랜잭션이 롤백하면 다른 하나의 트랜잭션 마저 롤백이 되는 문제

Q. 트랜잭션을 병행으로 처리할 때 위와 같은 문제를 방지하기 위한 방법을 설명하시오.

A. 로킹 제어 기법을 사용한다.

어떤 트랜잭션이 특정 DB의 데이터를 사용할 때 DB의 일정부분을 Lock시키고 트랜잭션이 완료될때 해당부분을 Unlock시키는 방법이다. 종류는 크게 두가지가 있는데 공유 로킹은 Lock한 부분을 읽기는 가능하지만 쓰기는 불가능한 것이고 배타 로킹은 읽기,쓰기 둘다 불가능하게 한 것이다.

Q. 그렇다면 이 로킹 단위를 크게했을 때와 작게 했을 때의 차이점을 설명하시오.

A. 로킹 단위가 크면 그만큼 관리가 쉽지만 병행성이 떨어진다. 로킹단위가 작으면 관리가 어렵고 오버헤드가 증가하지만, 병행성이 올라간다.

Q. 로킹 제어가 일으킬 수 있는 문제점은 무엇인가?

A. 로킹단위에 따라 다르겠지만 트랜잭션의 직렬화 가능성이 높아진다.(병행처리하나마나 할 수도있다.) 또 데드락이 발생할 수 있다.

Q. 데드락에 대해서 설명해보세요.

T1 : write(A) read(B)

T2 : read(B) read(A)

위와 같은 트랜잭션이 있다고 하면 T1은 A를 로킹해두고 B의 로킹해제를 기다려야하고 T2는 B를 로킹해두고 A를 기다려야한다. 이 때 두 트랜잭션이 무한정 대기해야하는 상황이 발생하는데 이것을 데드락이라고 한다. (해결방법 : 이 경우 T1, T2중 하나를 ROLLBACK하고 나머지 하나를 완료시킨 후 ROLLBACK한 트랜잭션을 다시 실행시킨다.)

Q. 그럼 데드락을 안 생기게 하는 방법을 설명해보시오.

A.

서비스 별로 해결하는 방법이 매우 다른데 일반적으로는 데드락 탐지나 회피를 적용시키면 된다.

탐지인 경우 알고리즘을 통해 매번 데드락인지 아닌지 검사를 해야하므로 코스트가 크다.

회피인 경우 시분할 처리를하여 T1이 끝나면 T2가 실행시키게도 하면된다.

Facebook 처럼 write 보다 read가 월등히 많은 경우 Read용 DB를 slave로 두고 로드를 모두 몰아주고 write를 Master로 보내고 DB를 동기화 할 수도 있다.

또 다른 해결기법으론 로킹 제어기법이 아닌 타임스탬프 기법을 사용한다. 트랜잭션의 식별자로 타임스탬프를 지정하며 순서를 미리 선택한다. 트랜잭션이 대기하지 않고 바로 실행은 하나 높은 확률로 ROLLBACK이 일어나며 연쇄 복귀를 초래할 수 있다.

Q. COMMIT과 ROLLBACK에 대해 설명해보세요.

A. DML을 수행하고 난 뒤 COMMIT은 해당 트랜잭션으로 반영된 DB 변경사항을 저장 하는 것이고 ROLLBACK은 해당 트랜잭션으로 반영된 DB 변경사항을 취소 하는 것이다.

Q. 데이터베이스 장애의 유형

A. 

• 트랜잭션 장애: 트랜잭션의 실행 시 논리적인 오류로 발생할 수 있는 에러 상황

• 시스템 장애: H/W 시스템 자체에서 발생할 수 있는 에러 상황

• 미디어 장애: 디스크 자체의 손상으로 발생할 수 있는 에러 상황

Q. 데이터베이스 회복 기법에 대해 설명하시오.

A.

• 로그기반 회복기법

• 지연 갱신 회복 기법

  • write 연산 지연, 로그에 DB변경 내역 저장

  • 트랜잭션 완료시 로그를 보고 write 연산 수행

  • 트랜잭션 완료시 장애 발생 : REDO만 실행

  • 트랜잭션 미완료시 장애 발생 : 로그 무시

• 즉시 갱신 회복 기법

  • 즉시 DB 변경, 로그에 기록

  • 장애 발생 시 로그에 기반하여 UNDO 실행

• 체크포인트 회복기법

• 체크 포인트를 지정하여 장애발생시 체크포인트까지 UNDO 실행 후 다시 REDO 실행

• 그림자 페이징 회복 기법

• 하드디스크에 그림자 페이지를 만들고 저장해두고 장애발생시 하드디스크에 있는 페이지로 주메모리 페이지 변경

• 장애 미발생시 그림자 페이지 테이블은 삭제

* 트랜잭션 설명 및 예제가 가장 잘 나와있다고 생각되는 사이트

https://mangkyu.tistory.com/30?category=761304

# 정규화

Q. DB Normalization(정규화)란?

A. 데이터베이스 정규화란 데이터의 중복을 줄이고 무결성을 향상 시키는 등 여러 목적을 달성하기 위해 관계형 데이터베이스를 정규화된 형태로 재디자인하는 것을 말한다.

Q. DB Normalization(정규화)의 목적은?

A.

• 불필요한 데이터를 제거, 데이터의 중복을 최소화 하기 위해서

• 데이터베이스 구조 확장 시 재디자인을 최소화

• 다양한 관점에서의 query를 지원하기 위해서

• 무결성 제약조건의 시행을 간단하게 하기 위해서

• 각종 이상현상을 방지하기 위해서, 테이블의 구성을 논리적이고 직관적으로 한다.

Q. 이상현상 이란?

A.
좋은 관계형 데이터베이스를 설계하는 목적 중 하나가 정보의 이상 현상(Anomaly) 이 생기지 않도록 고려해 설계하는 것이다.
이상 현상은 갱신 이상(Modification Anomaly), 삽입 이상(Insertion Anomaly), 삭제 이상(Deletion Anomaly) 으로 구성된다.
각각을 간략하게 설명하면 다음과 같다.

• 갱신 이상(Modification Anomaly): 반복된 데이터 중에 일부를 갱신 할 시 데이터의 불일치가 발생한다.

• 삽입 이상(Insertion Anomaly): 불필요한 정보를 함께 저장하지 않고서는 어떤 정보를 저장하는 것이 불가능하다.

• 삭제 이상(Deletion Anomaly): 필요한 정보를 함께 삭제하지 않고서는 어떤 정보를 삭제하는 것이 불가능하다.

Q. 정규화 과정?

A. 정규화는 1정규화 ~ 6정규화 까지 있지만, 실무에서는 대체로 1~3 정규화까지의 과정을 거친다.

• 제 1정규화 : 각 컬럼들은 값이 원자값을 가지게 바꾼다.

• 제 2정규화 : 테이블의 모든 컬럼에서 부분 함수적 종속을 제거하는 것

• 제 3정규화 : 기본키를 제외한 속성들 간의 이행적 함수 종속을 없애는 것

제 1정규화(First Normal Form, 1NF)

테이블(Relation)이 제 1정규형을 만족했다는 것은 아래 세 가지 조건를 만족했다는 것을 의미한다.

1. 어떤 Relation에 속한 모든 Domain이 원자값(atomic value)만으로 되어 있다.

2. 모든 attribute에 반복되는 그룹(repeating group)이 나타나지 않는다.

3. 기본 키를 사용하여 관련 데이터의 각 집합을 고유하게 식별할 수 있어야 한다.

제 2정규화(Second Normal Form, 2NF)

제 2정규화를 수행 했을 경우 테이블의 모든 컬럼이 완전 함수적 종속을 만족한다.(부분 함수적 종속을 모두 제거되었다.) 이를 이해하기 위해서는 부분 함수적 종속과 완전 함수적 종속이라는 용어를 알아야 한다.

• 함수적 종속: X의 값에 따라 Y값이 결정될 때 X -> Y로 표현하는데, 이를 Y는 X에 대해 함수적 종속 이라고 한다. 예를 들어 학번을 알면 이름을 알 수 있는데, 이 경우엔 학번이 X가 되고 이름이 Y가 된다. X를 결정자이라고 하고, Y는 종속자라고 한다. 다른 말로 X가 바뀌었을 경우 Y가 바뀌어야만 한다는 것을 의미한다.

• 함수적 종속에서 X의 값이 여러 요소일 경우, 즉, {X1, X2} -> Y일 경우, X1와 X2가 Y의 값을 결정할 때 이를 완전 함수적 종속 이라고 하고, X1, X2 중 하나만 Y의 값을 결정할 때 이를 부분 함수적 종속 이라고 한다.

제 3정규화(Third Normal Form, 3NF)

테이블(Relation)이 제 3정규형을 만족한다는 것은 아래 두 가지 조건을 만족하는 것을 의미한다.

1. Relation이 제 2정규화 되었다.(The relation is in second normal form)

2. 기본 키(primary key)가 아닌 속성(Attribute)들은 기본 키에만 의존해야 한다.

Q. 역정규화를 하는 이유는 무엇인가요?

A. 정규화를 진행할 수록 하나의 테이블을 여러 테이블로 나누게 되는데, 만약 데이터 호출 시 여러 테이블을 불러서 JOIN을 해줘야한다면 이 비용도 만만치 않기 때문에 역정규화를 한다.

* DB 정규화 개념 설명 및 예제가 가장 잘 나와있다고 생각되는 사이트

https://wkdtjsgur100.github.io/database-normalization/

# 관계형 데이터베이스와 비 관계형 데이터베이스

Q. 관계형 데이터베이스와 비 관계형 데이터베이스 차이점에 대해 설명해보세요.

A. 관계형 데이터베이스란 테이블(table)로 이루어져 있으며, 이 테이블은 키(key)와 값(value)의 관계를 나타낸다.이처럼 데이터의 종속성을 관계(relationship)로 표현하는 것이 관계형 데이터베이스의 특징이다.

비 관계형 데이터베이스는 행과 열로 이루어진 테이블 형식 스키마를 사용하지 않는 데이터베이스이다. 저장되는 데이터 형식의 특정 요구 사항에 맞게 최적화된 저장소 모델을 사용하는 것이 특징이다. 흔히들 NoSQL(not only SQL)이라고 하며 데이터를 저장할 때 SQL문이 아닌 다른 프로그래밍 언어 및 구문을 사용한다.

Q. RDBMS과 비교하였을 때 NoSQL의 장점을 설명해보세요.

A. 가장 큰 장점이라면 JOIN 처리가 없기 때문에 스케일 아웃을 통한 노드 확장 용이하다는 점이다. 뿐만아니라 가변적인 데이터구조로 데이터를 저장할 수 있어서 훨씬 더 유연성이 높다. 단점으로는 다양하고 복잡한 쿼리가 불가능하고 일관성을 항상 보장할 수 없는 것을 꼽을 수 있다.

속도적인 측면에서는 대표적인 RDBMS인 MySQL이나 ORACLE이 워낙 최적화가 잘 되어있기도하고 주어진 상황에 따라 아주 케이스바이케이스라 뭐가 더 좋다라고는 하기 어렵다.

Q. NoSQL이란?

A.

• NoSQL 데이터베이스는 관계형 데이터베이스(RDB)보다 덜 제한적인 일관성 모델을 이용하는 데이터의 저장 및 검색을 위한 매커니즘을 제공한다.
  

• 단순 검색 및 추가 작업을 위한 매우 최적화된 키-값 저장 공간을 사용한다.

• 빅데이터 시대에 따라 많은 양의 데이터를 효율적으로 처리하기 위해 등장하였다. (분산처리, 빠른쓰기 및 데이터의 안정성)

• 분산형 구조를 통해 여러 대의 서버에 분산해 저장하고, 분산시에는 데이터를 상호 복제에 특정 서버에 장애가 발생했을 때에도 데이터 유실이나 서비스 중지가 없는 형태의 구조를 갖고 있다.

Q. 어떤상황에서 NoSQL을 쓰는 것이 더 적합한가?

A. 비정형 데이터를 저장해야할 때 가장 적합하다. 검색기능이 있을 때도 좋다고들하는데 의견이 분분하다. 케바케라는 말이 적절할 것 같다.

* 참고자료

https://kadamon.tistory.com/21

https://91ms.tistory.com/2?category=711086

https://mangkyu.tistory.com/30?category=761304

https://www.acmicpc.net/problem/14890

문제

Simulation 문제이다. Queue를 사용하여 구현하다가 올라가는 경사에서 막혀서 다른사람 풀이를 참고하였다.

해결 방안

주어진 조건에 맞도록 구현하는 Simulation 문제이다.

1. 각 행과 열마다 지나길 수 있는 길인지 체크해서 갯수를 세준다.
2. 해당 행과 열을 1차원 배열로 만들어서 체크하기 쉽게 만든다. (checkPath()함수)
조건이 맞지 않는 경우 false를 리턴해준다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// 경사로
public class Main {

	static int N; // 지도 크기 NxN (2~100)
	static int L; // 경사로 길이 (1~N)
	static int[][] map; // 지도
	static boolean[][] visited; // 경사로 놓은지 확인
	static int pathCnt;
	
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str;
		str = br.readLine();
		N = Integer.parseInt(str.split(" ")[0]);
		L = Integer.parseInt(str.split(" ")[1]);
		pathCnt = 0;
		
		map = new int[N][N];
		visited = new boolean[N][N];
		
		StringTokenizer st;
		for(int i=0; i<N; i++) {
			str = br.readLine();
			st = new StringTokenizer(str, " ");
			
			for(int j=0; j<N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		// ===== 입력 끝 =====
		
		// 가능한 길인지 아닌지 체크
		for(int i=0; i<N; i++) {
			if(checkPath(i, 0, true)) // 행
				pathCnt++;
			
			if(checkPath(0, i, false)) // 열
				pathCnt++;
		}
		
		System.out.println(pathCnt);
	}

	// flag: true 행 검사
	// flag: false 열 검사
	static boolean checkPath(int x, int y, boolean flag) {
		
		int[] height = new int[N];
		boolean[] visited = new boolean[N];
		
		for(int i=0; i<N; i++) {
			if(flag)
				height[i] = map[x][i];
			else
				height[i] = map[i][y];
		}
		
		for(int i=0; i<N-1; i++) {
			// 높이가 같을 때
			if(height[i] == height[i+1]) {
				continue;
			}
			// 내려가는 경사
			else if(height[i]-height[i+1] == 1) {
				
				for(int j=i+1; j<=i+L; j++) {
					// 범위 넘어가거나 칸의 높이가 다르거나 이미 경사로가 있는 경우
					if(j>=N || height[i+1]!=height[j] || visited[j]) return false;
					visited[j] = true;
				}
			}
			// 올라가는 경사
			else if(height[i]-height[i+1] == -1) {
				
				for(int j=i; j>i-L; j--) {
					// 범위 넘어가거나 칸의 높이가 다르거나 이미 경사로가 있는 경우
					if(j<0 || height[i]!=height[j] || visited[j]) return false;
					visited[j] = true;
				}
			}
			// 높이가 2칸 이상 차이 날때 (길x)
			else {
				return false;
			}
		}
		
		return true;
	}
	
}

https://www.acmicpc.net/problem/14889

문제

DFS + 구현 으로 문제를 해결하였다.

해결 방안

전체적으로 보면 1. 스타트 팀과 링크 팀 반으로 사람을 나누는 모든 경우의 수와 2. 나눠진 팀의 점수 차이를 구하는 두가지를 구현해야한다.

1. 스타트 팀과 링크 팀 반으로 사람을 나누는 모든 경우의 수는 DFS 탐색을 이용하여 구현하였다.
기저사례가 N/2 일 때까지 DFS 탐색을 하며 N/2 개의 visited를 true로 만들어준다.
caculateDifference()함수에서 visited가 true인 경우는 start 팀에 false인 경우 link 팀에 넣어주었다.

2. 나눠진 팀을 가지고 각 팀의 점수를 getTeamAbility() 함수를 이용하여 구해주었다.
그리고 각각 구해진 팀의 점수를 빼서 절댓값을 구해주었다.

그리고 마지막으로 min인 경우를 찾았다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// 스타트와 링크
// 능력치 차이의 최소화
public class Main {

	static int N; // 사람수(4~20, 짝수)
	static int[][] S; // 능력치
	static boolean[] visited;
	
	static int minDifference = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		
		S = new int[N+1][N+1];
		visited = new boolean[N+1];
		String str;
		StringTokenizer st;
		for(int i=1; i<N+1; i++) {
			str = br.readLine();
			st = new StringTokenizer(str, " ");
			for(int j=1; j<N+1; j++) {
				S[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		// ========= 입력 끝 ==========
		
		dfs(0, 0);
		
		System.out.println(minDifference);
	}
	
	static void dfs(int v, int len) {
		if(len == N/2) {
			// 스타트팀, 링크팀 능력치 차이 구하기
			int difference = caculateDifference();
			// 능력치 차이 최솟값 구하기
			minDifference = Math.min(minDifference, difference);
		}
		else {
			for(int i=v+1; i<N+1; i++) {
				if(!visited[i]) {
					visited[i] = true;
					dfs(i, len+1);
					visited[i] = false;
				}
			}
		}
	}
	
	// 팀 점수 차이 구하기
	static int caculateDifference() {
		
		int[] start = new int[N/2 + 1];
		int[] link = new int[N/2 + 1];
		
		int si = 1; int li = 1;
		for(int i=1; i<N+1; i++) {
			if(visited[i]) start[si++] = i;
			else link[li++] = i;
		}
		
		// 각 팀 점수 구하기
		int startAbility = getTeamAbility(start);
		int linkAbility = getTeamAbility(link);
		
		int difference = Math.abs(startAbility-linkAbility);
		
		return difference;
	}

	// 각팀 점수 구하기
	static int getTeamAbility(int[] team) {
		
		int teamAbility = 0;
		
		for(int i=1; i<team.length; i++) {
			for(int j=i+1; j<team.length; j++) {
				teamAbility += S[team[i]][team[j]];
				teamAbility += S[team[j]][team[i]];
			}
		}
		
		return teamAbility;
	}
}

https://www.acmicpc.net/problem/14888

문제

브루트포스 문제 인데 DFS 탐색을 이용하여 문제를 해결하였다.

해결 방안

숫자의 위치는 고정이고 연산자 우선순위도 무시하므로 숫자간 모든 경우의 연산자를 넣어 각각의 sum값들을 비교하여 최대 최소값을 구하는 문제이다.

덧셈, 뺄셈, 곱셈, 나눗셈의 갯수의 합이 N-1 개이므로 각각의 갯수들을 고려하여 DFS 탐색을 해주면된다.
그리고 기저사례를 depth가 N-1인 경우로 하며 계산된 sum값의 max, min 값을 구해준다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// 연산자 끼워넣기
// 연산자 우선 순위 무시하고 앞에서부터 진행
// 나눗셈은 몫만 취함(음수 이면 양수로 바꾼뒤 몫을 취하고 그 몫을 음수로 바꿈)
// 식의 결과가 최대인 값과 최소인 값을 구함
public class Main {

	static int N; // 수의 갯수(2~11)
	static int[] a; // a1~an
	
	static int[] operatorCnts; // 덧셈, 뺄셈, 곱셈, 나눗셈
	
	// (-10억~10억)
	static int max = Integer.MIN_VALUE;
	static int min = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		a = new int[N+1];
		
		String str;
		str = br.readLine();
		StringTokenizer st = new StringTokenizer(str, " ");
		for(int i=1; i<N+1; i++) {
			a[i] = Integer.parseInt(st.nextToken());
		}
		
		str = br.readLine();
		operatorCnts = new int[4];
		for(int i=0; i<4; i++) {
			operatorCnts[i] = Integer.parseInt(str.split(" ")[i]);
		}
		
		// =========== 입력 끝 ============
		dfs(0, a[1]);
		
		System.out.println(max);
		System.out.println(min);
	}
	
	static void dfs(int depth, int sum) {

		if(depth >= N-1) {
			max = Math.max(max, sum);
			min = Math.min(min, sum);
			return;
		}
		else {
			// 덧셈
			if(operatorCnts[0] > 0) {
				operatorCnts[0]--;
				dfs(depth+1, sum+a[depth+2]);
				operatorCnts[0]++;
			}
			// 뺄셈
			if(operatorCnts[1] > 0) {
				operatorCnts[1]--;
				dfs(depth+1, sum-a[depth+2]);
				operatorCnts[1]++;
			}
			// 곱셈
			if(operatorCnts[2] > 0) {
				operatorCnts[2]--;
				dfs(depth+1, sum*a[depth+2]);
				operatorCnts[2]++;
			}
			// 나눗셈
			if(operatorCnts[3] > 0) {
				operatorCnts[3]--;
				if(sum < 0) {
					sum *= -1;
					dfs(depth+1, (sum/a[depth+2]) * -1);
					sum *= -1;
				}
				else {
					dfs(depth+1, sum/a[depth+2]);
				}
				operatorCnts[3]++;
			}
		}
	}
}

https://www.acmicpc.net/problem/14503

문제

DFS 문제라고 생각하고 풀었는데 stackoverflow가 자꾸 떠서 다른 사람 풀이 참고하여 풀었다. (알고보니 구현 문제)

해결 방안

문제에서의 로봇 청소기 작동 방법에 맞춰서 구현해주면 된다.

while 두개를 이용하여 구현하였으며 코드를 보면 1, 2 조건에 따른 코드를 구현하였다. 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// 로봇 청소기
// 청소하는 영역의 갯수를 구하는 프로그램
// 청소기는 바라보는 방향이 있음
// (r,c) r: 북쪽으로부터 떨어진 칸의 갯수, c: 서쪽으로부터 떨어진 칸의 갯수
// 현재 방향을 기준으로 왼쪽 방향부터 차례대로 탐색을 진행함
public class Main {

	static int N; // 세로 (3~50)
	static int M; // 가로 (3~50)
	static int[][] map;
	
	static int r; // 로봇청소기 좌표(r,c)
	static int c; 
	static int d; // 바라보는 방향 (0:북, 1:동, 2:남, 3:서)
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	static int cleanSite = 0;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str;

		str = br.readLine();
		N = Integer.parseInt(str.split(" ")[0]);
		M = Integer.parseInt(str.split(" ")[1]);
		map = new int[N][M];
		
		str = br.readLine();
		r = Integer.parseInt(str.split(" ")[0]);
		c = Integer.parseInt(str.split(" ")[1]);
		d = Integer.parseInt(str.split(" ")[2]);
		
		StringTokenizer st;
		for(int i=0; i<N; i++) {
			str = br.readLine();
			st = new StringTokenizer(str, " ");
			for(int j=0; j<M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		// ========= 입력 끝 ==========
		
		cleaning();
		System.out.println(cleanSite);
	}
	
	static void cleaning() {
		
		int dirCnt = 0; 
		int nx,ny;
		boolean flag = true;
		
		while(flag) {
			// 1. 현재 위치 청소
			if(map[r][c] == 0) {
				map[r][c] = 2;
				cleanSite++;
			}
			
			// 2. 탐색
			while(true) {
				if(dirCnt == 4) {
					nx = r - dx[d];
					ny = c - dy[d];
					
					// d. 뒷칸이 벽인 경우 작동 멈춤
					if(map[nx][ny] == 1) {
						flag = false;
						break;
					}
					// c. 후진
					else if(map[nx][ny] == 2) {
						r = nx;
						c = ny;
						dirCnt = 0;
					}
				}
				
				d--;
				if(d == -1)
					d = 3;
				nx = r + dx[d];
				ny = c + dy[d];
				
				// a. 한칸 전진
				if(map[nx][ny] == 0) {
					dirCnt = 0;
					r = nx;
					c = ny;
					break;
				}
				// b. 2번으로 돌아감
				else {
					dirCnt++;
					continue;
				}
				
			}
		}
	}

}

https://www.acmicpc.net/problem/14502

문제

벽 3개 세우는 경우를 완전 탐색하고 벽이 3개 세워진 경우에 바이러스를 퍼트려서 최대 안전 구역 크기를 구해주는 문제이다.

생각보다 쉽게 풀려서 놀랐다. DFS + BFS 문제

해결 방안

1. 메인에서 지도값 입력받을 때 바이러스의 좌표를 저장할 수 있는 자료구조(여기서는 ArrayList 사용함)를 사용해준다. (나중에 BFS 탐색에서 Queue에 넣어줄 값)

2. DFS 탐색을 이용하여 벽이 3개가 추가된 경우를 완전탐색한다.(벽이 3개가 추가된 지도가 만들어진다.)

3. DFS 탐색의 기저 사례에 벽이 3개가 추가된 경우로 설정해주고 해당 경우마다 바이러스를 BFS 탐색을 이용하여 퍼트려준다.
3.1. 이 때, 해당 지도를 copy한 지도를 만들어준다. (기존 지도는 DFS를 통해 계속 사용해야하므로)
3.2. copy된 지도에 BFS 탐색을 이용하여 바이러스를 퍼트려준다.
3.3. 바이러스가 퍼트려진 copy된 지도의 안전 구역 크기를 구해준다.
3.4. 기존에 누적된 max 안전 구역 크기와 비교하여 새로운 max 안전 크기 구역을 구해준다.

4. 바이러스가 퍼지는 부분을 BFS를 이용하여 구해주었다. (3.2 부분)
4.1. 3.2 부분에서 바이러스를 퍼트릴때 1.에서 저장한 바이러스 좌표를 Queue에 넣어주고 visited를 true로 만들어준다.
4.2. 바이러스 좌표의 상하좌우 부분의 경우 범위가 지도 범위를 넘어가는지 확인해주고 방문 안했으며 빈 칸인 경우 바이러스를 확진 시켜준다.
4.3. BFS 탐색이 끝나면 해당 map을 반환해준다.
4.4. 끝나면 3.2 과정이 끝나 3.3 과정이 시작한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

// 연구소
// 바이러스 확산을 막기 위해서 연구소에 벽을 세우려고함
// NxM 직사각형의 연구소
// 바이러스는 인접한 빈칸(상하좌우)으로 모두 퍼져나감
// 새로 세울 수 있는 벽의 갯수는 3개
// 0:빈칸  1:벽  2:바이러스
// 안전 영역(바이러스, 벽 제외한 부분) 크기의 최댓값을 구하는 프로그램 작성
public class Main {

	static int N; // 세로 (3~8)
	static int M; // 가로 (3~8)
	static int[][] maps; // 지도
	static boolean[][] visited;
	
	// 바이러스 움직임 (상하좌우)
	static int[] dx = {-1, 1, 0, 0}; // 세로
	static int[] dy = {0, 0, -1, 1}; // 가로
	
	static List<int[]> virusLocation = new ArrayList<>(); // 바이러스 좌표
	
	static int max_safe = 0;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String str;
		str = br.readLine();
		N = Integer.parseInt(str.split(" ")[0]);
		M = Integer.parseInt(str.split(" ")[1]);
		
		maps = new int[N][M];
		visited = new boolean[N][M];
		
		StringTokenizer st;
		for(int i=0; i<N; i++) {
			str = br.readLine();
			st = new StringTokenizer(str, " ");
			for(int j=0; j<M; j++) {
				maps[i][j] = Integer.parseInt(st.nextToken());
				
				if(maps[i][j] == 2) {
					virusLocation.add(new int[] {i, j});
				}
			}
		}
		//====== 입력 끝 ========
		
		// 완전 탐색으로 3개의 벽 세우고 바이러스 퍼졌을 때 안전지역이 최대값을 찾는 프로그램
		dfs(0);
		
		
		System.out.println(max_safe);

	}
	
	public static int[][] copyMap() {
		int[][] copy_maps = new int[N][M];
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				copy_maps[i][j] = maps[i][j];
			}
		}
		
		return copy_maps;
	}
	
	//바이러스 퍼지는 것을 bfs로 구현
	public static int[][] bfs(int[][] copy_maps, boolean[][] visited) {
		
		Queue<int[]> q = new LinkedList<>();
		
		// 처음 바이러스좌표를 Queue에 넣어줌
		int[] loc = new int[2];
		for(int i=0; i<virusLocation.size(); i++) {
			loc = virusLocation.get(i);
			q.offer(new int[] {loc[0], loc[1]});
			visited[loc[0]][loc[1]] = true;
		}
		
		// 현재 바이러스 위치
		int cx, cy;
		int nx, ny;
		int[] tempLoc;
		while(!q.isEmpty()) {
			tempLoc = q.poll();
			cx = tempLoc[0];
			cy = tempLoc[1];
			
			// 상하좌우 바이러스 퍼트림
			for(int i=0; i<4; i++) {
				nx = dx[i] + cx;
				ny = dy[i] + cy;

				// 범위 넘어가는지 확인
				if(nx<0 || nx>=N || ny<0|| ny>=M) continue;
				
				// 방문 안했고 빈 칸 인지 확인해서 바이러스확진
				if(!visited[nx][ny]) {
					if(copy_maps[nx][ny] == 0) {
						visited[nx][ny] = true;
						copy_maps[nx][ny] = 2;
						q.offer(new int[] {nx, ny});
					}
				}
			}
		}
		
		return copy_maps;
	}
	
	public static void dfs(int cnt) {
		// 벽의 갯수가 3개가 됬을 때
		if(cnt == 3) {
			
			int[][] copy_maps = new int[N][M];
			
			// copy map
			copy_maps = copyMap();
			
			// 바이러스 다 퍼트리고
			boolean[][] visited = new boolean[N][M];
			copy_maps = bfs(copy_maps, visited);
			
			int safe = 0;
			// 안전 지역 갯수 구하고(빈 칸의 갯수)
			for(int i=0; i<N; i++) {
				for(int j=0; j<M; j++) {
					if(copy_maps[i][j] == 0)
						safe++;
				}
			}
			
			// 안전지역 최댓값 구함
			max_safe = Math.max(max_safe, safe);
		}
		else {
			
			// 벽의 갯수 dfs 탐색으로 늘려줌
			for(int i=0; i<maps.length; i++) {
				for(int j=0; j<maps[i].length; j++) {
					// 벽이나 바이러스일 경우 
					if(maps[i][j] == 1 || maps[i][j] == 2) continue;
					// 빈 칸 인 경우
					else {
						// 방문하지 않은 경우
						if(!visited[i][j]) {
							// 빈칸에 벽을 세워줌
							visited[i][j] = true;
							maps[i][j] = 1;
							dfs(cnt+1);
							maps[i][j] = 0;
							visited[i][j] = false;
						}
					}
				}
			}
		}
	}

}

https://www.acmicpc.net/problem/14501

문제

나는 DFS로 풀었다. 풀고나서 다른 사람들의 풀이를 보니 DP를 이용하여 푼 것을 확인하였다.
다음 복습에는 꼭 DP로 풀어봐야겠다.

해결 방안

1부터 N일 까지 상담이 가능하며 하루에 1개씩만 상담이 가능하다. 이 부분에서 걸리는 시간 비교를 통한 DFS를 이용하면 구할 수 있을 것이라고 생각하였다. 

1. DFS 탐색 시작 부분에서 반복문을 이용해서 1~N일까지 DFS 탐색을 하는데 i + T[i] 가 N+1이 넘어가는 순간은 제외하고 진행하였다. (문제에서 퇴직날까지 상담이 가능하다고 하였므르로)

2. 그리고 DFS 탐색 부분에서 기저 사례는 dfs 함수에서 보내준 index 값과 T[index]의 합이 N+1이 넘어가는 순간이다.
그 순간 최대값을 계속 갱신해준다.

3. 그외 DFS 탐색 부분에서는 dfs 함수에서 보내준 index 값에 T[index] 더한 수 부터 다시 DFS 탐색을 해준다.
이 때 기저사례로 빠질 수 있는 조건을 만들어준다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

// 퇴사
// N+1일 째 되는 날 퇴사
// 남은 N일 동안 최대한 많은 상담
// 하루에 상담 1개만 가능
public class Main {
	
	static int N; // 상담 가능 일수
	static int[] T; // 상담을 완료하는데 걸리는 시간
	static int[] P; // 상담을 했을 때 받을 수 있는 금액
	
	static int result = 0; // 최대 이익

	public static void main(String[] args) throws Exception, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		T = new int[N+1];
		P = new int[N+1];
		
		String str;
		for(int i=1; i<N+1; i++) {
			str = br.readLine();
			T[i] = Integer.parseInt(str.split(" ")[0]);
			P[i] = Integer.parseInt(str.split(" ")[1]);
		}
		
		int sum = 0;
		for(int i=1; i<N+1; i++) {
			sum = 0;
			if(i+T[i]<=N+1) {
				sum = P[i];
				dfs(i, sum);
			}
		}
		
		System.out.println(result);

	}
	
	public static void dfs(int index, int sum) {
		if(index + T[index] >= N+1) {
			result = Math.max(result, sum);
		}
		else {
			for(int i = index+T[index]; i<N+1; i++) {
				if(i+T[i]<=N+1) {
					sum += P[i];
					dfs(i, sum);
					sum -= P[i];
				}
				else {
					dfs(i, sum);
				}
			}
		}
	}

}

https://www.acmicpc.net/problem/12100

문제

쉬운듯 안쉬운듯... 처음 풀기엔 어려웠다... 다른사람의 풀이를 많이 참고함

해결 방안

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록값을 구하는 문제로써 5의 깊이를 가지는 DFS를 이용하여 문제를 풀어야겠다고 생각하였다.

1-1. 일단 기저사례에 도달하였을 때 해당 board의 가장 큰 값을 구하고
그 값과 지금까지 깊이가 5가 됬을 때 board의 가장 큰 값의 max 값을 비교한다.

1-2. DFS 탐색 부분은
상하좌우 모든 방면으로 이동시켜준다. 이때 board를 가지고 값들을 이동(merge()시켜주고 전의 값들을 copyBoard에 저장해둬서 반환 했을때 다시 board에 copyBoard 값을 저장해준다.

2. merge() 하는 부분은 Queue 자료구조를 이용하였다. 세로, 가로를 구분하여 한 줄 씩 해결하였다.
Queue 에 한 줄의 값중 0이 아닌 숫자들을 다 넣어준 다음
Queue에 있는 값들을 꺼내가면서 조건 3가지에 따라 board에 Queue에서 빼준 값을 다시 넣어주었다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// 2048 (Easy)
// 최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력
public class Main {

	static int n; //(1~20)
	static int[][] board; //게임판
	static int result; // 가장 큰 블록
	
	public static void main(String[] args) throws IOException {
		
		// 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		
		board = new int[n][n];
		
		String str;
		StringTokenizer st;
		for(int i=0; i<n; i++) {
			str = br.readLine();
			st = new StringTokenizer(str, " ");
			
			for(int j=0; j<n; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		result = 0;
		dfs(0);
		
		System.out.println(result);

	}
	
	static void dfs(int depth) {
		if(depth>=5) {
			// 게임 판 가장 큰 블록 찾기
			int max = getMaxValue();
			// 최대값 찾아서 비교
			result = Math.max(result, max);
			return;
		}
		else {
			// 복사
			int[][] copyBoard = new int[n][n];
			copyBoard(copyBoard, board);
			
			for(int i=1; i<=4; i++) {
				merge(i);
				dfs(depth+1);
				copyBoard(board, copyBoard);
				
			}
		}
	}
	
	static void copyBoard(int[][] a, int[][] b) {
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				a[i][j] = b[i][j];
			}
		}
	}
	
	// 게임판에서 가장 큰 값 찾기
	static int getMaxValue() {
		int max = 0;
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				max = Math.max(max, board[i][j]);
			}
		}
		
		return max;
	}
	
	// 
	static void merge(int dir) {
		
		Queue<Integer> q = new LinkedList<>();
		
		switch(dir) {
			// 상
			case 1:
				for(int i=0; i<n; i++) {
					// 세로 한줄 씩 해결
					for(int j=0; j<n; j++) {
						// 0이 아닌 경우 q에 넣어주고
						if(board[j][i]!=0) q.offer(board[j][i]);
						board[j][i] = 0;
					}
					
					// q에는 세로줄이 다 넣어진 상태
					// q에서 꺼내면서 합쳐줄껀 합쳐주고 board에 저장
					int index = 0;
					int popData;
					while(!q.isEmpty()) {
						popData = q.poll();
						
						// 0일 때 (아무것도 안들어간 상태)
						if(board[index][i] == 0) {
							board[index][i] = popData;
						}
						// 같을 때
						else if(board[index][i] == popData) {
							board[index][i] = popData*2;
							index++;
						}
						// 들어가있을 때 (다음거에 데이터 넣어줌)
						else {
							index++;
							board[index][i] = popData;
						}
					}
				}
				break;
				
			// 하
			case 2:
				for(int i=0; i<n; i++) {
					// 세로 한줄 씩 해결(밑줄부터)
					for(int j=n-1; j>=0; j--) {
						// 0이 아닌 경우 q에 넣어주고
						if(board[j][i]!=0) q.offer(board[j][i]);
						board[j][i] = 0;
					}
					
					// q에는 세로줄이 다 넣어진 상태
					// q에서 꺼내면서 합쳐줄껀 합쳐주고 board에 저장
					int index = n-1;
					int popData;
					while(!q.isEmpty()) {
						popData = q.poll();
						
						// 0일 때 (아무것도 안들어간 상태)
						if(board[index][i] == 0) {
							board[index][i] = popData;
						}
						// 같을 때
						else if(board[index][i] == popData) {
							board[index][i] = popData*2;
							index--;
						}
						// 들어가있을 때 (다음거에 데이터 넣어줌)
						else {
							index--;
							board[index][i] = popData;
						}
					}
				}
				break;
				
			// 좌
			case 3:
				for(int i=0; i<n; i++) {
					// 가로 한줄 씩 해결
					for(int j=n-1; j>=0; j--) {
						// 0이 아닌 경우 q에 넣어주고
						if(board[i][j]!=0) q.offer(board[i][j]);
						board[i][j] = 0;
					}
					
					// q에는 가로줄이 다 넣어진 상태
					// q에서 꺼내면서 합쳐줄껀 합쳐주고 board에 저장
					int index = n-1;
					int popData;
					while(!q.isEmpty()) {
						popData = q.poll();
						
						// 0일 때 (아무것도 안들어간 상태)
						if(board[i][index] == 0) {
							board[i][index] = popData;
						}
						// 같을 때
						else if(board[i][index] == popData) {
							board[i][index] = popData*2;
							index--;
						}
						// 들어가있을 때 (다음거에 데이터 넣어줌)
						else {
							index--;
							board[i][index] = popData;
						}
					}
				}
				break;
				
			// 우
			case 4:
				for(int i=0; i<n; i++) {
					// 가로 한줄 씩 해결
					for(int j=0; j<n; j++) {
						// 0이 아닌 경우 q에 넣어주고
						if(board[i][j]!=0) q.offer(board[i][j]);
						board[i][j] = 0;
					}
					
					// q에는 가로줄이 다 넣어진 상태
					// q에서 꺼내면서 합쳐줄껀 합쳐주고 board에 저장
					int index = 0;
					int popData;
					while(!q.isEmpty()) {
						popData = q.poll();
						
						// 0일 때 (아무것도 안들어간 상태)
						if(board[i][index] == 0) {
							board[i][index] = popData;
						}
						// 같을 때
						else if(board[i][index] == popData) {
							board[i][index] = popData*2;
							index++;
						}
						// 들어가있을 때 (다음거에 데이터 넣어줌)
						else {
							index++;
							board[i][index] = popData;
						}
					}
				}
				break;
		
		}
	}

}