팡스블로그 팡스블로그

알고리즘

• [백준 1759] - [백트래킹] - 암호 만들기 (JAVA)

  알고리즘/백트래킹 2018. 12. 26. 15:19

  문제 링크 : https://www.acmicpc.net/problem/1759 이 문제는 백트래킹으로 쉽게 접근 할 수 있다. 이전에 풀었던 백트래킹 문제들을 하나씩 풀어본다면 아주 쉽게 코드를 작성 할 수 있다. 모든 경우에 수를 전부 탐색하면서 문제에서 제시한 3가지 조건을 만족 시키는 경우 생성된 암호를 출력 해주고 다시 다른 경우의 수를 탐색하면 된다. 이전에 풀었던 백트래킹 문제를 기억해가면서 풀어보니 정말 쉽게 문제를 풀 수 있었다. 만약 기억이 안난다면 다른 백트래킹 문제를 풀어보면서 접근해보면 좋을듯 하다. 백트래킹 관련 글 2018/11/21 - [알고리즘/백트래킹] - [백준-9663]-[백트래킹] - N-Queen2018/11/23 - [알고리즘/백트래킹] - [백준-1987]-[D..

  Read More
• [백준 6603] - [백트래킹] - 로또 (JAVA)

  알고리즘/백트래킹 2018. 12. 26. 14:08

  문제 링크 : https://www.acmicpc.net/problem/6603 이 문제는 백트래킹으로 접근 하면 되는 문제다. 백트래킹은 모든 경우의 수를 탐색을 진행 할때 탐색을 한 후에 다시 값을 탐색하기 이전으로 되돌리는 형태의 알고리즘 이다. 이 문제는 그럼 어떻게 접근을 해야 할까? 주어진 k 개의 원소 중에서 하나씩 뽑아서 로또 번호를 생성하면 된다. 한번 로또 번호에 사용된 원소는 다시 사용 될 수 없기 때문에 i 번째 원소가 로또 번호로 생성 됐다면 그 다음 로또번호는 i+1 부터 k-1 번 째 원소가 될 수 있다. 예를 들어 k 는 7 이고 원소들의 집합으로 {1, 2, 3, 4, 5, 6, 7} 을 입력 받은 상태에서 { 1, 2, 3} 까지 로또 번호를 생성 했다면 그 다음 로또 번..

  Read More
• [백준 2580] - [백트래킹] - 스도쿠

  알고리즘/백트래킹 2018. 12. 21. 17:58

  문제링크 : https://www.acmicpc.net/problem/2580 이문제는 백트래킹으로 접근 할 수 있는 문제이다. 예전에 풀었던 N-Queen 문제도 백트래킹이었는데 간단하게 설명하자면 현재 인덱스에 값을 넣어보고 다음 탐색을 돌린다. 다시 현재 인덱스에는 값을 초기화 시킨다. arr[y][x] = i; backtracking(idx+1, cnt+1); arr[y][x] = 0; 위에 소스처럼 백트래킹을 진행하는데 이렇게 하면 결국엔 다 초기화 되는거 아냐?? 하겠지만 잘 생각해보면 그렇지 않다. 최종 arr의 값은 당연히 초기 탐색할때의 값이 되겠지만 탐색을 하는 도중에 맞는 결과가 나왔을거고 맞는 결과가 나왔을때 배열을 바로 출력을 했다. 이해가 안된다면 백트래킹에 대한 설명 N-Que..

  Read More
• [백준 5427] - [BFS 최단거리] - 불 (JAVA)

  알고리즘/BFS_DFS 2018. 12. 20. 13:57

  문제링크 : https://www.acmicpc.net/problem/5427 이 문제는 BFS를 가지고 풀면 되는데 좌표정보를 갖는 queue를 2개를 사용해야 한다. queue1은 불의 좌표를 저장하는 queue로 사용하고queue2는 사람의 좌표를 저장하는 queue로 사용한다. 입력 값이 숫자가 아닌 # * . @ 형식의 char 타입 데이터 이기 떄문에 나는 이 char를 custom 해서 int 형의 값으로 변경했다. # --> -1* --> -2. --> 0@ --> 1 방문 정보를 저장할 visited 배열을 사용하기 싫어서 빈 공간은 0으로 두고 사람이 움직일때 좌표의 값이 0인 위치만 이동하게 소스를 작성했다. 복잡하다면 char형의 이차원 배열과 visited 배열을 두개 생성하고 문..

  Read More
