[목차]310

• [백준 1189번 / C++] 컴백홈 dfs를 활용해서 완전 탐색으로 풀면 된다. 1. dfs 기본 문법을 활용해서 상 하 좌 우에 조건에 부합되면 들어간다. 2. 집의 좌표값과 일치하고 좌표값까지의 distance가 K와 일치하면 cnt+1을 해준다. 3. 재귀 처리후 돌아오면 visited 배열을 0으로 세팅한다. (다른 방향으로 가는 루트도 체크 해줘야하기 때문에 초기화) #include using namespace std; int dx[4] = { 0,0,-1,1 }; int dy[4] = { 1,-1,0,0 }; int m, n, k; int map[5][5]; int visited[5][5]; int cnt; void dfs(int y, int x, int dis) { if (x == n - 1 && y == 0&&dis==k) .. 백준/완전 탐색 2022. 1. 25.

• 

  [백준 2667번 / C++] 단지번호붙이기 bfs, dfs 자신있는 것으로 해보자. main문에서 함수 호출할 때 증가하는 cnt는 영역을 표현. 함수에서 또 함수를 호출할 때 증가하는 cnt는 영역안의 넓이를 표현. #include #include #include #include using namespace std; int n; int dx[4] = { 0,0,1,-1 }; int dy[4] = { 1,-1,0,0 }; int map[25][25]; int visited[25][25]; int cnt1; void dfs(int y, int x) { cnt1++; for (int i = 0; i = n || ny < 0 |.. 백준/DFS BFS 2022. 1. 24.

• 

  [백준 10026번 / C++] 적록색약 bfs 문제로 풀면 쉽게 나온다. 1. map 에 RGB 색상에 맞게 숫자로 저장. (그대로 해도 상관없음. 저는 보통 숫자로 합니다.) 2. 반복문을 돌면서 해당 위치가 방문되지 않았다면 bfs() 함수를 호출 한다. 3. bfs 기본적인 알고리즘을 사용해 동일한 색상에 인접한 구간들을 다 방문 처리한다. 4. 메인문에서 bfs 호출된 개수를 출력 ( 첫번째 답안 ) 5. map 에서 R과 G를 동일한 번호로 저장. 6. 2~4 번과 동일. #include #include #include #include #include #include using namespace std; int dx[4] = { 0,0,1,-1 }; int dy[4] = { 1,-1,0,0 }; int n; int map[100][1.. 백준/DFS BFS 2022. 1. 24.

• [백준 3986번 / C++] 좋은 단어 stack을 활용한 문제이다. 아치형 곡선이 겹치지 않는다는 말이 스택의 최상단 value값과 현재 문자 값이 일치하면 지워주는것을 반복했을 때 스택에 남는 문자가 없다는 뜻이다. #include #include using namespace std; int main() { int n; cin >> n; int result = 0; for (int i = 0; i > ss; for (auto c : ss) { if (s.size() && c == s.top())s.pop(); else s.push(c); } if (s.empty())result++; } cout 백준/구현 2022. 1. 24.

• 

  [Level_2 / C++ / 카카오] 문자열 압축 이 문제의 핵심은 문자열의 절반만 확인하면 된다는 것이다. 첫번째 예제에서 크기가 8인 문자열이 주어졌다면 1부터 4사이즈만큼만 반복문을 돌리면된다. 즉, 사이즈가 1~4인 문자열을 돌아보면서 같으면 cnt값을 증가하고 다르면 이전에 증가시켰던 cnt값을 스트링으로 바꾸고 비교해왔던 문자열을 뒤에 붙인다. 그리고 비교해왔던 문자열을 현재 자른 문자열로 교체한다. * 파라미터 값으로 받아온 문자열이 사이즈가 1이였다면 바로 return 1을 해준다. #include #include #include #include #include using namespace std; int solution(string s) { int answer = INT_MAX; if(s.size()==1)return 1; for(int.. 프로그래머스/Level_2 2022. 1. 24.

