백트래킹
-
백준 2529번 부등호 :: 마이구미알고리즘 풀이/그래프 2017. 12. 30. 15:58
이 글은 백준 알고리즘 문제 2529번 "부등호" 를 풀이한다.정올 초등부에서 출제된 문제이다.본인은 백트래킹을 활용해서 문제를 해결했다.문제 링크 - https://www.acmicpc.net/problem/2529 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자. A => 부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다. 3 1 7 0이 상황에..
-
백준 14889번 스타트와 링크 :: 마이구미알고리즘 풀이/그래프 2017. 10. 29. 14:42
이 글은 백준 알고리즘 문제 14889번 "스타트와 링크" 를 풀이한다.삼성 SW 역량 테스트의 기출 문제이다.본인은 DFS를 활용해 문제를 해결했다.문제 링크 - https://www.acmicpc.net/problem/14499DFS 참고관련 문제 - http://mygumi.tistory.com/191DFS 이해 - http://mygumi.tistory.com/102 오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 ..
-
백준 14888번 연산자 끼워넣기 :: 마이구미알고리즘 풀이/그래프 2017. 10. 29. 00:12
이 글은 백준 알고리즘 문제 14888번 "연산자 끼워넣기" 를 풀이한다.2017 삼성 SW 역량 테스트의 문제 중 하나이다.본인은 DFS로 문제를 풀이할 것이다.문제 링크 - https://www.acmicpc.net/problem/14499DFS 참고관련 문제 - http://mygumi.tistory.com/191 DFS 이해 - http://mygumi.tistory.com/102 N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)로만 이루어져 있다.우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이 때, 주어진 수의 순서를 ..
-
백준 1941번 소문난 칠공주 :: 마이구미알고리즘 풀이/그래프 2017. 9. 15. 23:52
이 글은 백준 알고리즘 문제 1941번 "소문난 칠공주" 를 풀이한다.기본적인 DFS를 통한 백트래킹을 활용해서는 이 문제를 해결할 수 없다.문제 접근에 있어, 아이디어가 필요한 문제이다.1941번 - https://www.acmicpc.net/problem/1941DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작했다. 곧 모든 여학생이 ‘이다솜파’와 ‘임도연파’의 두 파로 갈라지게 되었으며, 얼마 지나지..
-
백준 2023번 신기한 소수 :: 마이구미알고리즘 풀이/그래프 2017. 9. 15. 22:54
이 글은 백준 알고리즘 2023번 문제 "신기한 소수" 를 풀이한다.백트래킹을 통한 문제 풀이가 된다.백트래킹에 대한 기본적인 이해가 필요하다면, 다음 글을 참고바란다.http://mygumi.tistory.com/1912023번 신기한 소수 - https://www.acmicpc.net/problem/2023DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수 7331이다.7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터..
-
백준 2661번 좋은수열 :: 마이구미알고리즘 풀이/그래프 2017. 9. 9. 21:49
이 글은 백준 알고리즘 문제 2661번 "좋은수열"을 풀이한다.접근 방식은 백트래킹을 활용해 문제를 해결한다.문제 링크는 다음과 같다.https://www.acmicpc.net/problem/2661DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다.다음은 나쁜 수열의 예이다.3332121323123123213다음은 좋은 수열의 예이다.232321231232123길이가 N인 좋은 수열들을 N자리의 정수로 보아 ..
-
백준 1759번 암호 만들기 :: 마이구미알고리즘 풀이/그래프 2017. 9. 9. 15:04
이 글은 백준 알고리즘 문제 1759번 "암호 만들기" 를 풀이한다.접근 방법은 백트래킹을 활용해 문제를 풀이한다.6603번 로또 문제와 흡사하다.조금 응용된 문제로써, 백트래킹을 잘 모른다면 먼저 참고하길 바란다.6603번 로또 - http://mygumi.tistory.com/191문제 링크는 다음과 같다.https://www.acmicpc.net/problem/1759DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보..
-
백준 2580번 스도쿠 :: 마이구미알고리즘 풀이/그래프 2017. 9. 2. 23:47
이 글은 백준 알고리즘 문제 2580번 "스도쿠" 를 풀이한다.일반적으로 알고 있는 스도쿠 문제를 해결하는 과정을 그대로 구현하는 것이다.본인은 스도쿠 문제를 풀어본 적이 없다.그렇기에 스도쿠 관련 알고리즘을 사용한 것이 아닌, 단순히 규칙만을 가지고 접근했다.문제 풀이의 핵심은 백트래킹을 활용한다.참고 링크 - http://www.geeksforgeeks.org/backtracking-set-7-suduku/DFS, BFS - http://mygumi.tistory.com/102백준 문제 - https://www.acmicpc.net/problem/2239 스도쿠 문제를 풀기 위한 일반적인 규칙은 다음과 같다.스도쿠에 대해 굳이 자세히 다루지는 않겠다. 일반적으로 빈칸에 해당하는 가로줄 또는 세로줄 또..