깡뇽

- 문제직사각형 격자 미로에서 탈출하려고 함. 각 칸은 통로 또는 벽. 벽은 통과 불가능하며, 통로 중 한 칸에는 미로 탈출 문이 존재. 그러나, 문은 레버를 당겨야만 열 수 있으며, 레버도 통로들 중 한 칸에 존재.즉, 출발 지점에서 먼저 레버 칸으로 이동해서 레버 당긴 후에 미로 탈출 문 칸으로 이동해야 함.아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있으며, 미로 한 칸 이동은 1초 소요.최대한 빠르게 미로를 빠져나가는데 걸리는 시간 구하기. - 입력 문자열 배열 maps : 미로 - 출력탈출에 필요한 최소 시간 리턴(단, 탈출 불가능 시에는 -1 리턴) - 제약 사항5 (S : 시작 / E : 출구 / L : 레버 / O : 통로 / X : 벽)시작 지점과 출구, 레버는 항상 다른 ..

- 문제그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. - 입력N : 정점 (1~1,000)M : 간선 (1~1,000)V : 시작노드 - 풀이DFS는 인접 행렬을 활용한 재귀 방식으로 풀었다.BFS는 queue를 사용해서 풀었다.#include #include #include using namespace std;int arr[1001][1001] = { 0, };int visited[1001] = { 0, };void dfs(int start) { cout q; q.push(start); whi..

String 스트링char를 사용해 문자열을 표현하려면, char str[100]; 선언 후 문자열 끝에 null 문자('\0')가 있어야 한다. C++ 에서는 #include 헤더를 사용해서 string을 다양하게 활용 가능하다.string s = "string"; 과 같이 타입으로 선언 가능하다.- 길이 : s.length()- 비교 : strcmp( 문자열1, 문자열2)              -> 동일하면 0             -> 다르면 -1 (문자열1이 문자열2보다 사전순으로 앞) OR 1 (문자열1이 문자열2보다 사전순으로 뒤)- 결합 : strcat( 문자열1, 문자열2 )              -> 문자열2가 문자열1에 결합             * 결합에 += 연산자를 사용할 수..

- 문제 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다. 이제 두 번째 사진처럼 지역에 많은 비가 내려서 높이가 4 이하인 모든 지점이 물에 잠겼다고 하자. 이 경우에 물에 잠기는 지점을..

문제 : 1년 동안 각 달의 수영장 이용 계획을 세우고 가장 적은 비용으로 수영장을 이용할 수 있는 방법 찾기 1. 1일 이용권 : 하루 이용 가능. 2. 1달 이용권 : 한 달 이용 가능. 매달 1일부터 시작. 3. 3달 이용권 : 연속 세 달 이용 가능. 매달 1일부터 시작. (11월, 12월, 다음해 1월 사용 불가능) 4. 1년 이용권 : 일 년 이용 가능. 매년 1월 1일부터 시작. - 입력 테스트 케이스 T 1일 이용권 요금, 1달 이용권 요금, 3달 이용권 요금, 1년 이용권 요금 1월~12월 이용 계획 - 출력 수용장 이용 계획대로 진행했을 때 가장 적게 지출하는 비용 - 제약 사항 10 ≤ 이용권 요금 ≤ 3,000 각 달의 이용 계획은 각 달의 마지막 일자보다 크지 않음 문제 이해 1월..

문제 : N * N 크기의 부지에 최대한 긴 등산로 만들기 1. 등산로는 가장 높은 봉우리에서 시작. 2. 높은 지형에서 낮은 지형으로 가로 또는 세로 방향으로 연결. (높이가 같거나 낮은 지형이거나 대각선 방향 연결 불가능) 3. 한 곳을 골라 최대 K 깊이 만큼 지형 깎기 공사 가능. - 입력 지도 크기 N, 최대 공사 가능 깊이 K N * N의 지도 정보 - 출력 만들 수 있는 가장 긴 등산로의 길이 - 제약사항 3 ≤ N ≤ 8, 1 ≤ K ≤ 5, 1 ≤지형의 높이 ≤ 20 가장 높은 봉우리 최대 5개 지형은 정수 단위로만 깎기 지형 높이 1보다 작게 만들기 가능 문제 이해 N * N 크기의 지도에서 등산로를 만들고, 그 중에서 가장 긴 등산로의 길이를 찾자! 접근 방법 DFS 사용해서 등산로를..

