류호석님의 알고리즘 github 강의커리큘럼과 최백준님의 코딩테스트 준비 기초 커리큘럼을 따라 작성한 문서입니다!
중간중간 참고한 블로그/강의는 해당 자료 아래에 출처를 남기도록 하겠습니다!
풀이는 java를 사용하여 작성했습니다.
백준 2309 : 일곱 난쟁이
재귀를 이용한 조합방법으로 문제를 풀었다.
import java.util.*;
public class Main {
public static Scanner scanner=new Scanner(System.in);
public static StringBuilder sb=new StringBuilder();
static int n,m;
static int arr[];
static int ans[];
static int choice=0;
static int sum=0;
public static void main(String[] args) {
arr=new int[9];
ans=new int[7];
for(int i=0;i<9;i++) {
arr[i]=scanner.nextInt();
}
solve(0,0,0,0);
}
static boolean flag =false;
public static void solve(int pos,int sum, int choice, int cnt) {
//pos: 9명의 난쟁이의 키가 들어있는 배열에서의 현재위치
//sum: 선택한 난쟁이 키의 합
//choice :선택 유무 1:true 0:false
//cnt : 지금까지 선택한 난쟁이 개수
//ans[] : 키의 합이 100인 난쟁이들의 모임이 될 배열
if(flag)return;
if(choice!=0) //선택됐으면 ans에 해당 pos의 난쟁이 추가
{
ans[cnt-1]=arr[pos-1];
}
if(cnt==7) //선택한 난쟁이가 7명이거나 9까지 다 돌았을때 base case
{
if(sum==100)//sum이 100이면 정답
{
Arrays.sort(ans);
for(int i=0;i<7;i++) {
System.out.println(ans[i]);
}
flag=true;
}
//아니면 리턴
return;
}
if(pos==9) {
return;
}
solve(pos+1,sum+=arr[pos],1,cnt+1);// pos+1 번째 원소를 픽
sum-=arr[pos];
solve(pos+1,sum,0,cnt); //픽안함
}
}실수 point
한 가지의 결과만을 출력해야했는데 재귀에서 아예 빠져나올 방법을 몰랐었다. 그래서 서칭 끝에 flag를 true로 설정하고 매번 if문으로 검사하는 방법을 사용했다.
두번째로 문제에 제시된 테스트케이스는 통과했으나 반례인 99 100 1 2 3 4 5 6 79를 통과 하지 못했다 이유는 100인지 검사하는 if문에서 pos가 9인경우도 or로 같이 확인을 했는데 그럼 100만 선택되고 pos만 확인되기 때문에 틀린결과가 나온것이다 ㅠㅠ 알고리즘 오픈카톡방의 백준 실1님께 도움을 받았다 감사합니다 !!'
복습
다시 풀어봤을때도 틀림
<반례>
13
11
9
7
17
19
21
23
10
이 예제를 넣었을 때 한개만 출력해야하는데 가능한 답이 전부 출력된다
두번이상 출력되지않게해야한다.
백준 3085 : 사탕게임
import java.util.*;
public class Main {
public static Scanner scanner=new Scanner(System.in);
public static StringBuilder sb=new StringBuilder();
static int n,m;
static char arr[][];
static int ans;
static int max=0,max2=0,MAX=0;
public static void main(String[] args) {
n=scanner.nextInt();
arr=new char[n][n];
for(int i=0; i<n; i++) {
String str = scanner.next();
for(int j=0; j<n; j++) {
arr[i][j] = str.charAt(j);
}
}
solve();
System.out.print(max);
}
public static void solve() { // 1. 가로를 바꾸고비교 한다. max를 구한다 2. 세로를 비교한다. max를 구한다.
//max : 사탕의 최대 개수
char tmp ;
for(int j=0;j<n;j++) { //행
for(int i=0;i<n-1;i++) { //열
//자리교체
tmp=arr[j][i];
arr[j][i]=arr[j][i+1];
arr[j][i+1]=tmp;
count();
//원상복구
tmp=arr[j][i];
arr[j][i]=arr[j][i+1];
arr[j][i+1]=tmp;
}
}
for(int j=0;j<n;j++) { //열
for(int i=0;i<n-1;i++) { //행
tmp=arr[i][j];
arr[i][j]=arr[i+1][j];
arr[i+1][j]=tmp;
count();
//원상복구
tmp=arr[i][j];
arr[i][j]=arr[i+1][j];
arr[i+1][j]=tmp;
}
}
return ;
}
public static void count() {
//가로 세기
for(int m=0;m<n;m++) {
int cnt=1;
for(int k=0;k<n-1;k++) {
if(arr[m][k]==arr[m][k+1]) {
cnt++;
}
else {
cnt=1;
}
max=Math.max(max, cnt);
}
}
//세로 세기
for(int m=0;m<n;m++) {
int cnt=1;
for(int k=0;k<n-1;k++) {
if(arr[k][m]==arr[k+1][m]) {
cnt++;
}
else {
cnt=1;
}
max=Math.max(max, cnt);
}
}
return;
}
}일단 엄청난 for문들로 문제를 풀었는데 풀면서도 이게 맞나 시간초과 안나려나 걱정했는데 성공은 했다.
실수 point
평소처럼 입력이 space로 구분되어 있을줄알았는데 연속된 문자였다.
scanner에는 char를 받는게 따로없기때문에 string으로 받은 후 charAt으로 입력해줘야 했다.
그리고 for문이 하도 여러개다보니까 알고리즘을 다짜도 수정하다가 범위가 어긋나버려서 index오류로 시간을 아주 많이 버렸다 ㅠ omg
백준 1476 : 날짜 계산
import java.util.*;
public class Main {
public static Scanner scan =new Scanner(System.in);
static int e,s,m,ans;
public static void main(String[] args) {
e=scan.nextInt();
s=scan.nextInt();
m=scan.nextInt();
if(e==15) {
e=0;
}
if(s==28) {
s=0;
}
if(m==19) {
m=0;
}
solve();
System.out.print(ans);
}
public static void solve() {
int n=1;
while(true) {
if(n%15==e&&n%28==s&&n%19==m) {
ans=n;
break;
}
n+=1;
}
}
}당연히 시간초과 날것같았는데 성공했다
실수 point
15 28 19 일때 나머지가 0이 되기 때문에 예외처리가 필요했다~
백준 6064 : 카잉 달력
import java.util.*;
public class Main {
public static Scanner scan =new Scanner(System.in);
public static StringBuilder sb=new StringBuilder();
static int t, n,x,y, m,arr[][],ans;
static int k=0;
static int tmp=0,tmp2=0;
static int flag;
public static void main(String[] args) {
t=scan.nextInt();
for(int i=0;i<t;i++) {
m=scan.nextInt();
n=scan.nextInt();
x=scan.nextInt();
y=scan.nextInt();
solve(m,n,x,y);
System.out.println(ans);
}
}
public static void solve(int m,int n, int x,int y) {
if(x==m) {
x=0;
}
if(y==n) {
y=0;
}
for(int i=x;i<m*n;i+=m) {
if(i%n==y) {
ans=i;
return;
}
}
ans=-1;
}
}날짜 계산과 유사한 문제다. 근데 1부터 다 넣었을 때 시간초과가 뜨기때문에 i가 x부터 시작해서 m을 더해주는 식으로 늘려가서 i%n만 체크를 해줬다.
백준 1748 :수이어쓰기1
import java.util.*;
public class Main {
public static Scanner scan =new Scanner(System.in);
public static StringBuilder sb=new StringBuilder();
static String t;
static int k=0;
static int cnt=0,tmp2=0;
static int flag;
public static void main(String[] args) {
t=scan.next();
k=t.length(); //몇자리 수인지
for(int a=0;a<k-1;a++) { //0: 1의자리수 n-1: n의 자리수
cnt+=(a+1)*9*Math.pow(10, a);
}
cnt+=k*(Integer.parseInt(t)-(Math.pow(10, k-1)-1));
System.out.println(cnt);
}
}처음으로 1트에 통과한듯 ㅠㅠㅠㅠㅠ String형으로 받은후 몇자리 수 인지 세리고
자리수 910의 자리수승 해서 세리고 최상위 자리수는 따로 계산해줬다!
Math.pow 까먹어서 다시 찾아봄 ㅎㅎ
★백준 9663 : N-QUEEN
한 세시간동안 짠코드이다. 완전 주먹구구식으로 짠것같아서 이렇게 제출해도 될지 모르겠지만 일단 코드를 짜다가 실패한 부분을 나열해보자면
실패 point
-
처음에는 오른쪽 대각선만 체크를 해줬어서 왼쪽 대각선을 다시 체크하는 코드를 만들었다.
-
실패해서 base case까지 가지 못하고 돌아온 line과 i에 해당하는 queen을 놓지 못하는곳을 다시 초기화를 시켜줬어야했는데 처음에는 해당 line 을 0으로 만들면 된다고 생각하여 fill을 사용해서 채워 줬으나 중복되는 부분이 있기때문에 기존 1과 0으로 체크하던 코드를 +1코드로 바꾸어, 재귀 후에는 -1하도록 짰다.
-
마지막으로 base case는 실제 배열에 들어갈것보다 +1할것.
package codeup100;
import java.util.*;
public class Main {
public static Scanner scanner=new Scanner(System.in);
static int n;
static int[][] data;
static int count=0;
static int queen=0;
public static void main(String[] args) {
n=scanner.nextInt();
data=new int[n][n];
solve(0);
System.out.print(count);
}
public static void solve(int line) {
// 한줄에 한개씩 퀸을 놓는 자리를 설정 가능한 자리는 0 안되면+1한다.
if(line==n){ //base case
count++;
return;
}
for(int i=0;i<n;i++) { // line번째 줄에 i번째 자리에 퀸의 자리를 결정
if(data[line][i]==0){
//line+1 부터 n행까지 대각선, 아래 방향을 체크해준다.
int k=i+1; //오른쪽 대각선
int m=i-1; //왼쪽 대각선
for(int j=line+1;j<n;j++) {
if(k<n) { //k가 n보다 작거나 같으면 체크 (대각선 오른쪽)
data[j][k]+=1;
k++;
}
if(m>=0) {//m이 0보다 크거나 같으면 체크 (대각선 왼쪽)
data[j][m]+=1;
m--;
}
data[j][i]+=1;//직선 아래 방향 체크
}
solve(line+1);
int a=i+1; //오른쪽 대각선
int b=i-1; //왼쪽 대각선
for(int j=line+1;j<n;j++) {
if(a<n) { //k가 n보다 작거나 같으면 체크 (대각선 오른쪽)
data[j][a]-=1;
a++;
}
if(b>=0) {//m이 0보다 크거나 같으면 체크 (대각선 왼쪽)
data[j][b]-=1;
b--;
}
data[j][i]-=1;//직선 아래 방향 체크
}
}
}
}
}★백준 1182 : 부분수열의 합
조합 코드를 힐끔도르하면서 쉽게 짰으나 틀렸습니다가 떴다!
실패 point
s가 0일때 아무것도 선택안한 공집합일때도 val값이 0이나오기 때문 ㅠㅠ..
그래서 basecase를 pos==n일때로 바꾸고 안에서 다시 조건문을 주어 카운트했다.
import java.util.*;
public class Main {
public static Scanner scanner=new Scanner(System.in);
static int n,s;
static int[] data;
static int cnt;
public static void main(String[] args) {
n=scanner.nextInt();
s=scanner.nextInt();
data=new int[n];
for(int i=0;i<n;i++) {
data[i]=scanner.nextInt();
}
solve(0,0,0);
System.out.print(cnt);
}
public static void solve(int pos,int val,int a) {
if(pos==n) {
if(a==n) //선택을 아예안했을때
{
return;
}
if(val==s) {
cnt++;}
return;
}
solve(pos+1,val+data[pos],a); //선택하고
solve(pos+1,val,a+1); //선택안하고
}
}
복습
똑같이 반례인 s가 0일때 예외처리를안해서 틀렸다
★백준 1759 : 암호 만들기
같은 골드 5인데도 n queen보다는 훨씬 빨리 푼느낌이다.
실패 point
-
처음에 비트마스크 조합 여러가지 생각이 섞여서 시간이 오래걸림
-
재귀를 끝나고 돌아왔을 때 i값이 되돌아와서 +1 해줘야했다.
-
3개이상의 input이므로 1개이상이 모음이면 나머지는 자음 2개 알아서 맞춰지겠지 생각했는데 모음이 과반수라 자음이 1개일 경우도 있을 수 있어서 자음도 count 해줘야했다.
-
모범답안에는 tmp안에 data를 넣는 시간낭비를 줄이고 tmp에 들어갈 인덱스를 저장하여 출력해줬다.
새로배운거!
Arrays.sort() //배열을 오름차순으로
import java.util.*;
public class Main {
public static Scanner scanner=new Scanner(System.in);
static int l,c;
static String[] data,tmp;
static int cnt;
static StringBuilder sb=new StringBuilder();
public static void main(String[] args) {
l=scanner.nextInt();
c=scanner.nextInt();
data=new String[c];
tmp=new String[l];
for(int i=0;i<c;i++) {
data[i]=scanner.next();
}
Arrays.sort(data);
solve(0,0);
}
public static void solve(int pos,int i) { //pos:현재 tmp의 위치 i:현재 data의 위치
//모든 문자열의 경우의 수 만들고 a i e o u가 하나라도 없으면 없애기
if(pos==l) {
int k=0, m=0; //k는 모음 체크 m은 자음 체크
for(int i1=0;i1<l;i1++) {
if(tmp[i1].equals("a")||tmp[i1].equals("e")||tmp[i1].equals("i")||tmp[i1].equals("o")||tmp[i1].equals("u")) {
k++; //모음 있으면 체크
}
else {
m++;
}
}
if(k>=1&&m>=2) {
for(int i1=0;i1<l;i1++) {
System.out.print(tmp[i1]);
}
System.out.println();
}
return;
}
for(int a=i;a<c;a++) {
//c개의 문자중 l개를 골라 tmp에 넣는다.
tmp[pos]=data[a];
solve(pos+1,i+1); //고르고
i=i+1;
}
}
}