분류 전체보기

(C++) 백준 1182번 - 부분수열의 합

문제 링크 : https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 풀이 백트래킹을 활용하여 풀이하였다. 부분수열에 숫자 하나를 포함하거나 포함하지 않거나 하는 경우를 모두 시도하여 조건에 맞는 경우를 카운트하는 식으로 풀이하였다. #include using namespace std; int n, s, tmp, size, cnt; int num[20]; int used[20]; void subseqadd(int i..

(C++) 백준 9663번 - N-Queen

문제 링크 : https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 백트래킹을 활용하여 풀이하였다. Queen은 같은 행이나 열, 같은 대각선 상에 존재하면 서로를 잡을 수 있다는 점을 알아야 한다. 그렇기에 한 행에 놓으면 같은 행의 다른 칸에 놓을 수 없음을 이용하여 한 행에 Queen을 하나씩만 두고, 열과 대각선 상만 피해서 Queen을 놓게 구현하면 된다. #include using namespace std; int n; int isUsedcol[15..

(C++) 백준 15649번 - N과 M (1)

문제 링크 : https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 백트래킹을 사용한 풀이이다. 이미 특정 숫자가 배열에 들어가 있는지 arr을 순회하면서 확인하고, 들어있지 않은 숫자들만 배열에 삽입한다. 사이즈가 m이 되는 순간 지금까지 배열에 저장해 놓은 숫자들을 출력한다. #include using namespace std; int n, m; int arr[8]; void nNm(int num, int idx){ for(int x = ..

캐치카페 신촌점 이용 후기

지난 04/22(금), 코테이토 정규세션을 캐치카페 신촌점에서 진행하였습니다. 쾌적하고 넓은 시설, 편안한 분위기 속에서 세션을 잘 진행할 수 있었습니다! 그뿐만 아니라 무료 커피 또는 차도 제공되어 더욱 기분 좋은 시간을 캐치카페에서 보낼 수 있었습니다. #캐치카페신촌점 #캐치카페 #카페대관 #대학생 #진학사 #취준생

(CS) ArrayList, LinkedList, Stack, Queue, Deque

ArrayList vs LinkedList ArrayList는 내부적으로 배열로 구현되어 있으며, 배열의 크기를 동적으로 조절할 수 있다. ArrayList는 인덱스를 이용한 요소 접근이 매우 빠르기 때문에, 특정 요소를 검색하는 작업에 유용한다. 또한 ArrayList는 LinkedList에 비해 메모리 사용량이 적다. 그러나 ArrayList는 요소의 삽입과 삭제 작업 시 배열 내에서 해당 요소 이후의 요소들을 전부 이동시켜야 하기 때문에, 요소의 삽입과 삭제가 빈번하게 일어나는 경우에는 성능이 저하될 수 있습니다. LinkedList는 이중 연결 리스트로 구현되어 있으며, 각 요소는 자신의 이전 요소와 다음 요소를 가리키는 두 개의 포인터를 가지고 있다. 따라서 LinkedList는 요소의 삽입과 ..

(C++) 백준 13549번 - 숨바꼭질 3

문제 링크 : https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 백준 1697번(숨바꼭질)과 상당히 유사한 문제이다. 비슷하게 풀이하되 시간이 들지 않는 2배 순간이동을 최우선으로 체크하고, 다음으로 - 연산, + 연산 순으로 BFS를 쓰면 된다. #include #include #include #define X first #define Y second using namespace std; int n,k; ..

(C++) 백준 7569번 - 토마토

문제 링크 : https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 풀이 토마토(백준 7576번)의 3차원 버전이다. 2차원과 동일하게 진행하되 체크를 6개의 방향으로 진행하도록 BFS를 구현하면 된다. #include #include #include using namespace std; int dx[6] = {1,0,0,-1,0,0}; int dy[6] = {0,1,0,0,-1,0}; int dz[6] = {0,0,1,0,0..

(C++) 백준 10026번 - 적록색약

문제 링크 : https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 백준 1926번 그림 문제와 거의 동일한 문제이다. BFS를 이용하여 풀이를 하였다. 색약이 아닌 사람들은 1926번에서 풀이한 그대로 하면 되고, 색약인 사람들의 경우에만 R과 G를 동일한 색인 것처럼 풀이하면 된다. //boj 10026 성공 #include #include #include #define X first #define Y second using name..

(C++) 백준 1074번 - Z

풀이 재귀를 이용하여 풀이하였다. 2의 거듭제곱으로 커져가기 때문에 한 변의 길이가 2, 4, 8, 16, ... 순으로 증가한다. 그렇기 때문에 한 변이 2일 때를 재귀를 종료하는 base condition으로 두고, 사각형들을 4개로 분할하여(한 변의 길이를 2배씩 줄여) 나가면서 풀었다. #include using namespace std; int calZ(int n, int r, int c){ if(n == 1){ // 2 * 2 일 때 if(r == 0 and c == 0) return 0; else if(r == 0 and c == 1) return 1; else if(r == 1 and c == 0) return 2; else return 3; } int half = (1= half and ..

(C++) 백준 11729번 - 하노이 탑 이동 순서

문제 링크 : https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 풀이 재귀 문제의 대명사격인 하노이 탑 문제이다. s에서 l로 n개를 이동하려면 다음과 같은 과정을 거치면 된다. 1. 제일 아래에 있는 가장 큰 판을 제외한 n-1개의 판을 s에서 6-s-l로 이동시킨다. 2. 제일 큰 판을 s에서 l로 이동시킨다. 3. 1에서 6-s-l로 이동한 n-1개의 판을 l로 이동시킨다. 이 과정을 재귀로 반복하여 문제를 풀이하였다. #inc..