[목차]310 [백준 11000번 / C++] 강의실 배정 자료구조 Priority_Queue는 Queue 의 한 종류인데 말 그대로 우선순위에 따라 정렬된 Queue라고 보면 도니다. 와 동일한 라이브러리에서 지원 해주며 특정 원소를 push 를 할 때 O(logN)만에 이루어진다. 해당 시간 baebalja.tistory.com 그리디 문제이다 방 배정을 하기 위한 최소 값을 구하기 위해서는 각 강의에서의 종료시간과 시작시간이 겹치지 않으면 된다. #접근방법 pair 벡터를 생성하여 시작 시간과 종료 시간을 저장한다. 오름차순으로 정렬한다. priority_queue를 최소힙으로 만들어주고 종료시간을 push한다 (종료시간의 최소값이 top에 위치) for문을 돌면서 priority_queue에 top에 위치한 값보다 같거나 큰 시작시간의 강의가 들어오게되면.. 백준/그리디 2022. 2. 21. [프로그래머스 Level_2 / C++ / 카카오] [3차] 압축 문제를 읽고 이해가 잘 되지 않아서 예제를 보고 이해를 한 문제이다. #접근방법 A~Z 까지 unordered_map 에 형태로 저장 ( A : 1 ~ Z : 26 ) map(사전) 에 저장되지 않은 문자열을 찾을 때까지 문자들을 새로 생성한 문자열에 이어 붙여준다. map(사전)에 저장되지 않은 문자열을 찾으면 바로 전에 있던 값(prev)을 출력하고 이어 붙인 문자열을 사전에 등록 반복문에 종료된 후 prev에 값이 남아있다면 해당 값 또한 answer 에 넣어준다. #include #include #include #include using namespace std; unordered_map m; vector solution(string msg) { vector answer; int cnt =1; f.. 프로그래머스/Level_2 2022. 2. 20. [백준 2529번 / C++] 부등호 완전 탐색 문제이다. #접근 방법 0부터 9까지 반복문을 돌리는 재귀함수를 생성 후 호출. 0부터 9까지 반복문을 돌리면서 부등호가 일치한지, 방문 하지 않았는지 체크하고 부합되면 재귀함수 호출. 부등호의 개수를 넘게되면 max값과 min값을 저장하여 리턴. 스택에 쌓였던 모든 재귀함수가 반환되면 max값과 min값을 출력한다. * min 값이 012 일 때는 12 로 출력되니 이럴 경우 앞에 0을 하나 붙여준다. #include #include #include #include using namespace std; vector v; int visited[10], k; long long max_n=-1; long long min_n=9999999999; void dfs(int cnt, string s, i.. 백준/완전 탐색 2022. 2. 19. [프로그래머스 Level_2 / C++ / 카카오] [3차] n진수 게임 #접근 방법 1. "숫자 0 ~ ?" 까지 while문을 돌리면서 해당 숫자의 n진수 값을 변환하여 문자열 s 에 저장. 2. 문자열 s 를 뒤집어주고 temp 라는 문자열에 붙인다. 3. temp 사이즈가 m+1 보다 크거나 같으면, - answer 값에 튜브의 순서에 해당하는 인덱스 문자값을 붙인다. (문자열 temp 인덱스를 1부터 시작하기 위해 처음에 문자 하나 저장 해놓음. 그래서 조건식이 m+1 인 것이다. ) - cnt +1 증가 - temp 인덱스 1부터 M까지 자르고 이후 문자열 이어 붙이기 5. cnt값이 미리 구할 숫자의 갯수(t)와 동일하면 break; #include #include #include #include using namespace std; string solution(.. 프로그래머스/Level_2 2022. 2. 18. [프로그래머스 Level_1 / C++ / 카카오] 키패드 누르기 #접근방법 1. ( '*' ,'0', '#' ) -> (10, 11, 12) 로 치환 2. 1, 4, 7 일 때 왼손 위치 해당 값으로 이동, 3, 6, 9 일 때 오른손 위치 해당값으로 이동 3. 2, 5, 8, 11 일 때 왼손과 오른손의 위치를 중간열로 이동 (이동할때 카운트 +1, 이미 가운데에 위치했을 경우 변화 x 4. 왼손과 오른손이 위치한 숫자 값에서 가려고 하는 숫자값의 차이의 절댓값 구하기 5. 절댓값이 더 작은 값이 나온 손에 위치 저장. 같을 경우 hand 변수에서 어떤 손잡이인지 확인하고 해당 손에 위치 저장. #include #include #include using namespace std; int temp_l, temp_r, l_cnt, r_cnt; string solutio.. 프로그래머스/Level_1 2022. 2. 18. [백준 1149번 / C++] RGB거리 dp배열을 생성해서 풀면 된다. #접근방법 1. 2차원 dp 배열 생성한다. 2. 현재 dp값에 이전 dp 배열에서 다른 색을 가지고 있는 집들 중 작은 값을 선택해서 더해준다. 3. 최솟값 출력한다. #include #include #include #include using namespace std; vector v; int n; int result = INT_MAX; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; vector dp(n + 1, vector(3, 0)); for (int i = 1; i > dp[i][0] >> dp[i][1] >> dp[i][2]; dp[i][0] += min(dp[i - 1][.. 백준/DP 2022. 2. 17. [백준 3055번 / C++] 탈출 bfs 문제이다. #접근방법 1. 고슴도치, 물, 비버의 굴 위치를 저장 후 bfs() 호출 (물과 고슴도치의 위치를 각각 queue에 push) 2. 먼저 물의 위치가 저장된 queue에서 물의 좌표값을 pop 하면서 물이 이동할 수 있는 인접한 구역에 물로 바꾼다. 3. 고슴도치의 위치에서 상하좌우로 갈수 있는 경우 dis라는 배열에 더해나간다. 4. 고슴도치가 더이상 갈 수 있는 길이 없을 때 또는 고슴도치가 비버의 굴 위치에 도달했을 때 리턴 해준다. #include #include #include #include #include using namespace std; int m, n, a_y, a_x; queue w; //물이 차있는 곳 queue q; //고슴도치가 이동할 수 있는 곳 vecto.. 백준/DFS BFS 2022. 2. 17. [백준 13549번 / C++] 숨바꼭질 3 bfs를 문제를 활용해서 풀면 된다. #접근방법 1. 방문 배열 100001개 생성 후 큰 값으로 초기화 2. 수빈이의 현재 위치 queue에 push. 3. queue에 들어간 수빈이의 현재 위치에서 갈 수 있는 경로는 현재 값에서 -1 , +1, *2 이다 현재 위치에서 3가지 방향의 값을 연산하여 해당 인덱스의 visited값을 갱신해간다. 4. queue에 값이 있을 동안 반복문을 돌리며 수빈의 위치와 동생의 위치가 동일하다면 해당 인덱스의 visitied값을 출력하고 종료한다. #include #include #include #include #include using namespace std; int n, k; int visited[100001]; queue q; void bfs() { int .. 백준/DFS BFS 2022. 2. 17. [프로그래머스 Level_2 / C++ / 카카오] 방금그곡 문제를 봤을 때 역시나 카카오는 문자열을 예쁘게(?) 준다. #접근방법 (1) 먼저 m 의 문자열은 12개의 문자열을 나타낸다. 여기서 중요한 점은 'C#' 또한 하나의 음이라는 것이다. 그렇기 때문에 본인은 '#'을 우측에 두고 있는 알파벳에다가 +10 정도를 해주면서 다른 알파벳으로 나타냈다. 즉, 'C' 는 아스키코드로 67 이기 때문에 +10 을 해주면 'M'으로 치환된다. "CC#BCC#BCC#BCC#BCC#B" -> "CMBCMBCMBCMBCMBCMB" (2) 인덱스로 문자열 자르기 문자열을 처리하기 위해서 정말 많이 쓰이는 함수이다. 이 함수는 어떠한 문자열의 특정 인덱스에서 어떠한 인덱스까지 사이의 새로운 문자열을 만들때 보통 사용된다. 예를 들어, "abcdefe" 라는 baebalja... 프로그래머스/Level_2 2022. 2. 17. [백준 2230번 / C++] 수 고르기 투포인터 문제이다. 접근 방법 1. 벡터 오름차순 정렬 및 start, end 포인터 생성 후 0으로 초기화 2. result 값은 벡터 원소중 최솟값과 최댓값의 차이값으로 저장 3. end포인터의 벡터 원소값이 m보다 작으면 end 포인터 증가 4. end포인터의 벡터 원소값이 m보다 크거나 같다면 result 최솟값 갱신 (차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램) #include #include #include using namespace std; int main() { int n, m; cin >> n >> m; vector v(n); for (int i = 0; i > v[i]; sort(v.begin(), v.end()); int s, e; s = 0; .. 백준/증가수열 & 투포인터 2022. 2. 16. 이전 1 ··· 17 18 19 20 21 22 23 ··· 31 다음 반응형