본문 바로가기

Algorithm

 (389)
[백준] 1138_한줄로서기 / 그리디알고리즘, 그리디란? Sliver  문제 N명의 사람들은 매일 아침 한 줄로 선다. 이 사람들은 자리를 마음대로 서지 못하고 오민식의 지시대로 선다.어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다. 그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다.사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다.각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 출력하는 프로그램을 작성하시오.  입력 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수..
[백준] 1212 8진수 2진수 Bronze  문제 8진수가 주어졌을 때, 2진수로 변환하는 프로그램을 작성하시오.  입력 첫째 줄에 8진수가 주어진다. 주어지는 수의 길이는 333,334을 넘지 않는다.  출력 첫째 줄에 주어진 수를 2진수로 변환하여 출력한다. 수가 0인 경우를 제외하고는 반드시 1로 시작해야 한다.   풀이 import java.util.*;class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String oct = sc.nextLine(); // 0부터 7까지의 8진수를 대응하는 3비트 2진수 문자열 String[] binary = {..
[백준] 나머지합 / 누적합 Glod  문제 수 N개 A1, A2, ..., AN이 주어진다.이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.  입력 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109)  출력 첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.   풀이 import java.util.*;import java.io.*;class Main { public static void main(String[] arg..
[백준] 2580_스토쿠 / 백트래킹, DFS Gold  문제 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.  나머지 빈 칸을 채우는 방식은 다음과 같다.각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.  또한 위쪽 가운데 위치한 3x3 정..
[백준] 1835_카드 / 덱 deque Sliver  문제 1부터 N까지의 숫자가 적힌 카드가 있다. 찬유는 이 카드를 가지고 마술을 하려 한다.마술을 하는 순서는 다음과 같다.먼저 1부터 N까지의 숫자가 적힌 카드에서 첫 번째 카드를 가장 뒤로 옮긴다. 그러고 나서 첫 번째 카드를 책상 위에 올려놓는다. 그런데 그 카드는 1이 되어야 한다.그리고 남은 카드 중에서 첫 번째 카드를 가장 뒤로 옮기고, 또 가장 앞에 있는 카드를 가장 뒤로 옮긴다.(2번 반복) 그리고 가장 앞에 있는 카드를 책상 위에 올려놓는다. 그런데 그 카드는 2가 되어야 한다.또 남은 카드 중에서 첫 번째 카드를 가장 뒤로 옮기고... (3번 반복) 그리고 가장 앞에 있는 카드를 책상위에 올려놓는데 그것은 3이 된다.또 남은 카드 중에서 첫 번째 카드를 가장 뒤로 옮기고...
[백준] 1816_암호키 / 큰 소수, 6k ± 1 Bronze  문제 현대 사회에서 통용되고 있는 많은 종류의 암호 시스템에서는, 매우 큰 소수의 곱으로 만들어진 수를 암호 키로 이용하는 경우가 많다.현실적으로 매우 큰 수를 빠른 시간 내에 소인수분해하는 것은 어려운 일이기 때문이다.물론 실제 생활에서는 수십만 또는 수백만 자리 이상의 매우 큰 소수가 활용되지만 그러한 소수를 구하는 것은 매우 어려운 일이므로, 우리는 좀 더 스케일이 작은 경우에 대해서만 생각해 보기로 하자. 1,000,000=10^6보다 큰 소수이면 매우 큰 소수로 생각하는 것이다. 어떤 수 S가 주어지면, 이 수가 우리가 생각하는 스케일이 작은 경우에서 적절한 암호 키인지 아닌지를 구하는 프로그램을 작성하시오.만일 S의 모든 소인수가 106보다 크다면 그 수는 적절한 암호 키이고, ..
[백준] 1526_가장큰금민수 / DFS 조합 Bronze  문제 은민이는 4와 7을 좋아하고, 나머지 숫자는 싫어한다.금민수는 어떤 수가 4와 7로만 이루어진 수를 말한다.N이 주어졌을 때, N보다 작거나 같은 금민수 중 가장 큰 것을 출력하는 프로그램을 작성하시오.  입력 첫째 줄에 N이 주어진다. N은 4보다 크거나 같고 1,000,000보다 작거나 같은 자연수이다.  출력 첫째 줄에 N보다 작거나 같은 금민수 중 가장 큰 것을 출력한다.    풀이 import java.util.*;class Main { static ArrayList list; // 금민수를 저장할 리슽트 static int n; // 입력값 // DFS 재귀적으로 금민수를 생성 public static void dfs(int num){ ..
[백준] 1072_게임 / 이분탐색 Sliver  문제 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다.누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시작했다.의심을 피했다고 생각한 형택이는 다시 게임을 켰다. 그 때 형택이는 잠시 코딩을 하는 사이에 자신의 게임 실력이 눈에 띄게 향상된 것을 알았다.이제 형택이는 앞으로의 모든 게임에서 지지 않는다. 하지만, 형택이는 게임 기록을 삭제 할 수 없기 때문에, 자신의 못하던 예전 기록이 현재 자신의 엄청난 실력을 증명하지 못한다고 생각했다.게임 기록은 다음과 같이 생겼다.게임 횟수 : X이긴 게임 : Y (Z%)Z는 형택이의 승률이고, 소수점은 버린다. 예를 들어, X=53, Y=47이..

티스토리툴바