개인사

리뷰DFS를 통한 완전탐색과, PQ를 통한 값 비교, 시뮬레이션 까지 필요한 까다로운 문제   SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 문제 풀이각 테스트 케이스 마다 init과 input, solution으로 나누어 진행하였다.init에서는 각 테스트 케이스마다 초기값을 세팅해 준다.input에서는 맵 정보와 사람, 계단 정보를 받아와 초기화 해준다.solution에서는 DFS를 실행하고, DFS 내부적으로 재귀를 거치며 기저조건에 달성하면 시뮬레이션을 돌려준다.모든 재귀가 종료되고 나면 ans에 저장 되어 있는 값을 각 테스트 케이스마다 출력해주면 된다. 참고 사항1. init()맵 정보를 모두 0으로 ..

리뷰촌수를 구하는 완전 탐색 문제, DFS, BFS, 다익스트라 뭘 써도 괜찮을 듯 하다.  문제 풀이n, sn, dn, m값을 차례로 입력 받고, 방문 처리 배열을 101 크기, 0으로 초기화 해준다.정수형 2차 벡터 lst에 노드 정보를 받아와 인접 리스트를 생성해 준다, 단 방향이던 양 방향이던 상관 없을듯?이후 bfs를 돌려주고 시작 노드에서 종료 노드까지의 거리를 구해주는데, 이때 방문 배열에 이전 값 + 1을 해주는 식으로 촌수를 구해주었다.큐가 빌때까지 while을 돌다가 목표 노드에 도달했을 경우 현재 노드의 방문 배열 값을 리턴해준다.만약 while이 종료될 때 까지 만나지 못하고 bfs가 종료된다면 -1을 리턴해 준다.리턴값을 출력해주면 된다. 참고 사항없음  정답 코드#include#..

리뷰1굉장히 쉬운 백트래킹 문제, 정답률이 67%인 이유가 있는듯 하다. 문제 풀이각 테케마다 최소값을 비교할 mp 변수를 5억정도의 큰 크기로 초기화 해준다.1일권, 1달권, 3달권, 1년권의 가격을 모두 받아오고, 1년간 월별 수영장을 사용할 일수를 받아온다.level과 price가 0인 채로 dfs를 실행해 주고, 4개의 이용권을 각각 사용하는 경우의 수를 완전탐색 돌려준다.기저조건에 도달했다면 mp와 비교하여 최소값을 갱신해 주고, 각 테스트 케이스마다 mp값을 출력해 준다. 참고 사항dfs함수의 내부구조는 다음과 같다.매개변수로는 level과 price를 사용해 준다. level은 개월 수를 나타내줄 것이고 price는 누적 값을 나타낸다.기저조건으로 level이 12 이상일때 즉, 1년이 지났..

리뷰브루트포스와 백트래킹이 접목된 문제 재귀는 아직도 너무 어렵다.. 문제 풀이각 테케마다 max_val을 0으로 초기화 해주고, 2차 배열을 받아와 준다.일꾼 1이 0, 0부터 시작하여 일꾼의 작업공간을 제외한 하위 작업공간에서 일꾼 2가 일을 하도록 시켜야 한다.우선 일꾼 1이 m크기만큼 벌통을 수집하여 팔았던 수익을 bt 함수로 부터 구해준 뒤 이를 dfs 함수에 인자로 전달한다.dfs함수는 일꾼 1이 일했던 범위를 피해 일을 할 수 있는 나머지 부분에서 일을 해준다.일꾼 1이 일을 할때마다 bt 함수를 실행해 마찬가지로 벌통을 수집하여 판 수익을 구하고 max_val에 일꾼 1이 일한 값과 일꾼 2가 일한 값을 더해준 후 최대값을 지속적으로 갱신해 준다.모든 for문과 재귀가 종료되었을때 각 테케..

리뷰처음엔 최악의 케이스만 생각하여 시간내에 가능 할까? 라는 생각이 들었는데 생각보다 여유롭게 풀렸다.백트래킹이나 DFS는 생각이 너무 많아지면 더 어려운 문제인 것 같다. 문제 풀이각 테스크 케이스 마다 min_val은 아주 큰 값으로, max_val은 아주 작은 값으로 초기화를 해준다.숫자의 개수와 부호의 개수를 각각 받아와 주고 각 숫자를 배열에 입력 받아준다.재귀의 깊이를 나타낼 level과 연산에 사용할 숫자를 매개변수로 백트래킹을 통해 완전 탐색을 실행해준다.모든 완전 탐색을 마친 뒤 각 테스트 케이스마다 max_val - min_val 값을 출력해 주면 된다. 참고 사항dfs 함수 정보기저 조건 : level이 n - 1에 도달했을 경우 max_val과 min_val을 최신화반복문 : 연산..

