개인사

리뷰 https://www.acmicpc.net/problem/2568lower_bound를 통해 가장 긴 증가하는 부분 수열을 구하고 경로 역추적을 해줘야 하는 문제4달 전엔 경로 역추적에 대한 지식이 없어 틀렸으나 다시금 보니 문제 풀이가 가능했다. 골드 전깃줄 문제에 비해 티어가 훨씬 높으며 경로 역추적을 모른다면 어떻게 풀어야 할지 모르겠다.[G5] 백준 2565번 전깃줄 C++ LIS, 이분 탐색 [G5] 백준 2565번 전깃줄 C++ LIS, 이분 탐색리뷰 https://www.acmicpc.net/problem/2565알고리즘 분류는 DP로 되어 있지만 기본적인 LIS(가장 큰 증가하는 수열) 문제이다.  전역 변수n : 주어지는 전깃줄의 개수를 저장할 변수ans : 정답을 저장할 변zzzz..

리뷰 https://www.acmicpc.net/problem/2565알고리즘 분류는 DP로 되어 있지만 기본적인 LIS(가장 큰 증가하는 수열) 문제이다.  전역 변수n : 주어지는 전깃줄의 개수를 저장할 변수ans : 정답을 저장할 변수 함수없음  문제풀이n값을 입력 받고, pair(이후 pii) 타입의 오름차순 우선순위 큐 pq를 초기화 한다.n개의 전깃줄 정보를 입력 받고, 전깃줄 A의 위치와 B의 위치를 묶어 pq에 push한다.정수형 벡터 lis를 초기화 한다.pq가 빌 때 까지 while루프를 실행하고, 매 루프마다 요소를 한개씩 꺼내준다.lower_bound 메서드를 통해 lis에 현재 요소의 B전깃줄의 위치 이상의 값이 있는지 찾아준다.만약 존재하지 않는다면, lis에 B전깃줄의 위치를 ..

리뷰 https://www.acmicpc.net/problem/17425약수의 합의 누적합을구하는 문제  전역 변수N : n의 최대값을 정의할 정수형 상수 변수t : 테스트 케이스의 개수를 저장할 변수n : g(N)을 구하기 위한 인덱스를 저장할 변수 함수없음  문제풀이약수의 합을 저장할 long long타입의 벡터 F를 N크기로, 모든 값은 1인 상태로 초기화 한다.2부터 N - 1까지의 수를 순회하며 자신의 배수인 수에 자기 자신을 더해준다.long long타입의 벡터 G를 N크기로 초기화 해준다.1부터 N - 1까지의 수를 순회하며 벡터 G에 누적합을 저장해 준다.t를 입력 받고, t번의 while루프를 순회해 준다.매 루프타마다 n에 값을 입력 받고, G의 n번 인덱스 값을 출력해 준다. 트러블 ..

리뷰 https://swexpertacademy.com/main/code/problem/problemDetail.do SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 이분 탐색으로 접근했다가 틀리고 그리디로 접근했더니 AC를 받은 문제 백준에 동일한 문제가 존재한다. 1 + 1 문제[G5] 백준 2212번 센서 C++ [G5] 백준 2212번 센서 C++리뷰 https://www.acmicpc.net/problem/2212고속도로에 집중국을 적절히 배치해서 수신 가능 센서 영역의 길이의 합이 최소가 되게 하는 문제2일간 문제를 고민했는데 적절한 방법이 떠올라 적용했더니 ACzzzz955.tistory.com  전역..

리뷰 https://www.acmicpc.net/problem/16120스택을 활용하여 주어진 문자열이 PPAP 문자열인지 체크하는 문제문제를 이해하기 좀 힘들었으나 그냥 PPAP를 P로 치환 할 수 있다는 조건이 있는 문제이다.  전역 변수s : PPAP문자열인지 검사할 문자열을 저장할 변수stack : 스택으로 사용할 문자열 함수1. PPAPvoid PPAP() 스택의 맨 뒤 문자열이 PPAP인지 체크하는 함수스택의 크기가 4이상, 스택의 맨 뒤 4글자가 "PPAP"라면 while루프를 계속 돌아준다.while 조건이 참이라면 스택에서 4개의 요소를 pop해준다.pop이 완료된 후에는 'P'를 스택의 맨 뒤에 삽입해 준다.  문제풀이문자열 s를 입력 받고, s의 크기만큼 for문을 개행해 준다.sta..

