개인사

리뷰 2차원 배열을 1차원 배열로 옮겨온 후 정렬한 값 중에서 k번째 수를 뽑는 특정 조건을 갖는 이분 탐색 문제 https://www.acmicpc.net/problem/1300 문제 풀이n, k값을 받아오고 left를 1, right를 n * n, result를 0으로 초기화 해준다. 해당 타입들은 모두 long long으로 설정left가 right를 넘지 않는 범위 내에서 while문 실행 mid를 left + right를 2로 나눈 몫으로, cnt를 0으로 초기화 해준다.1부터n까지 탐색하며 mid를 i로 나눈 값을 cnt에 추가해 준다, 이때 해당 값이 n보다 커선 안된다.탐색을 마친 후 cnt가 k보다 크거나 같으면 right 범위를 mid - 1로, 아니라면 left의 범위를 mid + 1로..

리뷰 정수형 변수 타입을 잘 확인하자.. 처음에 틀리고 나서 모두 long long으로 바꿔줬으나 다익스트라 리턴 형식을 int로 두었었다.https://www.acmicpc.net/problem/24042 문제 풀이n, m을 지역변수로 설정한다, long long타입 거리 배열을 10만 1 크기로 초기화 해준다.시뮬레이션 상에서 현재 위치 정보가 될 Pos구조체를 정의해 준다. pq를 활용할 것이니 내부에 compare 함수 포함인접 리스트를 표시할 EDGE 구조체를 정의해 준다, 노드와 해당 노드의 신호등 인덱스 정보가 담긴다.EDGE타입의 2차 배열 path를 초기화 해준다. 해당 벡터를 통해 인접리스트를 체크할 것이다.n과 m을 입력 받고 path의 사이즈를 n + 1로 초기화 해준 뒤 거리 배열..

리뷰 시작 문자열이 특정 조건을 가진 문자열을 더해 도착 문자열로 변할 수 있는지 여부를 체크하는 문제https://www.acmicpc.net/problem/12919 문제 풀이문자열 a와 b를 입력 받고, b의 크기에서 a크기를 뺀 값을 limit으로 저장한다. 이는 백트래킹의 기저조건이 될 값이다.변수 flag를 0으로 초기화 하고 함수 bt에 매개변수 0을 전달하여 백트래킹을 시작한다. 이때 0은 재귀 단계를 나타낸다.백트래킹의 기저조건은 flag가 1일때와 level이 limit에 도달했을 때다, 이는 둘의 문자열의 길이가 동일할때를 의미한다.문자열 a에서 b로 가는 재귀 말고, 문자열 b에서 a로 가는 재귀를 실행해 줄 것이다.만약 문자열 b의 앞이 B라면 문자열을 뒤집은 후 맨 뒤의 B를 삭..

리뷰 입력되는 숫자의 범위가 10000이므로 10000까지의 값을 미리 구해놓은 뒤 O(1)의 속도로 쿼리를 처리하는 문제https://www.acmicpc.net/problem/15989 문제 풀이정수형 배열 dp를 10001 크기로 설정한 후, dp[1], dp[2], dp[3]은 1로 초기화를 해준다.n이 10인 경우까지 손코딩을 해보면 쉽게 점화식을 도출할 수 있다.점화식 : dp[i] = dp[i - 3] + i / 2 + 1t값을 입력 받고 t번에 입력되는 테스트케이스를 dp의 인덱스로 출력해 주면 된다. 참고 사항n = 1 ~ 10까지의 케이스11 121 1 12 131 1 1 12 1 12 23 11 1 1 1 12 1 1 12 2 13 1 13 21 1 1 1 1 12 1 1 1 12 2..

리뷰 방향 배열을 사용한 전형적인 시뮬레이션 문제 문제 풀이전역변수로 원자의 개수 n, 남은 원자의 개수 cnt, 정답을 출력할 ans, 맵 배열 lst, 방향 배열을 설정해 주었다.좌표의 범위는 -1000 ~ 1000이지만 -인덱싱을 방지하기 위해 +1000을 해준다.추가로 원자가 만나지 않고 지나치는 경우를 방지하기 위해 *2를 해준다. 즉, 좌표의 범위는 4000 * 4000이다.원자의 정보를 담을 구조체 Atom과 위치를 나타낼 구조체 Pos를 만들고 원자 벡터 atoms를 초기화해 주었다.init 함수를 통해 cnt, ans를 0으로 초기화 하고 atoms배열 및 맵 정보를 테케마다 초기화 해준다.input 함수를 통해 n값을 입력 받고 n개의 원자 정보를 atoms 벡터에 추가해 준 뒤 맵에 ..