리뷰DFS와 브루트포스 알고리즘이 접목된 문제문제 풀이배열을 초기화 해줘야 한다. 각 테케의 데이터를 1 ~ N로 받고 나머지는 -1로 초기화 해준다.출발한 카페로 돌아와야 하니 각 DFS를 실행할때 현재 위치의 좌하 방향의 좌표를 도착지로 설정해 준다.경로상에 같은 카페가 있으면 안되니 방문 처리를 해줘야 한다. 방문한 좌표의 값을 v배열의 인덱스로 방문처리지나온 길에 대한 정보를 기억해야 한다. path 벡터에 기록해 준다. (길이를 구하는 문제이니 아무 값이나 들어와도 상관x)도착지에 도달했을 경우 path벡터의 길이가 방문한 카페의 길이가 된다. 최대값을 ans변수에 기록해 준다.모든 좌표에 대한 DFS가 종료된 경우 ans의 값이 4보다 작으면 -1로 변경 (완벽한 사각형이 만들에 진게 아니다...

리뷰쉽게 생각했다가 푸는데 한시간은 걸린 문제 생각지 못한 까다로운 조건이 많다. 이래서 설계를 하고 풀어야 하는데.. 문제 풀이n개의 줄에 노드간 상관 관계를 받아준다. -1이 주어졌을땐 해당 인덱스를 루트 인덱스로 따로 저장해 주자인접 리스트 형태가 완료 되었다면 삭제할 값을 받아오고 해당 인덱스의 벡터를 날려주자루트 인덱스부터 dfs를 시작한다. 이때 루트가 비어있다면 리턴을 해주자 (루트가 삭제된 케이스)현재 노드의 자식을 순회하고, 만약 삭제된 노드를 만났는데 현재 노드의 크기가 1일 경우 cnt를 1개 올린다.자식의 리스트가 비어있다면 cnt를 올리고 다음 요소를 순회한다.둘 다 해당되지 않으면 해당 인덱스를 dfs 해준다. dfs가 전부 종료되면 cnt를 출력해 준다. 참고 사항참고해야할 조..

개요그래프정점과 정점사이의 상관관계를 나타내는 자료구조 노드와 간선으로 이루어져 있다.1. 그래프의 방향그래프는 방향이 있는 그래프와 방향이 없는 그래프로 나뉘어 진다. (양방향과 단방향)2. 가중치각 노드간 간선에 가중치가 있을 수 있다. (거리 등) 3. 트리그래프의 한 종류로 LEVEL이 설정되어 있는 그래프이다. LEVEL 0에 ROOT 노드가 있으며, 하위 노드는 자식이 된다. 반대로 자식 입장에서 ROOT 노드는 부모 노드이며, 자식간의 관계는 형제 노드가 된다.트리의 특징방향 그래프만 존재루트 노드가 한개만 존재계층 형식으로 비순환 그래프4. 인접 행렬위 트리 노드를 인접 행렬로 표현하면 아래와 같이 표현할 수 있다.노드12345101001200110300000400000500000 출발지 ..

개요백트래킹 : 재귀 호출 중 가망성이 있는지 여부를 판별하면서 진행하는 방식재귀를 통해 경우의 수를 모두 탐색하여 구하고자 하는 조건에 일치하는 경우를 모두 구할 수 있다.실행하고자 하는 하는 반복 횟수, 재귀를 빠져나올 기저 조건, 각 반복 횟수에 적용할 식을 잘 세우면 효율적으로 사용할 수 있다.  예제1. 조합을 선택하여 출력하기서로 다른 n개의 수에서 k개의 수로 이루어진 조합을 출력하기코드#include using namespace std;int n, k;int arr[100];int DAT[110];void bt(int index) { // 2. 기저 조건 if (index >= k) { for (int i = 0; i > n >> k; for (int i = 0; i > arr[i]; }..

개요함수란 무엇인가? 코드를 기능 단위로 묶어둔 것이다.return type funcname() { body}와 같은 형식을 가진다. 지역/전역/함수를 사용할때 어떤 메모리 영역에서 쓰이는지 잘 구분해야 한다. 재귀는 다시 돌아오다 라는 뜻으로 재귀 함수는 다시 돌아오는 함수이다. 즉 다시 실행되는 함수 (run / recall)재귀 함수는 자기 자신을 리턴 혹은 호출 하므로 종료 조건을 설정하지 않으면 원하는 의도가 나오지 않을 가능성이 매우 높다. (함수를 호출하는 것 자체가 메모리를 사용하는 것이므로 while처럼 무한루프에 빠지진 않을 것이다.)따라서 재귀 함수를 사용할 당시엔 종료 조건을 설정해 주어야 한다. 예제1. 무한 루프코드#include using namespace std;void he..