Category: problems

2018
0
computer sciencealgorithms

백준[1991] - 트리 순회

문제백준 1991 문제 보기 접근 방법순회 시점에 따라 출력하고 재귀함수를 호출하면 정답이 출력된다. 트리의 왼쪽, 오른쪽 노드의 자료 표현을 위해 이치원 배열을 선언하고 [0]에는 왼쪽 노드를 [1]에는 오른쪽 노드를 저장했다. 코드#include <iostream> using namespace std; int N; int tree[26][2]

0
computer sciencealgorithms

백준[2146] - 다리 만들기

문제백준 2146 문제 보기 접근 방법섬을 숫자로 분류해 섬의 갯수를 파악한 뒤 각 섬마다 돌면서 가장 자리를 증가시키는 형식으로 제출했다. 그리고 최소값을 저장한다. 하지만 메모리 초과!!이유는 59번째 주석 처리돼 있듯이 큐에 넣기 전에 방문을 체크해야하는데 큐에서 뺀 뒤 방문 체크가 이루어져 중복된 방문이 발생했다. 코드#include <iostr

0
computer sciencealgorithms

백준[4963] - 섬의 개수

문제백준 4963 문제 보기 접근 방법동서남북과 대각선 방향을 맵의 유효 범위안에서 완전 탐색하면 답을 출력할 수 있다. 코드#include <iostream> #include <cstring> using namespace std; int h, w; int map[50][50]; int visited[50][50]; // 동 북 남 서 i

0
computer sciencealgorithms

백준[2331] - 반복 수열

문제백준 2331 문제 보기 접근 방법최악의 상황으로 메모리를 잡고 연산을 계산해보니 시간 초과는 나지 않을 것 같아 배열을 최대로 잡고 풀었다. 먼저 계속 각 자리를 제곱해 더한 수를 따로 배열에 저장하고 계산 진행하다 추후에 반복된 숫자가 나오면 완전 탐색을 빠져 나간다.dfs함수 안에서 cnt를 세는 건 참고로 안해도 된다. 코드#include <

0
computer sciencealgorithms

백준[1707] - 이분 그래프

문제백준 1707 문제 보기 접근 방법처음 이차 배열을 다 잡아 놓고 시작했다. 그럼 128MB 밖에 안되는 문제 요건을 충족할 수 없어 vector을 활용해 추가될때마다 공간를 만드는 형식으로 변환했다. dfs를 돌며 blue, red로 번갈아가며 색을 배정한다.dfs를 다 돌면 노드 별로 연결된 노드를 확인하며 색이 같은지만 체크하면 된다. 코드#inc

0
computer sciencealgorithms

백준[11724] - 연결 요소의 개수

문제백준 11724 문제 보기 접근 방법dfs로 접근해 거의 리니어한 타임에 문제를 풀수 있다. 그 대신 사이클이 있는 경우를 대비해 방문한 노드를 체크하고 방문했을 경우에는 다시 해당 노드로 접근하지 않는다. 코드#include <iostream> #include <cstring> using namespace std; int N, M;