본문 바로가기

Programming/Algorithm 193

swe 보급로 1. bfs 를 해서 계속 돌아가는데, 섬을 가지고 돌아다닙니다. 그런데 만약에 섬을 가지고 돌아다니다가, 이게 하도 돌아서 섬이 커지면 d_map 에 적용되지 않도록 합니다. 2. 그것을 위해서 처음에 d_map 은 엄청 큰 수로 넣어주고, 가지고 다니는 섬끼리 비교를 하도록 해서 작은 섬만 남도록 합니다. 3. 그래서 이것이 끝점까지 도달하면 끝. 가지치기가 그렇게 많이 필요없는 이유는 섬이 조금만 방황해도 엄청 숫자가 커지기 떄문에, 빠르게 감소할 것 입니다. /*1330 시작해서 풀어보도록 하겠습니다.보급로 문제 dp 로 풀어보도록 하겠습니다. */ #include #include #include #include #define SIZE 104 // 102using namespace std; int.. 2018. 3. 27.
백준 1941 소문난 칠공주 1. 연결되어 있는지 확인 하기 위해서 bfs 를 사용합니다.dfs 로는 십자모양을 검사할 수 없기 때문에 7개를 선정하는 과정은 맵이 아닌 단순하게 25C7 을 사용하여 선정합니다. 코드가 if 문이 길어서 시간초과가 나지 않고, 시간복잡도를 풀면 됩니다. /*1. 25시7 조합을 만듭니다.2. 에스가 4 이상인지 확인을 합니다.3. 연결되어 있는지 확인을 합니다. 4. 위의 조건이 맞으면 정답++ 을 합니다. */ #include #include #include #include using namespace std;#define SIZE 5 int map[SIZE][SIZE];int visit[SIZE][SIZE];int check_map[SIZE][SIZE];int x, y, nx, ny;int df.. 2018. 3. 27.
백준 2178 미로 탐색 stl 큐가 아닌 직접 큐를 사용해보기. front, rear 만 인덱스를 사용하면 됩니다.그리고 새로운 bfs 가 들어오면 front, rear 를 초기화하면 됩니다.지금은 bfs 를 한번만 사용해도 되므로 문제가 없습니다. rear 가 들어가는 부분을 끌고 갑니다.그리고 front 가 출력하는 부분을 끌고 나갑니다. 2018. 3. 26.
swe D3 Magnetic 1. 교착상태를 만들기 위해 포문을 사용할 때 주의해야 합니다. 내려가는 것은 아래서부터 검사하고, 올라가는 것을 위에서부터 검사하도록 합니다. 오께이. 2. 그리고 bfs 로 풀어서 교착상태를 세어줄 때는 교착 하는 조건을 정확하게 이해해주어야 합니다. /*1220 Magnetic1416 시작 1445 안에 설계 완료 후 코드 완성하기. 1. n번에 대해서 이동을 시킵니다. 이것은 단순하게 이중 포문 써서 하나씩 이동하도록 하겠습니다. 2. 교착상태의 갯수를 세도록 합니다. 세는 것 또한 열을 기준으로 샙니다. 1이나 2가 있으면, 오케이 하고, bfs 를 아래로만 해서 연속되는 것까지 이동하고, ++ 하나를 해주고, 다시 끝열까지 검사를 해서 또 있으면 ++ 를 해주면 됩니다. 오께이. 여기서는 bf.. 2018. 3. 24.
백준 1981 배열에서 이동 정답 참조 1. 기본 dfs 하면 시간초과가 납니다. 2. 그러므로 다른 방법을 찾아야 하는데, 배열의 각 수가 0~200 사이라는 사실을 알아채고이분탐색과 bfs 를 사용합니다. 3. 방법은 먼저 배열 내에 가장 작은 수와, 가장 큰수를 찾습니다.이것을 이분 탐색하면서 범위를 줄여 나가도록 합니다. 예제를 통해서 보면 0~8 을 잘른 4로 시작합니다.그런데 여기서 큰 for 문 하나를 작성해야 하는데, 이는 가장 작은 수부터, 왜 가장 큰 수까지 조사를 하는 것이지? 가장 작은 수부터, 가장 큰수 - 범위 만큼 l 이 1씩 증가합니다. 이 엘 변수를 사용해서 맵을 구성해줍니다. 갈 수 있는 길과 갈 수 없는 길을 구분합니다. 그리고 bfs 를 통해서 정리된 맵에서 0을 따라서 끝까지 갈 수 있는지 없는지를 판단하.. 2018. 3. 23.
이진 탐색 알고리즘 C++ 1. 이진 탐색을 하기 위해서 필요한 것, 인덱스, 키, 그리고 찾았다 안찾았다. 이런 변수가 필요합니다.정렬이 되어 있어야 합니다. 헤드와 미드가 있고, 미드의 인덱스 데이터가 그 안에 있으면 그 안에 없으면 각각 미드를 수정합니다. 그리고 데이터가 미드와 같으면 키를 출력하면 됩니다. 오께이. 그리고 찾으면 break 를 하도록 합니다. 이전에 배열에서 이동하기 문제를 풀어보도록 하겠습니다. 이것을 응용 하면 되겠습니다. #include using namespace std;void main() {int data[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14 };int n = 14;int index = -1;int key;cin >> key; int head = 0;int tai.. 2018. 3. 23.
백준 1981 배열에서 이동 https://www.acmicpc.net/problem/1981 문제 파악하기. 문제를 정확하게 읽고, 풀이 할 수 있는 다른 방법이 있는지 확인 해보기.그럼 일단 스스로 이분 탐색을 구현해보도록 하겠습니다. 다음에 적용하기 위해서 1. 이분 탐색2. bfs 돌려서 도달 가능한지 확인 해보기. 2018. 3. 23.
백준 2169 로봇 조종하기 디피문제 정답 참조 맵, 디피맵이 있습니다. 일단 맵을 저장해두고, 라인도 하나 저장해두는데, 라인 0에는 라인1에는 무엇을 저장하는가요. 토탈은 변수가 사용안됩니다. 먼저 왼쪽, 오른쪽 위에서 아래로 내려오는 3가지 방향이 있으므로, 이 3가지 내려오는 방향 중에 가장 큰 것을 저장해 나가면 됩니다. 1. 첫줄은 오른쪽으로만 저장해 나갈 수 있으므로, 저장해둡니다.2. 그 다음에 2행부터는 일단 라인 0,1 에 위에서 내려오는 값들을 저장해 둡니다.3. 위, 왼 값을 비교해서 큰 값을 라인 0에 저장을 합니다.4. 위, 오 값을 비교해서 큰 값을 라인 1에 저장을 합니다.5. 라인 0과 1을 비교해서 큰 값을 프리맵에 저장을 하면 됩니다. 마지막 도달하는 점의 값을 출력하면 됩니다. 일단 이렇게 알아두고 넘아가도록 합니다.. 2018. 3. 23.
백준 1018 체스판 다시 칠하기 1. 입력 받는 함수2. 입력받고 8*8 만 검사하는 함수3. 몇개의 수정이 필요한지 검사하는 함수를 만듭니다. 여기서 3번 함수인 검사하는 함수에서, 아이디어는 맵의 인덱스의 합이 짝수인지 홀수인지를 검사하여서 원래 체스판의 색이 아니면 modCnt++ 을 하였습니다. 잘라내는 것에서 지난번에 디스플레이에서 불량 화소가 얼마나 나오는지를 알아내는 문제에서 짜 본 적이 있기에 시간을 벌고, 자신감 있게 해결할 수 있었습니다. 풀이 시간 30분 입니다. /*2001 체스판 다시 칠하기 시작.검은색, 흰색, 8 곱 8 체스판으로 만들고 싶다.잘라낸 후에 몇 개의 정사각형을 다시 칠하기. 칠해야 하는 보드의 최솟값을 구하는 프로그램을 작성하세요.체스판은 2 종류 입니다. 1. 입력 받는 함수2. 입력받고, 8.. 2018. 3. 22.
백준 3085 사탕 게임 처음 설계를 할때, 명확하고, 이것이 제대로 돌아가는지, 예외는 없는지까지 고려해야 합니다. 이 문제를 푸는 방법으로는 1. 인접한 사탕을 선택하고, swap 하는 함수2. swap 을 한 후에 가로로, 세로로 연속된 사탕이 몇개 있는지 검사하는 함수 이렇게 2개의 함수로 나누어서 풀이하면 됩니다. /*1908 사탕게임1. 사탕을 교환하는 함수 -> 하나씩 이동하는데, 일단 가로로 인접한 것 2개를 교환, 하는 i,j 그리고 i,j를 이동하는데 아래랑 교환하는 것 이렇게 짜도록 하겠습니다. 조사가 끝나면 다시 i,j 를 그대로 변경해주도록 하겠습니다. 2. 교환한 맵에서 가로, 세로로 같은 것이 가장 긴 맵 찾으면 됩니다. bfs 가 아니라, for 문으로 풀면 되겠습니다. */ #include #inc.. 2018. 3. 22.

티스토리툴바