리뷰 https://www.acmicpc.net/problem/1351재귀를 통해 n을 p와 q의 관점에서 최적해를 구하고, 이미 구한 값을 기억해두어 재귀 탐색을 최소화 하는 문제  전역 변수n : 답을 구하고자 하는 인덱스를 저장할 변수p, q : 인덱스에 나누어 몫을 구하기 위한 값을 저장할 변수dp : 메모제이션을 활용하기 위한 해시맵 함수1. solvell solve(ll num) 재귀를 통해 최적해를 찾기 위한 함수매개변수로 탐색을 진행할 인덱스 num을 입력 받는다.기저 조건으로 이미 dp의 num 인덱스가 구해진 상태라면 해당 값을 리턴해 준다.기저 조건에 해당하지 않는다면 num을 p와 q로 나눈 값을 매개변수로 전달하여 재귀를 진행한다.재귀를 빠져나오며 dp의 num 인덱스에 3번에서 ..

리뷰 3 * 3크기의 퍼즐을 정렬된 상태로 만드는 최단 시간을 구하는 문제https://www.acmicpc.net/problem/1525  전역 변수lst : 초기 퍼즐 정보를 저장할 정수형 2차 배열v : 퍼즐의 상태를 방문처리 하기 위한 해시맵dx, dy : 4방향 탐색을 위한 방향 배열Pos : 퍼즐의 현재 상태를 정의하기 위한 구조체, 좌표 위치  x, y와 현재 맵 정보 b, 현재까지 소요 시간 t로 구성되며 t를 기준으로 오름차순 정렬한다. 함수1. bfsint bfs(const Pos& start) 너비 우선 탐색을 통해 퍼즐이 정렬되기 까지 걸리는 최소 시간을 구하는 함수매개변수로 초기 퍼즐 정보 start를 전달받는다.Pos타입의 우선순위 큐 q를 초기화 하고, start를 q에 pus..

리뷰 https://www.acmicpc.net/problem/2212고속도로에 집중국을 적절히 배치해서 수신 가능 센서 영역의 길이의 합이 최소가 되게 하는 문제2일간 문제를 고민했는데 적절한 방법이 떠올라 적용했더니 AC를 받았다. SWEA에 유사 문제가 존재한다.https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWJHjcFqdyoDFAUH SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com  전역 변수n : 센서의 개수를 저장할 변수k : 집중국의 개수를 저장할 변수ans : 정답을 저장할 변수lst : 센서의 위치를 저장할..

리뷰 https://www.acmicpc.net/problem/1700문제를 어렵게 생각해서 계속 틀리다가 간단하게 생각하니 AC를 받게 된 문제  전역 변수n : 콘센트의 구멍 개수를 저장할 변수k : 콘센트에 꽂고자 하는 제품의 개수를 저장할 변수ans : 정답을 저장할 변수dic : 콘센트에 꽂힌 물품 정보를 저장할 해시 셋 함수없음  문제풀이n, k값을 입력 받고, 정수형 벡터 lst를 k크기로 초기화 해준다.k개의 제품 정보를 입력 받고, lst에 저장해 준다.k개의 제품을 순회하며 dic이 n보다 작거나, 이미 존재하는 제품일 경우 dic에 insert해준다.콘센트에 연결된 제품을 제거해야 할 경우 정수형 변수 Del과 Midx를 -1로 초기화 해준다.dic을 순회하며 아직 사용하지 않은 제품..

리뷰 https://www.acmicpc.net/problem/2437복잡하게 생각할 수록 더 나락에 빠지는 문제  전역 변수n : 주어지는 추의 개수를 저장할 변수lst : 추의 무게를 저장하기 위한 정수형 배열 함수없음  문제풀이n을 입력 받고, n개의 추의 무게를 입력 받아 lst배열에 저장해 준다.sort메서드를 통해 lst배열을 오름차순으로 정렬해 준다.정수형 변수 ans를 1로 초기화 해준다.n개의 추를 순회하며 현재 추가 ans보다 작거나 같은 경우 ans에 추의 무게만큼 더해준다.ans에 저장된 값을 출력해 준다. 트러블 슈팅multiset을 사용하여 매 숫자마다 upper_bound 메서드를 통해 사용할 수 있는 추 중 가장 무거운 추를 추가해 줬다.예제의 정답은 나왔으나 결국 시간 초과..