"2115. [모의 SW 역량테스트] 벌꿀채취"에 기반을 두는 문제. 문제 : N개의 벌통이 있는데, 각 벌통에 있는 꿀의 양으로 부터 벌꿀을 채취해 얻을 수 있는 최대 수익 알아내기 1. 꿀은 최대 C까지만 채취 가능 2. 서로 다른 벌통에서 채취한 꿀이 섞이지 않도록 하나의 벌통에서 채취한 꿀은 하나의 용기에 담기 3. 하나의 벌통에서 꿀 채취할 때, 한 번에 모든 꿀을 채취 4. 채취한 꿀을 팔 때, 하나의 용기 속 꿀의 양이 많을수록 상품가치가 높고 각 용기의 꿀 양을 제곱만큼 수익 발생 ex) 6, 1, 8 만큼 꿀이 담긴 용기 3개를 판매하면 (6*6) + (1*1) + (8*8) = 36 + 1 + 64 = 101 수익이 생김 - 입력 테스트 케이스 개수 T T줄 - 벌통 크기 N, 꿀 채취..

Q. 주사위 게임을 했을 때, 나올 수 있는 모든 경우의 수를 구해보자. - 입력 : 주사위의 개수 → 정수 1개 - 출력 : 해당 주사위로 나올 수 있는 주사위 눈의 모든 경우 주사위 N개가 있다면, N개의 주사위에서 각 주사위 눈을 선택 ex. N = 3이면, 1번 주사위 -> 2번 주사위 -> 3번 주사위 순으로 작동 즉, 현재(now)에 a를 넣으면 다음(next)에서는 a+1을 넣음. 1부터 6 중에서 하나를 뽑고 다음 주사위로 넘어감. int path[10]; void func(int a){ //지금 a번째 주사위를 뽑을 차례 // 0~N-1번 : 정상 // N번 주사위~ : 존재하지 않는 주사위 // N번의 주사위까지 도달 -> 0~N-1번 주사위에서 모두 눈을 선택 완료. if(a>=N){..

함수 지역변수 : 함수 안에서 선언한 변수 전역변수 : 어디에서나 같은 변수 (공통 사용) + 함수의 파라미터(변수가 가지고 있는 값을 준 것)도 지역변수로 취급. 재귀함수 함수가 자기 자신을 호출하여 문제를 해결하는 방법 DFS, Union Find, 분할정복, DP(Top-Down)에서 활용. void func1(){ func1(); } int main(){ func1(); return 0; } 이때, 너무 많이 쌓이면서 Stack Overflow(메모리 부족) 발생. 특정 함수에서 멈추라고 해줘야 함. 작동을 멈출 함수를 정해야하고, 반복되는 함수들이 같은 함수이더라도 구분할 수 있어야 함. ⇒ 변수 활용 (매개변수 or 전역변수 활용 가능 / 매개변수 주로 사용) → void func1(int a..

Q. 만약 aabbccabcbc 가 주어졌을 때, 각 문자가 몇 개 존재하는지 알 수 있을까? - 목표 : '문자' → 해당 문자의 개수 찾기 ⇒ DAT 활용 DAT DAT : Direct Access Table 배열의 index에 의미를 부여함. int DAT[]; 로 정의한 배열에서 index는 문자, value는 해당 문자 개수를 나타냄. WHEN : 기록 할 때 1) 카운팅 2) 존재 확인 WHERE : 배열의 삽입과 추출 . . . n 차원에서 방향을 가지고 사용할 때 BAD : 정수 외의 값(char까지는 가능)은 index로 사용 불가능 너무 큰 범위 사용 불가능 int main(){ char temp[100]; cin >> temp; int DAT[256] = {0, }; //기본적인 문자..

17142번 연구소3 출처 : https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net

폴리오미노 : 1x1 크기 정사각형 여러 개 이어 붙인 도형 - 정사각형은 서로 겹치면 안 됨. - 도형은 모두 연결되어야 함. - 정사각형의 변끼리 연결되어 있어야 함. (꼭짓점끼리만 맞닿아 있으면 안 됨.) 4개를 이어 붙이면 "테트로미노" -> 5가지 NxM 크기 종이 위에 테트로미노 하나 놓을 때, 종이 1x1 크기의 칸 하나에는 정수가 쓰여져 있음. 테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성해라. 테트로미노는 반드시 한 정사각형이 한 칸을 포함하도록 놓고, 회전이나 대칭 가능. - 입력 1줄 : 종이의 세로 크기 N, 가로 크기 M 2~N줄 : 종이에 쓰여 있는 수. ( i번째 줄의 j번째 수) - 출력 테트로미노가 놓인 칸에 쓰인..