본문 바로가기

Algorithm

 (28)
백준 에디터(1406) C++ 풀이 알고리즘 분류 자료 구조 스택 연결 리스트 문제 해결 아이디어 list와 iterator를 이용하여 list의 기능을 통해 문제를 해결하면 된다. list정리:https://khjtoy.tistory.com/17 초보자를 위한 STL list 정리 1)list란 무엇인가 1-1.list의 존재 이유 초보자를 위한 C++ STL forward_list 정리 1)forward_list 사용 이유 앞서 살펴본 STL array, vector같은 연속된 자료 구조에서는 데이터 중간에 자료를 추가하거나 삭제하 khjtoy.tistory.com iterator(반복자):https://khjtoy.tistory.com/16 초보자를 위한 c++ STL 반복자(iterator) 정리 1)반복자란 무엇인가 앞서 arra..
백준 두 수의 합(3273) C++ 풀이 알고리즘 분류 정렬 두 포인터 문제 해결 아이디어 위 사진에서 알 수 있듯이 arr[L] + arr[R]를 더하여 숫자가 더 크면 작아져야 하므로 R를 왼쪽으로 이동시키고 더 작으면 커져야 하기 때문에 L을 오른쪽으로 이동시킨다. 또한 자기가 설정한 값이 같다면 L은 오른쪽, R은 왼쪽으로 시켜 다른 인덱스의 값이 설정한 값과 같은지 체크하면 된다. 코드 #include #include using namespace std; int n; int arr[100000]; int target; int result = 0; int main() { cin >> n; int left = 0, right = n - 1; for (int i = 0; i > arr[i]; } cin >> t..
백준 방 번호(1475) C++ 풀이 알고리즘 분류 구현 문제 해결 아이디어 0 ~ 8번 인덱스의 값을 넣을 수 있는 배열을 만들고 각 해당되는 숫자 인덱스에 값을 더하고 9는 6번 인덱스에넣는다. 그런 다음 최대값을 구한다. 코드 #include #include using namespace std; int arr[9]; // 0 ~ 8 => 9는 6번째 Index에 넣음 string n; int resultMax = 0; int main() { cin >> n; int num; for (int i = 0; i < n.length(); i++) { num = n[i] - '0'; if (num == 9) num = 6; arr[num]++; } for (int i = 0; i < 9; i++) { int compare = i == 6 ? c..
백준 영역 구하기(2583) C++ 풀이 알고리즘 영역 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 문제 해결 아이디어 연결되어 있는 빈칸의 개수를 DFS를 통해 연결하여 개수를 세어 출력하면 된다. 코드 #include #include #include using namespace std; int m, n, k; int arr[101][101]; // 상하좌우 세팅 int dirX[] = { 0, 0, -1, 1 }; int dirY[] = { -1, 1, 0, 0 }; int cnt = 0; vector result; int dfs(int y, int x) { // 방문처리 arr[y][x] = 1; count +1 증가 cnt++; // 상하좌우 탐색 for (int i = 0; i < 4; i++) { int _y = y + ..
백준 유기농 배추(1012) C++ 풀이 알고리즘 영역 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 문제 해결 아이디어 DFS를 이용하여 붙여있는 1의 개수를 세워 출력하면 됩니다. 위의 사진은 총 5마리의 배추휜지렁이가 필요합니다. 코드 #include using namespace std; int t, m, n, k, cnt = 0; int arr[51][51] = { 0, }; // 상하좌우 세팅 int dirX[] = { -1,1,0,0 }; int dirY[] = { 0,0,-1,1 }; void dfs(int y, int x) { // 0으로 바꾸기(방문처리) arr[y][x] = 0; // 상하좌우 탐색 for (int i = 0; i < 4; i++) { int _y = dirY[i] + y; int _x = dirX[..
백준 미로탐색(2178) C++ 풀이 알고리즘 영역 그래프 이론 그래프 탐색 너비 우선 탐색 문제 해결 아이디어 (0,0)부터 시작하여 BFS를 이용하여 전 거리에 +를 하여 도착지점까지 가면 된다. BFS: 가중치가 같으면 최단 거리를 찾을 수 있다. 코드 #include #include using namespace std; int n, m; int arr[101][101]; //배열 int dist[101][101]; //거리 // 상하좌우 세팅 int dirX[] = { -1,1,0,0 }; int dirY[] = { 0,0,-1,1 }; void bfs(int y, int x) { queue q; //(y,x) q.push(make_pair(y, x)); arr[y][x] = 0; // 방문 처리 dist[y][x] = 1; //거리..
백준 안전 영역(2468) C++ 풀이 알고리즘 영역 그래프 이론 브루트포스 알고리즘 그래프 너비 우선 탐색 깊이 우선 탐색 문제해결 아이디어 잠기는 영역들은 미리 방문 처리를 하고, DFS(깊이 우선 탐색)을 통해 각각의 연결된 영역들을 체크하여 개수를 세면 된다. 코드 #include using namespace std; int n; // 행과 열의 개수 int arr[101][101]; // 비의 양을 저장하는 2차원 배열 bool visited[101][101]; // 방문했는가?를 판단하는 2차원 배열 int maxH = 0; // 입력된 비의 양의 최대 int maxCnt = 0; // 안전한 영역의 최대 개수 int cnt = 0; // 안전한 영역을 세는 변수 // 상하좌우 세팅 int dirX[] = { -1,1,0,0 }; ..
백준 말이 되고픈 원숭이(1600) C++ 풀이 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색(BFS) 문제 해결 아이디어 BFS를 이용하여 K의 값이 0보다 크면 현 위치에서 말의 움직임으로 갈 수 있는 곳을 체크하여 Queue에 넣는다. 그 다음 상하좌우로 갈 수 있는 곳을 체크 한 후 Queue에 넣어, 최종적으로 도착지점에 도달하면 Cost를 출력한다. 코드 #include #include using namespace std; int k; int map[201][201]; bool visited[201][201][31]; int w, h; // 상하좌우 움직임 int dirX[4] = { -1,1,0,0 }; int dirY[4] = { 0,0,-1,1 }; // 말의 움직임 int horseX[8] = { -1,-1,1,1,-2,-2..

티스토리툴바