개인사

리뷰 LIS는 꼭 풀어봤으면 좋겠다. 난이도에 비해 코드길이가 정말 짧다! 꿀통 알고리즘https://www.acmicpc.net/problem/2352 문제 풀이포트의 개수 n개를 입력 받고 LIS를 저장할 정수형 벡터 ans를 초기화 해준다.n개의 입력을 받고, 입력 받은 포트 번호가 기존의 포트보다 크다면 ans에 push 해준다.만약 기존의 포트보다 작거나 같으면 해당 포트의 위치를 찾아 교체해 주면 된다.반복이 종료된 후 ans의 size를 출력해 주면 된다. 참고 사항lower_bound를 사용하려면 algorithm을 include 해주어야 한다.  정답 코드#include#include#includeusing namespace std;int main() { ios::sync_with_std..

리뷰 게임 상에서 각 건물이 지어질 수 있는 최소 시간을 구하는 문제 위상 정렬을 통해 쉽게 해결할 수 있다.https://www.acmicpc.net/problem/1516 문제 풀이건물의 개수 n과 각 건물의 건설 시간 t배열, 인접 리스트용 벡터 path를 전역 변수로 초기화 해준다.input 함수를 통해 n값을 입력 받고 1~n번째 건물의 건설 시간과 인접 리스트를 입력 받아준다.solution함수를 통해 각 건물의 건설 완료 시간을 구해줄 수 있다.각 건물의 건설 완료 시간 벡터 sum과 건물을 짓기위한 우선순위의 개수 벡터 cnt를 n + 1, 0값으로 초기화 한다.각 건물의 인접리스트를 순회하며 인접 리스트에 저장된 건물의 cnt를 1개씩 늘려준다.정수형 큐 q를 주비하고 cnt가 0인 건물..

리뷰 처참한 전투흔적.. 위상 정렬의 응용 문제였는데 꽤나 애를 먹었다.최소 거리를 구하는 부분은 쉽게 나왔으나 1분도 쉬지 않고 달려야 하는 도로의 수를 구하는게 어려웠다.처음엔 거리 배열을 사용하여 max로 갱신될 경우 이전 경로로 교체를 해주고, 값이 같을땐 현재 저장된 거리에 새로 들어온 경로를 더해주는 방식으로 생각했었다.하지만 이전까지 같은 경로로 오다 갈라진 후 다시 합쳐지는 케이스에서는 해당 방법을 사용할 수 없었다.이후 set를 사용해 왔던 경로를 모두 저장해 준 뒤 set의 크기를 출력해 주었으나 메모리 초과가 났다.결국 왔던 길을 역추적 해서 검증이 가능한 길의 개수만 구해지는 방식으로 풀이하였다.해당 방식이 맞는 접근 방법이나, 중복이 가능한 케이스들을 놓쳐서 방문 처리를 하고 나니..

리뷰 위상 정렬을 통해 가중치가 있는 간선을 갖고 특정 노드의 최소값을 구하는 문제https://www.acmicpc.net/problem/1005 문제 풀이테스트 케이스의 개수 tc, 노드의 개수 n, 간선의 개수 m, 목표 노드 dest를 전역변수로 초기화 해준다.인접 리스트를 담을 정수형 벡터 path, 각 노드의 소요시간 정보 times의 크기를 n의 최대값으로 설정해 준다.init 함수를 통해 times 배열 초기화, path 백터를 초기화 해준다.input 함수를 통해 n, m값과 각 노드의 소요시간, 간선정보, 목표 노드를 입력 받는다.solution 함수를 통해 dest 노드가 건설이 완료 되기까지의 최소 시간을 출력해 준다.cnt, sum 벡터를 n + 1 크기로, 초기값은 0으로 초기화..

리뷰 위상 정렬의 가장 기본이 되는 문제https://www.acmicpc.net/problem/2252 문제 풀이n, m과 정수형 벡터 path를 n의 최대 크기인 32001로 전역 변수로 초기화 해준다.input 함수를 통해 n, m값을 받고 m개의 키 정보를 받아 path 벡터에 연결 리스트를 추가해 준다.solution 함수를 통해 위상 정렬을 수행해 준다, 정수형 벡터 cnt를 n + 1크기, 0으로 초기화 result를 초기화 해준다.1 ~ n을 탐색하여 i번째 path를 탐색하여 인접리스트에 저장된 노드의 cnt를 늘려준다.정수형 큐 q를 초기화 하고 1 ~ n을 탐색하여 만약 cnt가 0인 키 정보가 있다면 큐에 추가해 준다.큐가 빌때까지 while 루프를 돌며 현재 키를 result에 추..

