개인사

리뷰 오일러 경로 테크닉으로 세그먼트 트리의 노드를 재정의 하고 누적합을 구하는 문제https://www.acmicpc.net/problem/14287 전역 변수MAX_N : 직원의 최대 개수를 저장할 정수형 상수 변수n, m : 직원의 개수를 저장할 정수형 변수 n, 쿼리의 개수를 저장할 정수형 변수 mtree : 세그먼트 트리 정보를 담은 정수형 배열, 크기는 MAX_N * 4로 초기화lst : 오일러 경로 테크닉에 사용할 인접 리스트, 정수형 벡터 타입으로 크기는 MAX_N으로 초기화it : 오일러 경로에서 각 직원의 탐색 시작 시간을 저장할 정수형 배열, 크기는 MAX_N으로 초기화ot : 오일러 경로에서 각 직원의 탐색 종료 시간을 저장할 정수형 배열, 크기는 MAX_N으로 초기화timer : ..

리뷰 https://www.acmicpc.net/problem/9251문자열 두개 중 최장 공통 부분 수열의 길이를 구하는 문제 전역 변수dp : 문자열 a, b의 LCS를 동적계획법으로 찾으며 각 단계를 저장할 2차원 정수 배열 크기는 1001 * 1001로 초기화 함수없음  문제풀이문자열 두개를 각각 문자열 변수 a, b에 저장한다.a, b의 길이를 각각 정수형 변수 len1, len2에 저장한다.len1 * len2 크기의 2중 for문을 개행해 준다. 이때 인덱스는 1부터 문자열의 길이까지 포함되도록 한다.a, b의 현재 탐색범위 이전의 문자가 같을 경우 현재 dp인덱스를 이전 dp인덱스 + 1로 저장해 준다.같지 않을 경우 i의 현재 인덱스, j의 이전 인덱스값과 i의 이전 인덱스, j의 현재 ..

리뷰 에잉.. 코드 한줄 차이로 너무 헤맨 문제였다.https://www.acmicpc.net/problem/1062 전역 변수n, k, ans : 단어의 개수 n, 배울 수 있는 글자의 수 k, 정답을 저장할 변수 ansv : 방문 처리용 배열path : 중복 제거용 벡터lst : 입력된 단어를 저장할 문자열 배열, 입력 문자의 최대 크기인 50으로 초기화 한다. 함수1. btvoid bt(int level) 백트래킹을 통해 배울 수 있는 단어 개수의 최대값을 구하는 함수매개변수로 level을 받아 각 재귀 단계 즉 배운 글자의 개수를 명시해 준다.기저조건은 level이 k - 5가 되었을때이다. cnt를 0으로 초기화 하고 n개의 문자열을 순회한다.flag를 1로 설정하고 각 문자열이 방문처리 되어있..

리뷰 3 * 3 도형을 반전시켜 모든 땅을 흰색으로 만드는 문제https://www.acmicpc.net/problem/10472 전역 변수tc, target : 테스트케이스의 개수tc, 각 테케마다 초기 도형의 비트 정보targetlst : 초기 맵 상태를 얻어올 문자열 배열, 3 * 3크기이므로 크기는 3이다.dx, dy : 비트 반전을 시킬 구간의 방향 배열, 상하좌우 및 제자리를 포함하여 총 5개이다.v : 비트마스킹 시 방문 여부를 저장할 배열 9개의 상태를 저장해야 하므로 2^9보다 크게 설정한다.Pos : 큐 내부에서 현재 비트정보와 변환 횟수를 저장하여 사용할 구조체 함수1. getTargetvoid getTarget() 테스트케이스에서 입력된 도형의 비트 정보를 target변수에 저장하기..

리뷰 조합할 수 있는 모든 음식의 조합을 탐색하여 신맛과 쓴맛의 차를 구하는 문제처음엔 모든 재료의 입력값이 10억 미만으로 봐서 어떻게 풀어야할지 정말 막막했다.모든 재료를 사용해서 요리를 만들었을 때 10억 미만인 점을 꼭 읽길 바란다 ㅠㅠhttps://www.acmicpc.net/problem/2961 전역 변수n, ans : 재료의 개수를 저장할 변수n, 정답을 저장할 변수 ans 10억 이상으로 초깃값을 세팅해 준다.v, ing1, ing2 : 방문 배열v, 신맛과 쓴맛 재료를 저장할 배열 ing1, ing2 모두 재료의 최대크기 10으로 크기를 세팅한다. 함수1. btvoid bt(int level, int val1, int val2) 백트래킹을 통해 완성된 음식의 쓴맛과 신맛의 차를 구하는 ..