• 

  [Level_2 / C++ / 카카오] [1차] 캐시 1. cacheSize 가 0이면 return 도시의 개수 X 5 2. 문자열 대문자로 변환 (소문자, 대문자 구분하지 않는다) 3. map 생성하여 제일 작은 cnt값을 갖는 key 문자열 저장 4. (주의) hit를 해도 cnt 값 갱신 5. 제일 작은 cnt값을 갖는 key 문자열에 해당하는 map을 지우고 새로운 값 추가 #include #include #include #include #include #include using namespace std; int solution(int cacheSize, vector cities) { int answer = 0; map m; int cnt =1; if(cacheSize==0)return cities.size()*5; for(int i=0; i 프로그래머스/Level_2 2022. 1. 24.

• 

  [Level_1 / C++ / 카카오] [1차] 다트 게임 아이유를 정말 좋아하기 때문에 이 문제는 꼭 풀려고 마음 먹었다. 이 문제는 하라는대로 풀면 된다. 코드를 봐도 쉽게 이해할 수 있을거라고 생각한다. 다만, 저와 똑같은 실수를 하시는 분도 계실까봐 말씀드리지만, 스타상(*)은 해당 점수와 바로 전에 얻은 점수를 2배하는 것이지, 이전에 얻은 모든 점수에 2배를 하는것이 아니다! #include #include using namespace std; int solution(string dartResult) { int answer = 0; string s= dartResult; vector v; string s1=""; for(int i=0; i='0'&&s[i] 프로그래머스/Level_1 2022. 1. 23.

• 

  [Level_1 / C++ / 카카오] 실패율 map을 활용하여 해당 스테이지와 그 스테이지를 밟고 있는 친구들의 수를 key, value값으로 지정하자. N만큼 반복문을 돌면서 map의 해당 스테이지의 value값을 "스테이지 사이즈 - 넘지못한 친구들의 수" 로 나눠주어 그 몫을 벡터에 저장한다. (넘지못한 친구들의 수 = prev변수로 할당 ) 벡터를 실패율의 내림차순으로 정렬하여 출력하도록 한다. #include #include #include #include #include using namespace std; bool cmp (pair v1, pair v2){ if(v1.second==v2.second)return v1.first v2.second; } vector solut.. 프로그래머스/Level_1 2022. 1. 23.

• 

  [Level_1 / C++ / 카카오] [1차] 비밀지도 다음 그림을 봤을 때 or 연산자가 떠오른다. 그림 옆에 이진수로도 힌트를 주는거 같다. 즉, '#' 문자는 '1' 을 나타내고 공백은 '0'을 나타낸다. 각 벡터의 정수값을 or 연산을 해주면 맨 밑의 그림과 같이 표현할 수 있다. 결과 그림과 같이 표현하기 위해서는 or연산을 통해 나온 결과값들은 각 행을 표현하는 정수값이며 그 정수값을 2로 계속 나눠주면서 나머지값이 1이라면 '#'를 붙여주고 아니라면 공백을 출력한다. #include #include #include using namespace std; vector solution(int n, vector arr1, vector arr2) { vector answer; for(int i=0; i 프로그래머스/Level_1 2022. 1. 23.

• 

  [Level_1 / C++ / 카카오] 신고 결과 받기 자료구조 중복제거를 하기위해 쓰이는 자료구조이다. 많이 쓰이는 자료구조는 아니지만 문제에서 모든값의 중복을 없애고 오름차순으로 정렬하라는 문제가 나온다면 사용할 수 있다. 헤더로 set을 갖고 s baebalja.tistory.com 공백으로 문자열 자르기 문자열이 공백이 주어진 상태로 주어진다면 공백을 기준으로 문자열을 자를 수 있다. 예) string s = "abc def gh" ; 해당 문자열을 "abc" , "def" , "gh" 로 자르는 거다. 해당 문법을 알아보자. #include #inclu.. baebalja.tistory.com s1>>s2; m[s2].insert(s1); ss.clear(); } for(auto it : m){ if(it.second.size()>=k){ for(a.. 프로그래머스/Level_1 2022. 1. 23.