개인사

리뷰 문제 이해에도 시간이 많이 걸리고 구현과 시뮬레이션 디버깅에도 다소 시간이 걸렸으나 한번에 풀긴 했다.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를 ..

리뷰 2차원 다익스트라의 기본적인 문제https://www.acmicpc.net/problem/4485 전역 변수n : 각 테스트 케이스마다 주어지는 맵의 한 변의 길이lst : 각 테스트 케이스마다 주어지는 맵 정보를 저장할 2차원 정수 배열, 최대크기는 125*125다.dx, dy : 상하좌우 4방향을 탐색하기 위한 방향 배열Pos : 우선순위 큐에서 현재 위치 정보를 나타낼 구조체, w를 기준으로 오름차순 정렬한다. 함수1. dijkstraint dijkstra() 다익스트라를 통해 출발지에서 도착지까지의 최단 거리를 구하는 함수Pos타입 우선순위 큐 pq를 초기화 하고 거기에 시작 지점 x, y좌표와 시작 지점의 값을 넣어준다.n * n크기의 2차원 정수형 벡터 dist를 기본값을 매우 크게 지정..

리뷰 그리디한 방법을 설계하여 알아서 문제를 푸는 구현문제인듯 하다.https://www.acmicpc.net/problem/2871 전역 변수n : 주어진 문자열의 길이v : 현재 상황에서 문자열이 존재하는지 체크하기 위한 배열 크기는 최대 문자열 크기인 10만으로 초기화 한다.s, t1, t2 : 입력되는 초기 문자열 s, 상근이의 문자열 t1, 희원이의 문자열 t2Prio : 원하는 단어를 얻기 위한 우선순위 큐용 구조체pq : 희열이가 사용할 우선순위 큐, 문자 기준 오름차순, 같다면 인덱스 기준 내림차순 정렬을 하였다. 함수없음  문제풀이n과 s값을 입력받은 뒤 0부터 n - 1까지 순회해준다.v배열을 모두 1로 변경해 주고 pq에는 문자와 해당 문자의 인덱스를 추가해 준다.상근이가 문자열을 가..

리뷰 우선순위 큐 문제는 풀어도 풀어도 어려운 것 같다 ㅠㅠhttps://www.acmicpc.net/problem/13334 전역 변수n, d, ans : 사람의 수 n, 철로의 길이 d, 구간에 포함되는 사람의 최대 수를 저장할 변수 ansnums : 집과 사무실의 좌표를 저장할 pair타입 배열, 크기는 10만으로 초기화 한다. 함수없음  문제풀이n값을 입력 받고 nums배열에 집과 사무실 위치를 입력 받아준다.s보다 e가 크다면 두 수를 바꿔주고, 도착 시간을 기준으로 오름차순 정렬을 할 것이기 때문에 e, s순으로 저장한다.sort메서드를 통해 nums배열을 0부터 n - 1인덱스를 오름차순으로 정렬해 준다.정수형 타입의 우선순위 큐 pq를 초기화 해주고 오름차순으로 우선 정렬한다.d값을 입력 ..

리뷰 브루트포스 알고리즘을 통해 문자열의 길이를 줄이며 각 문자열의 LPS를 구하는 문제https://www.acmicpc.net/problem/1701 전역 변수str : 탐색을 진행할 문자열 변수n, ans : 초기 문자열의 길이 n, 가장 긴 길이를 저장할 변수 ans 함수1. getLPSvoid getLPS(string str) 문자열의 LPS를 구하는 함수매개 변수는 초기 문자열에서 왼쪽의 문자열이 한개씩 날아간 문자열들이 주어진다.해당 문자열에서의 LPS를 구하고 LPS중 가장 큰 값이 ans에 저장되게 된다. 문제풀이초기 문자열 str을 입력 받고 n에 str의 길이를 저장한다.n번의 for문을 개행하고 str의 왼쪽에서부터 한글자씩 제거하며 getLPS함수의 매개변수로 전달해 준다.n번의 ..

리뷰 KMP의 기초가 되는 문제, O(M+N)의 시간 복잡도로 해당 문제를 푸는게 놀라울 따름이다.https://www.acmicpc.net/problem/1786 전역 변수str1, str2 : 원본 문자열 str1, 원본 문자열에서 패턴을 찾을 문자열 str2n, m, cnt : str1의 길이 n, str2의 길이 m, str1에서 str2를 찾은 개수 cntlps, ans : 부분 문자열의 lps를 구할 정수형 벡터 lps, 찾은 인덱스를 저장할 정수형 벡터 ans 함수1. getLPSvoid getLPS(const string& str2) 패턴 문자열 str2에서 LPS를 구하기 위한 함수lps벡터를 m크기로 초기화 해준다. lps[0]은 0으로 초기화 해야하므로 일단 모두 0으로 초기화 해주었..

리뷰 트라이를 사용해 유저가 가입한 순서대로 닉네임이 주어졌을 때, 각 유저의 별칭을 구하는 문제https://www.acmicpc.net/problem/16934 전역 변수Trie : 트라이를 구현할 구조체 동일한 닉네임이 들어올 수 있으므로 cnt라는 변수를 업데이트 해줘야 한다.root : 트라이의 루트를 나타낼 Trie타입 구조체n : 입력 받을 게임 닉네임의 개수 함수1. insertvoid insert(Trie* node, const string& str) 트라이에 게임 닉네임을 입력하고, 별칭을 출력해 주는 함수함수 호출 시 flag를 통해 별칭을 출력했는지 여부를 체크해 준다. 기본값은 1이다.입력 받은 문자열을 순회하며 다음 노드가 있는지 체크해 준다.만약 다음 노드가 존재하지 않을 시 ..

리뷰 개미굴과 유사한 부분이 많은 문제인듯 하다. 하지만 개미굴과 달리 공백이 아닌 역슬래시로 문자열을 구분https://www.acmicpc.net/problem/7432 전역 변수n : 디렉토리 전체 경로의 개수Trie : 맵을 사용하여 디렉토리 정보를 트라이로 사용할 구조체 함수1. insertvoid insert(Trie* node, const vector& strs) 트라이에 디렉토리 문자열을 추가할 함수입력할 디렉토리 이름을 벡터형식으로 입력 받는다.루트노드에서 부터 시작하여 각 문자열을 하위 요소에 넣어준다.만약 처음으로 정의된 디렉토리인 경우 새롭게 할당해주고 이동하는 작업을 해준다. 2. dfsvoid dfs(Trie* node, int level) 깊이 우선 탐색을 통해 디렉토리 정보를..

리뷰 접두사가 동일한 전화번호가 있는지 찾고, 있으면 YES를 없으면 NO를 출력하는 문제https://www.acmicpc.net/problem/5052 전역 변수tc, n : 테스트케이스의 개수 tc, 각 테케마다 입력되는 전화번호의 개수 nlst : 각 테케마다 입력된 문자열을 저장할 문자열 타입 배열, 최대 1만으로 크기를 설정한다.Trie : 트라이를 구현할 구조체, 숫자열 문자를 받아오므로 child의 크기는 10으로 설정한다. 함수1. insertbool insert(Trie* node, const string& str) 트라이에 새로운 전화번호를 넣는 함수전화번호를 넣는 도중 접두어가 있는지 체크까지 해주어야 한다.만약 접두어가 있다면 탐색을 그만하고 NO를 출력해 주어도 된다. 문제풀이t..