개인사

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

리뷰부분 문자열 생성과 문자열로 이루어진 16진수를 10진수로 변환하고, 정렬하는 문제 문제 풀이각 테스트 케이스마다 정수 n, k값과 문자열 s를 받아와 준다.정수형 벡터 lst를 초기화 하고, n번의 for문을 돌려준다.문자열 s의 앞 부터 n을 4로 나눈 값 만큼의 부분의 부분 문자열을 생성하고 이를 10진수로 변환해 준다.만약 lst 내에 해당 숫자가 없을 경우 lst에 추가해준다.그리고 제일 앞쪽의 문자를 뒤쪽으로 옮긴 뒤 탐색을 계속 진행해 준다.for문이 종료되었을 경우 lst를 내림차순으로 정렬해 주고 k - 1 번째 인덱스의 수를 출력해 주면 된다. 참고 사항stoi(temp, nullptr, 16);문자열을 16진수로 인식하고 10진수로 변환하는 함수 정답 코드#include#inclu..

리뷰다익스트라 라고 보기엔 애매하고 그냥 우선순위 큐를 사용한 BFS 문제 라고 보면 될 것 같다. 문제 풀이n값을 받고 1과 0이 붙어있길래 그냥 string으로 맵 정보를 받아주었다.방향 배열과 방문 처리를 할 배열을 초기화 해준다. 이때 방문 배열은 벽을 뚫은 횟수 기록용 3차 배열로 초기화거리, x좌표, y좌표를 인자로 갖는 구조체 Pos를 초기화 해준다.우선순위 큐에서 정렬용으로 사용할 compare 객체를 초기화 하고, 거리를 기준으로 오름차순으로 정렬해 준다.bfs를 시작하고 0, 0부터 시작해 n-1, n-1에 도달 했을 경우 벽을 부순 횟수를 리턴해 주도록 한다.리턴값을 출력해 주면 된다. 참고 사항bfs함수 내부 구조 상세 설명Pos를 자료구조로 갖고, Pos 내 d를 오름차순으로 정렬..

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

리뷰노드 간 간선이 주어질때 사이클이 존재하는지 체크하고 사이클이 존재한다면 해당 간선의 입력 순서를 출력하는 문제 문제 풀이노드의 개수는 최대 50만 이므로 50만 1짜리 정수형 배열을 선언해 준다.n과 m값을 입력 받고 n개의 노드를 인덱스를 1부터, 자기 자신의 인덱스를 value로 갖게끔 초기화 해준다.m번의 간선 정보를 입력 받고, 만약 a와 b가 같은 그룹에 속해 있다면 현재 간선이 입력된 번째를 출력하고 return같은 그룹에 속해있지 않다면 a와 b를 Union 처리 해준다.간선 정보를 모두 입력받아도 return되지 않았다면 0을 출력해 준다. 참고 사항같은 그룹에 속해 있다는 것은 두 노드를 Find해주고 반환된 값이 서로 같은 경우이다.  정답 코드#includeusing namesp..

리뷰1부터 N까지의 최단 경로의 길이를 찾되, 반드시 두 정점을 거친 후 이동 해야하는 문제 문제 풀이노드의 개수 n과 간선의 개수 e를 입력 받고 인접리스트를 나타낼 2차 pair형 벡터 lst를 n + 1크기로 초기화 한다.e개의 간선의 정보를 lst에 양방향 간선으로 추가해 주고, v1와 v2 값을 입력 받아준다.1 => v1 => v2 => N과 1 => v2 => v1 => N의 최단 경로를 각각 구해준다.두 경로 중 더 작은 값을 정답으로 출력하면 된다, 만약 두 경로 모두 INT_MAX라면 -1을 출력해 준다. 참고 사항우선순위 큐의 자료형을 pair를 쓸 경우 greater>를 통해 쉽게 최소힙으로 변환할 수 있다.INT_MAX를 사용해 주기 위해서는 climits를 include를 해줘야..

리뷰세그먼트 트리에 머지 소트 트리를 접목하여 범위 내 특정 값보다 큰 숫자의 개수를 출력해 주는 문제https://www.acmicpc.net/problem/13537 문제 풀이n값을 입력 받고 정수형 벡터 lst에 n개의 요소를 입력 받아준다.정수형 2차 벡터인 tree를 n * 4크기로 초기화 해준 뒤 lst를 통해 build를 진행해 준다.이때 리프 노드는 각 lst index의 값을 갖는 길이 1짜리 정수형 벡터로 초기화 해준다.이후 상위 노드는 merge 메서드를 사용해 각 리프 노드를 정렬된 상태로 merge하여 관리해 준다.이후 m값을 입력 받고 m개의 쿼리를 실행해 준다. 업데이트는 없으므로 질의만 받아오게 된다.범위와 찾을 기준이 될 값을 받아오고, query 함수에서 해당 범위를 찾았..

리뷰MST인데 테스트케이스 여러개를 곁들인.. 문제였다. 예제만 보고 테케를 나눠주지 않아 첫시도에 틀렸다.https://www.acmicpc.net/problem/6497 문제 풀이정답을 저장할 벡터 ans, 간선 정보를 저장할 edges, 간선 전체길이를 저장할 max_dist를 초기화 해준다.while루프를 시작하고 1번에서 초기화한 리스트 들을 모두 초기값으로 변경해 준다.n과 m 값을 받고 해당 값들이 모두 0일 경우 while루프를 종료한다.간선의 정보 m개를 가중치, 시작 노드, 종료 노드 순으로 edges 벡터에 tuple형태로 추가해 준다.max_dist에 가중치를 더해주어 전체 길이를 최신화 해준다.간선 정보를 모두 받아왔으면 간선의 가중치를 기준으로 오름차순 정렬해 준다.이후 유니온 ..