개인사

리뷰 https://www.acmicpc.net/problem/17471예제가 다 맞길래 제출했는데 1%에서 틀리길래 당황했다. 하지만 질문게시판에 존재하는 몇가지 반례를 보고 문제점을 파악하였다. 문제 풀이n값을 받아주고 정답을 출력할 변수 ans를 10억으로 초기화 해준다.각 노드에 대해 투표권을  입력 받아주고, 인접 배열을 생성해 준다. 나는 노드를 0부터 시작했기 때문에 b에서 1을 빼줬다.벡터 a, b를 초기화 하고 dfs에 매개변수를 level = 0, 빈 벡터a, 빈 벡터b를 전달해 주고 실행하였다.dfs에서는 level이 벡터에 들어있는 노드의 개수이자, 노드 자체를 나타낸다.벡터 a에 level 노드를 넣어주고 재귀를 실행한다, 재귀를 빠져나오면 a에서 노드를 빼준다.벡터 b에 leve..

리뷰 아ㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏ 재귀 너무 싫다.https://www.acmicpc.net/problem/17136  문제 풀이input 함수를 통해 맵을 초기화 해주고 1의 총 개수를 변수 one에 저장해 준다. 색종이 5개도 각각 5개씩 저장해 준다.dfs함수를 시작한다 매개변수로는 행, 붙힌 색종이 개수, 남은 1의 개수를 전달해 준다.당연하게도 기저조건은 맵에 1이 존재하지 않는 경우이다, 정답 ans를 갱신하고 리턴해 준다.만약 현재 붙힌 색종이 개수가 ans보다 크거나 같고, 25개 이상을 붙였다면 더 이상 탐색할 필요가 없다.x행부터 탐색을 시작하여 1을 만날 경우 1~5번 인덱스의 색종이를 하나씩 대입해 본다.만약 i번째 색종이를 붙힐 수 있다면 색종이를 붙히고 해당 색종이의 개수를 한개 줄..

리뷰 0, 1 좌표에서 파이프를 옮겨 n - 1, n - 1 좌표까지 이동 가능한 모든 경로를 구하는 문제 문제 풀이전역 변수로 변의 크기 n, 정답용 변수 ans, 맵을 나타낼 lst 배열, 방문 처리를 나타낼 v 배열, 방향 배열을 초기화 한다.n값을 입력 받고 ans를 0으로 초기화 한 뒤에 n * n크기의 맵을 lst에 초기화 해준다.0, 0과 0, 1을 방문 처리해 주고 0, 1 좌표 및 방향 배열 인덱스는 0 (오른쪽)으로 dfs를 시작해 준다.dfs의 매개변수로는 현재 좌표 x, y값과 방향 위치인 dir을 받는다.기저 조건으로 x, y 좌표가 n - 1일때 ans를 증가시키고 리턴을 해준다.현재 방향 인덱스에 -1 ~ 1범위로 더해주고 만약 인덱스 범위를 벗어난다면 continue 처리를 ..

리뷰 SWEA를 풀면서 처음으로 만난 덱을 써서 푸는 문제 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 문제 풀이tc를 입력 받고 각 테스트 케이스를 개행한다, 이후 init, input, solution 함수를 실행하고 각 테케마다 ans를 출력해줬다.1. init()ans를 0으로 초기화 해주고 각 자석 정보를 clear를 통해 초기화 해준다.2. input()k값을 받아와 주고, 4개의 자석에 각각 N극과 S극 정보를 받아와 준다.3. solution()k번을 순회하며 회전시킬 자석과 방향정보를 입력 받고 각 자석을 돌려준다.자석을 돌리기 전에 방문배열 초기화와 회전시킬 자석의 방문처리가 필요하다.4.bt..

리뷰숫자 사이에 연산자를 주어진 개수만큼 집어넣어 가장 큰 값과 작은 값을 구하는 문제 SWEA의 숫자 만들기와 동일한 문제  SWEA 4008번 [모의 SW 역량테스트] 숫자 만들기 C++ DFS, 백트래킹리뷰처음엔 최악의 케이스만 생각하여 시간내에 가능 할까? 라는 생각이 들었는데 생각보다 여유롭게 풀렸다.백트래킹이나 DFS는 생각이 너무 많아지면 더 어려운 문제인 것 같다. 문제 풀이각zzzz955.tistory.com  문제 풀이n값과 n개의 정수를 nums 배열에 입력 받아준다.덧셈, 뺄셈, 곱셉, 나눗셈의 각 연산자의 개수를 입력 받아준다.백트래킹을 시작한 후 내부에서 최소값과 최대값을 구해 최대값, 최솟값 순으로 줄바꿈하여 출력해 준다. 참고 사항백트래킹 내부 구현기저 조건은 level이 n..

리뷰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을 최신화반복문 : 연산..

리뷰접근하기 정말 힘든 문제였는데 SSAFY 강의를 듣고 재정리를 하여 통과하였다. 싸피 짱! 문제 풀이각 테스트 케이스 마다 약품 사용 횟수의 최소값, 현재 약품 사용 횟수, 약품 사용 여부 리스트를 초기화 해준다.보호필름 정보를 입력 받아 주고 재귀를 실행해 준다. 이때 전달해주는 매개변수는 row가 기준이 된다.약품을 사용하지 않은 케이스, A약품을 사용한 케이스, B약품을 사용한 케이스로 나누어 재귀를 실행한다.만약 약품을 사용하지 않았다면 path에 -1을 넣어주고, cnt를 증가하지 않는다.만약 약품을 사용했다면 path에 A약품은 0을, B약품은 1을 넣어주고 cnt를 1 증가시킨다.다음 row로 재귀를 실행해 주고 위에 적용했던 처리 조건들을 복구 해준다.만약 모든 행을 다 돌았다면 모든 ..

리뷰SSAFY 백트래킹 시간에 배워서 풀었다. 싸피 짱! 문제 풀이DAT 배열을 총 세개 만들어 준다. col 기준, 우하향, 좌하향 대각선에 방문 체크를 하기 위함우하향, 좌하향 DAT의 index로 전달해 줄 값을 저장할 2차 배열 2개를 만들어 준다.우하향 배열은 우하향 대각선의 값이 같게, 좌하향 배열은 좌하향 대각선의 값이 같게 만들어준다. 값은 DAT의 범위 내에 있고, 각 대각선과 값이 겹치지 않는다면 상관 없다.row를 매개변수로 0부터 백트래킹을 시작한다. 만약 row가 n과 동일하다면 배치가 가능한 것이다. cnt를 1 더해준다.for문을 시작하고 0부터 n까지 순회를 돈다. 위에서 말했듯 행은 현재 재귀의 row로 받고 있다.현재 열에 놓을 수 있다면 (판별 조건을 통과했다면) 모든 ..