• [백준 1697] - [bfs] - 숨바꼭질

  알고리즘/BFS_DFS 2018. 12. 19. 21:06

  문제 링크 : https://www.acmicpc.net/problem/1697 이 문제 힌트에 백트래킹으로 돼 있어서 백트래킹으로 풀었다가 후회하고 제일 간단한 단순 bfs로 풀었다. 분명 백트래킹으로 풀 수 있는 문제긴 하다. 하지만 쉽게 풀 수 있는 방식이 있었기에 이번에는 쉬운 방식으로 풀려고 한다. 간단하게 생각해서 1회전에 방문하는 위치 는 n-1, n+1, n*2가 되고 i번 만큼 반복하면서 목표 위치에도달했을때의 반복 횟수를 리턴해주면 된다. 소스123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051import java.util.LinkedList;import java.util...

  Read More
• [백준 1012] - [dfs] - 유기농 배추 (JAVA)

  알고리즘/BFS_DFS 2018. 12. 19. 17:00

  문제 링크 : https://www.acmicpc.net/problem/1012 이 문제는 DFS 간단하게 풀 수 있는 문제이다. 다만 주의해야 할 부분이 있는데 제한시간은 1초인데 여러개의 테스트 케이스가 주어지니 제한시간내에 모든 테스트 게이스를 풀기 위해선 불필요한 좌표까지 dfs로 접근할 필요가 없다. 배추의 좌표를 정수형 배열 타입의 큐에 저장한다. 모든 입력이 완료되고 queue가 빌때까지 queue에서 하나씩 추출해가면서 dfs를 돌린다. queue에 있는 좌표는 부조건 배추가 심어저 있는 좌표이다. 추출된 좌표가 이전에 방문한 이력이 없는 경우만 dfs 탐색을 한다. 위에 나열한 순서와 조건으로 DFS 탐색을 시도하면 문제는 아주 쉽게 풀린다. 모든 좌표에 방문여부와 배추가 심어진 좌표인지..

  Read More
• [백준 11050] - [수학] - 이항계수 1 (Java)

  알고리즘/수학 2018. 12. 14. 17:12

  문제 링크 : https://www.acmicpc.net/problem/11050 이문제는 간단한 조합 문제이다. 입력받는 형식을 식으로 풀이하면 아래와 같이 나온다. 이 문제는 제일 간단한 문제이기때문에 그냥 각 수 별로 {n!, k!, (n-k)! } 팩토리얼 을 구한다음 계산하면 된다. 소스 1234567891011121314151617181920212223242526import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int K = sc.nextInt(); int a = getFactorial..

  Read More
• [백준 15954] - [카카오 코드 페스티벌 2018 예선] - 인형들 (JAVA)

  알고리즘/카카오 코드 페스티벌예선 2018 2018. 12. 4. 17:20

  문제 링크 : https://www.acmicpc.net/problem/15954 이문제는 음 .. 문제를 이해하는데 어렵지는 않았다. 다만 문제를 제대로 읽지 않아 한번 틀렸다. 그러면서 시간을 30분 정도 더 버린거 같다. 알고리즘 문제는 대부분 이렇게 시간을 허비하는거 같다. 카카오프렌즈 스토어를 관리하는 브라이언은 어떠한 특정한 곳에 인형들을 배치하고자 하는데, 그곳에 인형들을 선택하는 방법은 다음과 같다:먼저 비슷한 인형이 가깝게 위치하도록 서로 다른 N개의 인형을 종류당 한 개씩 일렬로 배치한다.그 후, 선호하는 사람의 수의 표준편차가 최소가 되는, K개 이상의 연속된 위치에 있는 인형들을 선택하여 그들을 같은 곳에 배치한다.위의 방법으로 인형들을 선택했을 때, 선택된 인형들의 선호하는 사람의..

  Read More