리뷰 벽을 정확히 3개를 세워 학생들이 선생님의 눈을 피할 수 있게 하는 완전 탐색 문제https://www.acmicpc.net/problem/18428 문제 풀이전역 변수로 맵의 변의 크기 n, 정답 여부체크용 ans, 맵 lst, 방문 여부 v, 방향배열, 선생님 정보 T를 설정해 준다.input 함수를 통해 n값과 맵의 정보를 받는다, 이때 T가 입력된 경우 구조체 Pos타입 벡터 T에 추가해 준다.dfs 함수를 통해 완전 탐색을 돌려준다. 매개변수 level은 벽 설치 개수, row는 탐색을 재개할 행 정보다.벽의 개수가 3개가 되면 기저조건에 해당된다, bfs를 통해 시뮬레이션을 돌려준다.선생님을 순회하며 4방향으로 감시를 시작한다, 범위를 벗어나거나 벽을 만나기 전까지 해당 방향을 쭉 탐색한..

리뷰 문제 풀이전역변수로 테케의 수 tc와 지렁이의 수 n, 이동과 대기한 수를 나타낼 Move, Stay 정답 변수 ans를 설정한다.init 함수를 통해 ans를 최대한 큰 값, Move와 Stay를 0으로 초기화 해준다.input 함수를 통해 n값과 n개의 지렁이의 좌표를 Pos 구조체를 활용하여 pos배열에 저장해 준다.dfs 함수를 통해 각 지렁이가 짝을 지었을때의 좌표 벡터값을 구해줄 것이다.매개변수로는 지렁이 인덱스를 나타낼 level과 x좌표의 값 sumX, y좌표의 값 sumY를 전달해 준다.Move와 Stay가 각각 n / 2보다 작을 경우 Move와 Stay를 각각 증가시켜주고 재귀를 진행하면 된다.재귀를 전달할땐 level인덱스의 x, y좌표를 sumX, sumY에 더해주고 leve..

리뷰 시작 지점과 편의점과 도착지점을 같은 배열을 통해 사용했는데 배열의 크기를 편의점의 개수로만 초기화 해서 틀려버렸다 ㅠㅠhttps://www.acmicpc.net/problem/9205 문제 풀이전역 변수로 테케개수용 tc, 편의점 개수 n, 총 노드의 개수 length를 초기화 해주었다.방문 배열 및 인접 리스트용 Pos 구조체 타입의 벡터 path와 정답을 저장할 문자열 타입 벡터 ans를 전역 초기화init 함수를 통해 각 테스트 케이스마다 인접 리스트와 방문 배열을 초기화 해주었다.input 함수를 통해 n값과 path 벡터에 시작지점, 편의점, 도착정보를 입력 받아 인접리스트를 생성해 준다.bfs 함수를 통해 각 인접리스트를 순회하며 탐색을 하고, 도착지점에 도착을 하면 true를 리턴해 ..

리뷰 큐를 사용하여 적절한 조건문과 BFS를 조합하여 풀었다.https://www.acmicpc.net/problem/2573 문제 풀이전역 변수로 n, m, ans = 0과 2차원 배열로 맵용 lst 및 섬 덩어리를 찾을 chk와 방향배열을 넣어주었다.좌표와 현재 값을 나타낼 Pos 구조체를 정의해 주고 Pos구조체 타입의 큐 q를 초기화 해주었다.input함수를 통해 n, m값을 입력 받고, 맵의 정보를 받아온다. 이때 빙산은 q에 저장해 준다.solution함수를 통해 시뮬레이션 및 전반적인 답을 도출해 낼 것이다.재귀를 통해 직관적으로 확인해도 되지만, 나는 그냥 while문을 통해 시간의 흐름을 나타냈다.time을 0으로 초기화 하고 while문을 항상 true로 실행한다.chk_island 함..

리뷰 모든 CCTV가 바라볼 수 있는 모든 방향을 체크하고 사각지대가 제일 적은 케이스를 찾는 문제https://www.acmicpc.net/problem/15683 문제 풀이전역 변수로는 맵, 방향 배열과 행의 개수 n, 열의 개수 m, cctv의 개수 k, 정답을 출력할 ans를 설정했다.n과 m값을 받아오고 n * m의 맵을 받아온다. 이때 현재 들어온 값이 1이상 이라면 별도의 처리가 필요하다.입력값이 6인 경우 벽이므로 continue, 1 ~ 5 사이라면 CCTV이므로 cctv 배열에 추가해 준 뒤 k의 개수를 증가시킨다.이때 각 CCTV의 시야는 모두 다르므로 구조체 CCTV의 look에 각각의 시야각을 추가해 준다.CCTV들의 방향을 저장할 빈 벡터 dirs를 초기화 하고 level 0부터..