분류 전체보기

[백준, c++] 9663 N-Queen

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제입니다. Queen들이 서로 공격하는 조건은 다음과 같습니다. 같은 행에 위치 같은 열에 위치 대각선에 위치 같은 행에 위치하면 공격한다는 조건을 고려하여 볼 때, 한 행에 퀸은 한개만 존재한다는 것을 알 수 있습니다. 따라서 이차원배열이 아니라 일차원배열로 퀸의 위치를 나타내어도 상관이 없습니다. 예를 들어, row[..

[Algorithm] 백트래킹(Backtracking)

백트래킹이란 ? 백트래킹은 모든 경우의 수를 고려하는 알고리즘을 의미합니다. 트리 형태의 상태공간이 있을 때, DFS와 같은 완전탐색 알고리즘을 사용하여 모든 지점을 탐색하게 됩니다. DFS는 현재 지점에서 방문할 곳이 있으면 재귀를 호출하여 계속해서 이동하는 특징이 있습니다. 하지만, DFS는 모든 곳을 방문하기 때문에 비효율적인 측면이 있습니다. 따라서 목표지점이 될 가능성이 있는지를 검사한 후 그 지점들만 방문하는 것을 백트래킹 알고리즘이라 합니다. 즉, 백트래킹은 DFS를 사용하여 만약 조건에 맞지 않으면 그 즉시 중단하고 이전으로 돌아가여 다시 확인하는 것을 반복하면서 원하는 조건을 효율적으로 찾는 알고리즘 입니다. 백트래킹과 DFS의 차이점? 백트래킹과 DFS의 차이점을 많이 헷갈려하시는데, ..

리눅스 커맨드라인 완벽 입문서 <챕터 1, 2 > 요약정리

쉘이란, 키보드로 입력한 명령어를 운영체제가 전달하여 이 명령어를 실행하게 하는 프로그램이다. GUI 환경에서는 쉘과 직접 작업할 수 있도록 도와주는 터미널 에뮬레이터라는 프로그램이 필요하다. 리눅스에는 다양한 터미널 에뮬레이터가 있지만 모두 쉘에 접근할 수 있게 해준다는 기능을 수행한다. -쉘 프롬프트 쉘이 입력 가능한 상태일 때에만 나타난다. 만약 프롬프트의 마지막 글자가 달러표시($)가 아니라 해쉬 표시(#)라면, 현재 터미널 세션이 슈퍼 유저 권한을 가졌다는 뜻이다. -명령어 히스토리 방금 입력한 명령어를 다시 보려면 위쪽 방향키를 사용해보자. 이러한 기능을 명령어 히스토리라고 한다. -커서 이동 위쪽 방향키로 이전 명령어를 불러온 후, 왼쪽/오른쪽 방향키를 사용하면 커서를 명령어 어느 부분에라도..

[백준, c++] 1436 영화감독 숌

// // Copyright (c) 2021 HyeJin Shin All rights reserved. // #include #include #include #include using namespace std; int arr[10001]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int N; cin >> N; int p = 666; int n = 1; while(n

[백준, c++] 14502 연구소

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net bfs와 브루트포스를 사용해서 푸는 문제였다. 먼저 벽을 세우고, 바이러스 개수만큼 bfs를 돌린 후, 0의 개수를 세는 방식으로 풀었다. 3개의 벽을 세우는 것은 3중 for문으로 각기 다른 좌표들의 벽이 생성되게 했다. 그리고, 바이러스의 위치를 bfs하기전 탐색하는 것보다 입력받을때 바이러스의 위치를 vector v에 추가해 이중 포문을 줄였다. 놓쳤던 것을 몇가지 열거하자면, 1. graph 에 입력을..

공통과제 3번 <Good Matrix>

// // Copyright (c) 2021 HyeJin Shin All rights reserved. // #include #include using namespace std; int arr[300][300]; vector v; int main() { ios_base::sync_with_stdio(false); cin.tie(0); freopen("matrix.inp","r",stdin); freopen("matrix.out","w",stdout); int T; int N=0; cin >> T; while(T--){ if(N!=0){ //N이 0이 아니면(배열에 값을 받은 적이 있다면) arr배열을 초기화 해준다. for(int i=0;i> N; for(int i=0;i arr[i][k]; if(arr..

공통과제 2번 <격자에서 걷기 1>

// // Copyright (c) 2021 HyeJin Shin All rights reserved. // #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); freopen("grid1.inp","r",stdin); freopen("grid2.out","w",stdout); int T; int N, M; int t,s,k; cin >>T; while(T--){ cin >>N>>M>>t>>s>>k; if(t==1){ //타입 1 : {좌상,우상} {우하,좌하}가 짝을 이룸 int d = (k-1)/M; //d는 1행, 2행, 3행과 같은 행을 나타냄. if(s==1){ //좌상 if(d%2==0)c..

공통과제 1번 <그릇>

// // Copyright (c) 2021 HyeJin Shin All rights reserved. // #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); freopen("dish.inp","r",stdin); freopen("dish.out","w",stdout); int T; int n; string s; cin>>T; while(T--){ int cnt=10; cin >> n; cin>>s; for(int i=1;i