본문 바로가기

전체 글44

백준 2156번 : 포도주 시식 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 2020. 6. 30.
백준 1987번 : 알파벳 https://www.acmicpc.net/problem/1987 1987번: 알파벳 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 www.acmicpc.net DFS와 되추적 기법 (1,1)에서 시작되는 노드를 따라 갔던 정점 빼고 가장 많은 정점의 수를 출력해야한다. 즉, (1,1)에서 시작하여 모든 노드를 방문하며 - > DFS / BFS 모든 경우의 수를 생각해야한다 -> 되추적 기법 모든 경우의 수를 생각해야하는 거면 DP도 되지 않나라는 생각을 했는데 2차원 배열이 사용되는 그런 길? 타일 같은 공간이 필요하면 되추적으로 하는 것 같다(.. 2020. 6. 30.
백준 10250번 : ACM 호텔 https://www.acmicpc.net/problem/10250 10250번: ACM 호텔 문제 ACM 호텔 매니저 지우는 손님이 도착하는 대로 빈 방을 배정하고 있다. 고객 설문조사에 따르면 손님들은 호텔 정문으로부터 걸어서 가장 짧은 거리에 있는 방을 선호한다고 한다. 여러분은 www.acmicpc.net #include using namespace std; int main() { int T = 0; cin >> T; while (T--) { int result = 0; int H = 0, W = 0, N =0; cin >> H >> W >> N; if (N % H == 0) { result = H * 100; result += N / H; } else { result = (N % H) * 100.. 2020. 6. 23.
백준 2606번 : 바이러스 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어�� www.acmicpc.net 시작 정점 1에서 시작하는 그래프의 모든 경로의 개수를 구하는 문제 모든 경로 -> DFS / BFS 사용 나는 DFS로 문제를 풀었다. #include #include //sort, vector #include//queue using namespace std; vector v[101]; //vertex를 넣을 벡터 배열 bool visitCom[100]; //방문 확인하는 배열 true면 방문 i.. 2020. 6. 23.
백준 1743번 : 음식물 피하기 https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 문제 코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다. 이러한 음식물들은 근처에 있� www.acmicpc.net 유기농 배추한 DFS, BFS 문제로 나는 DFS로 풀었다. 어디서 음식물덩어리 크기를 세주는 증감식을 쓸지만 알면 쉽게 풀 수 있다. #include using namespace std; int N = 0, M = 0, K = 0; int tile[101][101] = { 0 }; int sizeMax[5001]; int idx = 0; void junk(int row, int col) { if (.. 2020. 6. 22.
[자료구조] DFS & BFS (C++) 보호되어 있는 글 입니다. 2020. 6. 22.
백준 1260번 : DFS와 BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 스스로 짜지 못 해 인터넷 세계를 방방곳곳 구경하며 얻은 소스를 해석하면서 풀었다ㅜ ▶왜 굳이 배열이 아니라 벡터를 썼는가? 1차원 배열을 쓰면 (1, 5) (1, 6) (1, *) 일 때 하나의 인덱스에 하나의 값 밖에 넣지 못 하기 때문에 안되며, 2차원 배열일 경우 NxN에서 안 쓰는 메모리가 많고 arr[1][0] = 5; arr[1][1] = 2; a.. 2020. 6. 22.
백준 10835번 : 카드게임 https://www.acmicpc.net/problem/10835 10835번: 카드게임 첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오�� www.acmicpc.net DP 동적 프로그래밍 문제 2차원 배열 arr[L][R]에 score을 memorization 해주었다. 이 과정에서 &score = arr[L][R], 주소 연산자를 사용하여 편리하게 해주었다. 1. 왼쪽만 버릴 때 L+1 2. 둘 다 버릴 때 L+1, R+1 3. L>R -> 오른쪽만 버릴 때 R+1 를 재귀함수로 구현하면서 max함수를 이용해 큰 score를 a.. 2020. 6. 22.
백준 9663번 : N-Queen https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 이 문제는 대표적인 되추적 기법 문제로 NxN 체스판에 N개의 Queen끼리 공격하지 않게 배치하는 경우의 수를 구하면 된다. 난 소스를 스스로 짜는게 어려웠다.. 정말 많은 블로그와 유투브를 보고 소스를 따라쳐서 컴파일 디버깅하면서 하나하나 변수가 어떻게 변하는지 본 이후에야 이해할수 있었다ㅠㅠ 소스 풀이 일차원 배열 하나를 board[row] = col 로 사용해주었다. board[1] = 1은 1x1에 퀸을.. 2020. 6. 19.
백준 1978번 : 소수 찾기 https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net #include using namespace std; int IsPrimeNumber(int n) { int ii = 0; if (n == 1) { return 0; } else { for (ii = 2; ii > T; for (int i = 0; i < T; i++) { cin >> n; result += IsPrimeNumber(n); } cout 2020. 6. 15.