본문 바로가기
728x90
반응형

Algorithm

 (66)
[ 백준 / 2580 ] 스도쿠 ( 자바 ) www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 기본적으로 알고 있는 스도쿠의 룰과 완전 똑같다. 게다가 정답이 없는 경우는 주어지지 않는다니, 첫번째로 정답이 나오는 것을 출력하고 종료하면 된다. (0,0)부터 (N,N)까지 계속 DFS로 들어간다. 그 이후, 가로, 세로, 9칸의 정사각형 3개에 대해서 어떤 숫자가 들어갈 수 있는지 검사한다. 이것을 Set에 담는다. Set에 담긴 값들을 하나씩 대입해 보면서 가로, 세로, 9칸의 정사각형에 모두 만족하는..
[ 백준 / 10971 ] 외판원 순회 2 ( 자바 ) www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net DFS의 문제이다. DFS이므로 backtracking에 신경쓰도록 한다. 전형적인 느낌으로 모든 지점을 방문하면서 지나간다. 무엇을 backtracking에 넣을 것인가? 각 방문했던 지점을 visited로 구분하는 것을 넣어준다. 이 부분만 신경써주면 된다. sum은 매개변수에서 처리하기 때문에 따로 신경쓰지 않는다. 단, 중간에 거리가 0인 부분은 이동이 불가하..
[ 백준 / 1009 ] 분산처리 ( 자바 ) www.acmicpc.net/problem/1009 1009번: 분산처리 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000) www.acmicpc.net a^b에 속아서 제곱의 수에만 신경을 써서는 안된다. 이 문제는 결국 최종 값의 일의 자리가 무엇인지가 궁금한 문제이다. 이런식으로 문제에서 요구사항을 감추는 일이 종종 있다. 문제를 읽고 어떤 방식으로 풀어야 하는지 조금 더 생각해보고 여러가지 방안을 마련해두자! //1009 분산처리 import java.util.*; public class Main { static List list = new ArrayList(); ..
[ 백준 / 1977 ] 완전제곱수 ( 자바 ) www.acmicpc.net/problem/1977 1977번: 완전제곱수 M과 N이 주어질 때 M이상 N이하의 자연수 중 완전제곱수인 것을 모두 골라 그 합을 구하고 그 중 최솟값을 찾는 프로그램을 작성하시오. 예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 완 www.acmicpc.net 케이스에 포함되는 모든 문자에 대해서 Math.pow()를 이용하면 쉽게 풀 수 있다.잊지말자, 제곱의 값은 Math.pow()! //1977 완전제곱수 import java.util.*; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Sc..
[ 백준 / 1032 ] 명령 프롬프트 ( 자바 ) www.acmicpc.net/problem/1032 1032번: 명령 프롬프트 첫째 줄에 파일 이름의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 파일 이름이 주어진다. N은 50보다 작거나 같은 자연수이고 파일 이름의 길이는 모두 같고 길이는 최대 50이다. 파일이름은 www.acmicpc.net 공통적인 알파벳은 적어주고 그렇지 않은 위치는 ?로 적어주면 된다. 한 문자열씩 모두 비교하면서 만들었다. //1032 명령 프롬프트 import java.util.*; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); ..
[ 백준 / 13460 ] 구슬 탈출 2 ( 자바 ) www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 정답률 25.549%의 쉽지 않는 구현 문제였다. 다른 풀이는 생각보다 길이가 짧지만 나는 굉장히 긴 코드가 나왔다. 아무래도 효율적인 방법은 아닌 것 같다. 나는 모든 케이스를 검사하여 빨간구슬과 파란구슬을 옮겼으며 DFS, 백트래킹을 사용하였다. 나름 각 순서에 대해서 메소드를 구분하여서 만들었다. 상->하, 하->상, 좌->우, 우->좌로 이동을 하지 못하..
[ 백준 / 2108 ] 통계학 ( 자바 ) www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 산술평균 , 중앙값, 최빈값, 최대값과 최소값의 차이 를 구하는 문제이다. *산술평균 - Math.round() 를 사용했다. 이것은 소수점 첫째자리에서 반올림하여 숫자를 만들어준다. 이와 같은 방법으로 소수점 첫째자리까지, 둘째자리까지 등등으로 만들 수 있다. Math.round(sum) : 소수점 첫째자리에서 반올림 Math.round(sum*10/10.0) : 소수점 둘째자리에서 반올림 Math.round(sum*100/100.0) : 소수..
[ 백준 / 1100 ] 하얀 칸 ( 자바 ) www.acmicpc.net/problem/1100 1100번: 하얀 칸 체스판은 8*8크기이고, 검정 칸과 하얀 칸이 번갈아가면서 색칠되어 있다. 가장 왼쪽 위칸 (0,0)은 하얀색이다. 체스판의 상태가 주어졌을 때, 하얀 칸 위에 말이 몇 개 있는지 출력하는 프로그램 www.acmicpc.net 구현문제이자 엄청나게 쉬어가는 편한 문제였다. package bj; import java.util.*; import java.io.*; //1100 하얀 칸 public class Main { public static void main(String[] args) throws IOException { // TODO Auto-generated method stub BufferedReader br = new Buf..
728x90
반응형

티스토리툴바