리뷰 DFS + 플러드필을 조합하여 AC를 받았다, 조합 관련 가지치기가 필요한 문제 안하면 시간 초과 난다 ㅠhttps://www.acmicpc.net/problem/15686 전역 변수n, m, ans : 맵의 한 변의 길이를 저장할 변수 n, 치킨 집의 최대를 저장할 변수 m, 정답을 저장할 변수 ansdx, dy : 4방향 탐색을 위한 방향 배열lst : 맵 정보를 입력 받을 2차원 정수형 벡터BBQ : 치킨 집 정보를 저장할 구조체, 치킨집의 x, y좌표와 현재 이동한 거리를 d에 저장한다.bbqs : 치킨 집의 모든 정보를 저장할 벡터choose : 현재 선택한 치킨집의 인덱스를 저장할 정수형 벡터cnt : bbqs의 길이를 저장할 정수형 변수chic : 치킨 집의 중복을 방지하기 위해 사용할..

리뷰 구간 대체 업데이트, 구간 합, 느린 갱신, 오일러 경로 테크닉을 활용해야 하는 문제https://www.acmicpc.net/problem/18437 전역 변수n, m : 직원의 수 n, 쿼리의 수 mMAX_N : 주어지는 n값의 최대치를 나타낼 정수형 상수 변수, 100001로 초기화 한다.tree : 세그먼트 트리 정보를 저장할 정수형 배열, MAX_N * 4크기로 초기화lazy : 세그먼트 트리 업데이트 정보를 저장할 정수형 배열, MAX_N * 4크기로 초기화path : 부하 직원을 인접리스트로 저장할 정수형 벡터, MAX_N크기로 초기화it : 서브 트리에서 해당 노드에 진입한 시간을 기록할 정수형 배열, MAX_N크기로 초기화ot : 서브 트리에서 해당 노드에서 빠져나온 시간을 기록할 ..

리뷰 오일러 경로 테크닉에 대한 개념을 이해하게 된 문제일반적인 Lazy propagation을 통한 풀이는 인덱스를 지정하기가 불가능해 보인다.https://www.acmicpc.net/problem/14268 전역 변수MAX_N : n값의 최대치를 저장할 정수형 상수 변수, 크기는 10만 1로 초기화 한다.tree : 세그먼트 트리 정보를 저장할 정수형 배열, 크기는 MAX_N * 4로 초기화lazy : 세그먼트 트리의 업데이트 정보를 저장할 정수형 배열, 크기는 MAX_N * 4로 초기화n, m : 직원의 수를 저장할 변수 n, 쿼리의 개수를 저장할 변수 mpath : 직원간의 상하 직속 정보를 인접리스트 형태로 저장할 정수형 벡터, 크기는 MAX_N으로 초기화it : 서브 트리의 시작시간(세그먼트..

리뷰 문제 이해에도 시간이 많이 걸리고 구현과 시뮬레이션 디버깅에도 다소 시간이 걸렸으나 한번에 풀긴 했다.https://www.acmicpc.net/problem/19236 전역 변수dx, dy : 8방향 탐색을 위한 방향 배열v : 이미 잡아먹힌 물고기를 방문처리 하기 위한 배열max_val : 잡아먹은 물고기의 번호 최대값을 저장하기 위한 변수sdir : 최초에 잡아먹은 물고기가 갖고 있던 방향 정보를 저장하기 위한 변수Fish : 물고기의 위치와 진행 방향을 저장하기 위한 구조체fishes : 초기 물고기들의 위치와 방향 정보를 저장할 Fish타입 벡터lst : 초기 맵에 존재하는 물고기 번호를 저장하기 위한 4 * 4크기의 정수형 벡터 함수1. inputvoid input() 4 * 4사이즈의 ..

리뷰 max이 하나가 정답을 좌지우지 했다 ㅠㅜhttps://www.acmicpc.net/problem/2056 전역 변수n : 작업의 개수 함수없음  문제풀이n값을 입력 받고 작업 시간 정보 times와 인접 리스트를 초기화할 정수 벡터 path를 n + 1크기로 초기화 한다.1부터 n개의 각각의 작업에 걸리는 시간을 times 벡터에 저장해 준다.이후 선행이 필요한 작업을 인접 리스트로 추가해 준다, 역방향으로 삽입해 주어야 한다.선행 작업의 개수를 저장할 벡터 cnt를 n + 1크기, 기본값은 0인 상태로 초기화 해준다.각 작업을 순회하며 작업의 인접리스트에 저장된 작업을의 cnt를 증가시켜준다.정수형 큐 q를 초기화 한 후에 cnt가 0인 작업을 큐에 넣어준다.정답을 저장할 정수형 벡터 ans를 ..