리뷰 5달만에 다시 찾아와 깨부신 문제 파이썬에 비해 입력을 처리하는데 시간이 더 쓰인거 같다.https://www.acmicpc.net/problem/14911 문제 풀이정수형 벡터 lst를 초기화 해주고 getline을 통해 첫 줄을 문자열로 받아와 준 뒤 두번째 줄은 정수 l에 저장해 준다.문자열 s를 stringstream타입 ss로 변환해 주고, 공백을 기준으로 문자를 뽑아 정수형으로 변환 시킨다.변환시킨 정수를 lst에 넣어준 뒤 length변수에 lst의 사이즈를 구해준다.lst를 오름차순으로 정렬시킨 후 length!번의 브루트포스 알고리즘을 실행해 준다.만약 lst[i] + lst[j]가 l과 같다면 set에 해당 숫자 쌍을 추가해 준다.브루트포스가 끝나면 ans에 저장된 숫자 쌍을 모두..

리뷰 5달만에 다시 덤볐으나 문제 조건을 제대로 읽지 않아 또 져버렸다... https://www.acmicpc.net/problem/26596 문제 풀이재료의 개수 m과 황금 비율을 비교할 gold_rate를 1.618로, 문자열, 정수로 이루어진 맵 dic를 초기화 해준다.m값을 입력 받고 m만큼 루프를 돈 뒤 재료명과 값을 입력받아 재료명을 키로 갖는 맵에 값을 더해준다.flag를 0으로 초기화 해주고 맵을 두개로 나누어 순회하며 특정 재료의 값 * 황금비율이 다른 재료의 값과 동일한지 찾아준다. 이때 재료가 동일한 경우에는 황금 비율로 인정하지 않는다.만약 황금 비율을 찾았다면 flag를 1로 변경한 후 break 처리를 해준다.flag가 1인 경우 Delicious! 를, 아닐 경우 Not De..

리뷰 10달만의 복수를 완료하였다, 확실히 10달 전보단 문제를 보는 시각이 많이 늘어난 것 같다.https://www.acmicpc.net/problem/9017 문제 풀이참여자의 수 n과 등수 정보 배열 lst, 팀 정보 구조체 Team과 해당 배열 teams를 전역 변수로 초기화 해준다.init 함수를 통해 팀 정보 teams 배열을 각 테스트 케이스 마다 초기화 해준다.input 함수를 통해 n값을 받고, 특정 팀이 들어온 등수와 팀의 총원, 5번째로 들어온 등수를 기록해 준다.solution함수를 통해 각 팀의 점수를 비교하여 가장 등수가 낮은 팀을 찾아준다.점수를 1부터 시작하여 팀의 총원이 6명이 이상인 경우만 등수를 기록해 준다.각 팀을 순회하며 총원이 6명 이상인 팀만 상위 4명의 등수를..

리뷰 배열을 돌리는 정석적인 문제 90도 회전과 상하, 좌우 반전 배열 그룹화 등이 포함되어 있다.https://www.acmicpc.net/problem/16935 달팽이 처럼 배열을 돌리는 문제보단 난이도가 쉬운 편인 것 같다.아래는 달팽이 처럼 배열을 순회하며 돌리는 문제 백준 17406번 배열 돌리기4 C++ 백트래킹, 구현, 시뮬레이션리뷰 완전 탐색을 통해 배열을 돌리는 경우의 수를 모두 실행하고 최적값을 찾는 문제회전을 하는 횟수인 k의 범위가 6으로 작아서 완전 탐색을 돌려도 시간이 크게 많이 걸리지는 않았다. httpszzzz955.tistory.com 문제 풀이행정보를 나타낼 변수 n, 열정보를 나타낼 변수 m, 회전 요청의 개수 r과 정수형 2차배열 lst를 전역변수로 세팅한다.inpu..

리뷰lower_bound를 통해 가장 긴 증가하는 부분 수열을 만들고, 해당 수열의 길이와 변경 내역 정보를 저장 및 역추적 하여 LIS를 출력하는 문제https://www.acmicpc.net/problem/14003관련 문제가장 긴 증가하는 부분 수열 4 : https://www.acmicpc.net/problem/14002 문제 풀이n과 100만 크기 정수 배열 nums, 정수형 벡터 temp, lis를 전역 변수로 초기화 해준다.n값을 입력 받고 nums에 각 수열 정보를 입력 받은 뒤 BS 함수를 실행 시켜준다.pos벡터를 n크기로 초기화 해 준 뒤 n개의 숫자를 모두 탐색해 준다.만약 temp에 i번째 수이상이 존재한다면 해당 위치를 i로 바꿔준다. 없다면 temp의 뒤에 i를 추가해 준다.매..