문제 😵‍💫

독일 로또는 {1, 2,...,49}에서 수 6개를 고른다.

로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.

예를 들어, k=8, S={1, 2, 3, 5, 8, 13, 21, 34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다.

{[1, 2, 3, 5, 8, 13], [1, 2, 3, 5, 8, 21], [1,2,3,5,8,34], ..., [3,5,8,13,21,34])

집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램ㅇ을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 이싿. 각 테스트 케이스는 한 줄로 이루어져 있다, 첫 번째 수는 k(6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스마다 수를 고르는 모든 방법을 출력한다. 이때, 사전 순으로 출력한다.

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

내 풀🦷

# 6603. 로또
def backtracking(depth, beginwith):
    if depth == 6:
        print(*result)
        return

    for i in range(beginwith, k):
        if not visited[i]:
            result[depth] = nums[i]
            backtracking(depth+1, i+1)
            visited[i] = False


while True:
    lotto = list(map(int, input().split()))
    k = lotto[0]
    nums = lotto[1:]
    result = [0] * 6
    visited = [False] * k
    backtracking(0, 0) // 깊이, 어디서 부터 시작할건지

    if k == 0:
        quit()
    print()

N과 M으로 다진 백트래킹 개념을 다른 문제에도 적용시키고 싶어서 로또라는 문제를 풀어보았습니다!!!!

어려웠던 점....

1. 테스트 케이스마다 한줄 뛰우는걸 어떻게 하지....

2. 마지막 0이 나왔을 때 종료를 어떻게 하지...

3. 테스트 케이스의 수가 안주어졌는데 어떻게 하지...

백트래킹 개념적인부분 보다는 다른것들에 더 시간을 많이 잡아먹었다....

순,조에 대한 개념은 👇👇👇

https://jeniffer0812techstory.tistory.com/94

참고하면 좋을 개념들 ✍️

• exit() : 프로그램 강제 종료

for i in range(100):
    if i == 5:
        quit()
    print(i)
    
/* 
0
1
2
3
4
*/

유튜버 딩코딩씨 보고 정리해보는 순열과 조합...

재귀, 백트래킹, dfs... 등등 정말 많이 연관되어있어서 정리하면 좋을것 같아 올려봅니다...

##### permutation(순열)

'''
순열 : permutation(포함되어 있는 수가 같은 수여도 순서가 다르면 다른걸로 친다)
dfs 트리와 체크리스트 사용

3개의 공 중에 2개를 뽑는 경우(3P2)
사용한 경우 넣으면 안되므로 체크리스트 사용하는 것임....
깊이 + 1 한후 길이에 맞는 값을 리턴을 하고나면
다시 체크리스트에 빼줘서 다시 넣을 수 있도록 해준다..

1 2
1 3
2 1
2 3
3 1
3 2
6가지
'''

def dfs(L):
    # 종료 조건
    # 리스트의 길이가 찾아야 할 개수(r)가 된다면 종료
    if L == r:
        print(result)
    else:
        for i in range(len(n)):
            # 체크리스트에 해당하는 값이 없다면
            if checklist[i] == 0:
                # result 리스트에 값을 추가
                result[L] = n[i]
                # 체크리스트에 값이 생겼다고 표시해주기
                checklist[i] = 1
                # 다음 깊이로 이동
                dfs(L+1)
                # 다음 번에 다시 사용하기 위해서 빼준다고 그냥 생각하셈 ^^;;;
                checklist[i] = 0

n = [1, 2, 3]
r = 2
result = [0] * r
checklist = [0] * len(n)
dfs(0)

이해도 이해지만 어느정도 외울만큼은 외우라고 하심...

이해해야 외우지 싶다가도 이러다가 진도가 영 안나갈거 같아서 적당히 이해시켜서 외우는것이 좋을 듯...

'''
조합 : 같은 숫자가 포함되어 있으면 같은 걸로 인정....
순열보다 경우의 수가 훨씬 작음...
순열보다 더 간단...
한번 썼으면 다시 쓰지를 않으니까 체크리스트도 필요없음...
DFS 트리를 이용해서 푼다

3C2

1 2
1 3
2 3

3가지
'''
def dfs(L, BeginWith):
    # 종료 조건
    if L == r:
        print(*result)
    else:
        for i in range(BeginWith, len(n)): # 시작하는 값부터 끝까지
            result[L] = n[i] # 해당하는 값을 넣어주기
            dfs(L+1, i+1) # 다음 깉이 다음 숫자로 이동하여 전 값을 들어오지 못하도록


n = [1, 2, 3]
r = 2
result = [0] * r

dfs(0, 0) # level, begin(어디서 시작할지)

5
4 1 5 2 3
5
1 3 7 9 5

1
1
0
0
1

틀린 내 풀🦷

# 1920. 수찾기
import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, sys.stdin.readline().split()))

M = int(input())
arr_2 = list(map(int, sys.stdin.readline().split()))
result = []

for j in range(M):
    one = []
    for i in range(N):
        if arr[i] == arr_2[j]:
            one.append(1)
            break
        else:
            one.append(0)

    # print(one)
    cnt = 0
    for k in one:
        if k == 1:
            cnt += 1
    if cnt >= 1:
        result.append(1)
    else:
        result.append(0)

for k in result:
    print(k)

구직구직하게 짜기 달인이 되버린 나,,,,

단계별 풀이로 안들어가고 성공률로 들어가서 안 풀어져 있는거 풀어가지고

어떤 방식으로 풀어야하는지 힌트(이차원 배열이다, 정렬이다, 이진탐색이다 이런거)가 없어서 어카지 하다가

찾아야할 값이 주어진 arr_2 리스트를 돌라면서 arr을 돌리는 완전 탐색으로 찾아서 있으면 더해주면 되겠다..

싶었고 무슨일로 인덱스 아웃오브레인지도 안나고 한번에 성공했는디.... 했는데.... 제출했는데...

했는데 시간초과가 나버렸다 ㅋㅋ 혹시나 몰라서 import sys로도 바꿔봤는데 실패....ㅜㅜ

수정된 내 풀🦷

백준에서 풀다가 막히면 질문게시판 들어가서 종종 힌트를 얻는데

나처럼 구질구질하게 푸는 사람이 없었고 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

set을 사용하여 입력받아 시간을 적게 걸리게 하는 방법이나 이진 탐색을 사용하였다!!

그러고 보니 이진 탐색을 이용하면 되었는데 혼자서 브로노마스(무지성)으로 하고있었다....

그래서 먼저 해본 set() 으로 입력 받기 =>

N = int(input())
arr = set(map(int, input().split())) # 출력 시간을 줄이기 위해 set 받음

M = int(input())
arr_2 = list(map(int, input().split()))

for i in arr_2:
    if i in arr: print(1)
    else: print(0)

결과는 성공~~~~~

set을 자주 안 쓰다보니 어떤 부분에서 쓸지 몰랐는데

입력을 set으로 받아 사용한다는 점을 알게 되었다!!

이진탐색으로 풀은 내 풀🦷

또 다른 방법중에 하나인 바이너리 서치를 통한 방법도 많이 보여서 도전해 보았다~~

N = int(input())
arr = list(map(int, input().split()))
arr.sort() # 이진탐색은 정렬된 것들 탐색하는데 이 부분 기억을 못해서 무한 루프로 몇번 다녀왔다
M = int(input())
arr_2 = list(map(int, input().split()))

for i in arr_2:
    # 바이너리 서치 활용하기(이진탐색)
    result = False 
    start = 0 # 시작 인덱스
    end = N - 1 # 끝 인덱스

    while start <= end:
        mid = ((start + end) // 2) # 중간값의 위치에 해당하는 수와 목표 비교해 나감
        if i == arr[mid]: # 중간값과 목표값이 같다면
            result = True
            break
        elif i > arr[mid]:
            start = mid + 1
        else:
            end = mid - 1

    if result:
        print(1)
    else:
        print(0)

시험에도 나오기는 했지만 오랜만에 이진탐색을 사용해서 계속 틀린값이 나오고

무한루프로 잠시 먼나라이웃나라 다녀왔다....

중간값과 목표값을 비교하면서 시작점이 마지막점보다 넘어서면 종료되는 기저조건을 설정하였다!!!!

참고함면 좋을 개념들 ✍️

1) 이진 검색(Binary Search)

:  자료의 가온데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법

 => 목적 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가면서 보다 빠르게 검색을 수행한다

- 이진 검색을 하기 위해서는 자료가 정렬된 상태여야 한다(정렬이 아니라 뒤에 수가 앞에 수보다 커버리면 오바자나.. 찾을 수가 없음!!!!!! 주의!!!!!!!!1..)

- 검색 과정

1. 자료의 중앙에 있는 원소를 고른다
2. 중앙 원소의 값과 찾고자 하는 목표 값을 비교한다
3. 목표값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로 검색을 수행, 크다면 자료의 오른쪽 반에 대해서 세로 검색을 수행
4. 찾고자 하는 값을 찾을 떄까지 1~3의 과정을 반복한다
5. 찾는다면 성공, 못 찾으면 실패

- 구현

• 검색 범위의 시작점과 종료점을 이용하여 검색을 반복 수행한다 => while의 종료 조건을 잘 설정하기
• 이진 검색의 경우, 자료에 삽입이나 삭제가 발생했을 때 배열의 상태를 항상 정렬 상태로 유지하는 추가 작업이 필요

# 이진 검색 알고리즘
def binarySweach(a, N, key):
	start = 0  # 시작점 
    end = N -1  # 종료점
    while start <= end:
    	middle = (start + end) // 2 # 몫으로 하는 이유 : 나누기 연산자를 사용하면 .0으로 float되걸랑
        if a[middle] == key: # 검색 성공
        	 return true
        elif a[middle] > key:
        	 end = middle - 1
        else:
        	start = middle + 1
    return flase # while 문을 다 돌았는데도 찾지못한다면 검색 실패

< 10951. A+B - 4 > 

입력이 끝날 때까지 A+B를 출력하는 문제. EOF에 대해 알아 보세요!!

아무생각 없이 앞문제랑 똑같네 뭐야,,, 하면서 열심히 적었는데 계속 런타임 에러가 나더라구요....ㅠ

그래서 다시 문제를 살펴봤는데 문제 밑에 EOF에 대해 알아보라고 하더라구여 ;;;;

EOF는 또 뭐람...

EOF 먼저 알아보겠습니다 🤔🤔

EOF : 데이터 소스로부터 더 이상 읽을 수 있는 데이터가 없음을 나타내는 용어

알고리즘 문제를 풀때 입력값을 얼마나 받을지 명시하지 않을 경우 사용합니다!!

1) Scanner 사용 시

• hasNext() 메소드 사용
• 입력된 토큰이 있으면 true를 반환하고, 그렇지 않을 경우 false를 반환합니다

2) BufferReader 사용시

• null 이 아님을 명시해 줍니다!!

파이썬과 C++ 언어 사용의 경우에 다 다르므로 자신이 사용하는 언어 별 EOF를 검색하시면 될 것 같아요 😂

import java.util.Scanner;
 
public class Main {
	public static void main(String args[]){
		
		Scanner in=new Scanner(System.in);
			
		while(in.hasNextInt()){
		
			int a=in.nextInt();
			int b=in.nextInt();
			System.out.println(a+b);
		}	
		in.close();
	}
}

원래라면 while(true)를 써줄껀데 마지막 데이터를 알 수 없으니까 while(in.hasNextInt())를 사용해줬다

진짜 몇번 틀렸는지 셀 수는 있지만ㅋ 많이 틀렸다..

이거 BufferReader로 바꾸면 또 많이 틀릴것 같았지만 해봐야할 거 같아서 일단 해봤다.

import java.io.*;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		while (true) {
			String str = br.readLine();
			if (str == null) {
				break;
				
			}
			
			st = new StringTokenizer(str);
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			bw.write(a + b + "\n");
		}
		bw.close();
	}
}

값이 없으면 멈춰야 하니까 str == null을 사용해줬다.

메모리나 시간적으로나 적게 걸려서 버퍼리더 쓰는 연습을 열심히 해야할 것 같다.. 실제로 자바가 다른 언어보다 느리다고 하니 더더욱 버퍼 연습해야할 듯

<10952. A+B - 5>

package bj0715;

import java.util.Scanner;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
	
		while (true) {
			int a = sc.nextInt();			
			int b = sc.nextInt();
			
			if (a == 0 && b == 0) {
				sc.close();
				break;
			}
			
			else  {
				System.out.println(a + b);
			}
		}
	}
}

처음에 문제도 제대로 안 일고 테스트 케이스를 만들었는데 계속 정답이 안 나와서 다시 보니까

테스트 케이스를 입력한다는 조건이 없었다 ;;;;;

이래서 문제를 잘 읽어야 한다고...

아무리 생각해도 for 문을 사용해서는 문제가 안풀리겠다 생각했는데 반복문에 for만 있었던게 아니었던거 같다^^ 싶었음

그래서 while문을 사용해줬구여... 문제는  a, b 둘다 0일때만 while문을 빠져나가는 것으로 간단하게 해결했습다 😂

for문, while문은 서로 변환이 가능하기 때문에 반복문을 작성할 때 어느 쪽을 선택해도 좋지만, for문은 반복 횟수를 알고 있을 때 주로 사용하고 while문은 조건에 따라 반복할 때 주로 사용한다고 합니다!!

근데 sc.close가 입력을 다 받고 난 후로는 어디든 써도 된다고 알고 있는데 프린트 앞줄에 썼는데 안되더라구여..

혹쉬 아시는 분 있으시면 댓글 남겨주삼유 ✍️✍️

import java.util.Scanner;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		
		for (int i =1; i<=T; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			
			System.out.println("Case #" + i + ": " + a + " + " + b + " = " + (a+b));
		}
		sc.close();
	}
}

계속 비슷한 부분이라 이제 반복문은 두문제씩 풀게요...

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
	public static void main (String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		
		for (int i=1; i<=T; i++) {
			
			st = new StringTokenizer(br.readLine());
			
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			bw.write("Case #"+ i + ": " + a + " + " + b + " = " + (a+b) + "\n");
		}
		bw.close();
	}
}

친구가 import 부분 import java.io*로 바꿀 수 있다 그랬는데 저는 왜 에러 뜰까요... ㅇㅈ님.....

그래서 그냥 원래 하던대로 다 적어보았습니다...

어제 문제랑 다른거는 밑에 write부분 정도라 그닥 한게 없네용

사실 어제(13일)에 했는데 기절해버려서 오늘 아침에 적어봅니다 ㅜㅜ 

오늘은 별찍기로 만나요 ✨✨

5
1 1
2 3
3 4
9 8
5 2

Case #1: 2
Case #2: 5
Case #3: 7
Case #4: 17
Case #5: 7

<풀어보오자>

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		
		for (int i = 1; i<=T; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			
			System.out.println("Case #" + i + ": "+ (a+b));
		}
		}
	}

간단한 출력문제라 간단하게 해결!!

어제 공부한 BufferedReader/Writer로도 한번 해볼께요~~

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.StringTokenizer;

public class Solution11021_bf {
	public static void main (String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		
		for (int i=1; i<=T; i++) {
			
			st = new StringTokenizer(br.readLine());
			
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			bw.write("Case #"+ i + ": " +  +(a+b) + "\n");
		}
		bw.close();
	}
}

아직은 버퍼 쓰기 좀 어색하네요 ㅎㅎㅎ import도 많구....

그래도 출력이 빠르다고 하니 계속 시도는 해보겠습니다

import java.util.Scanner;

public class Solution15552 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		int arr[] = new int[T];
		
		for (int i=0; i<T; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			arr[i] = a + b;
			
		}
		sc.close();
		
		for (int k : arr) {
			System.out.println(k);
		}
	}
}

스캐너로 풀었는데 시간초과로 문제가 풀리지 않았다..

드디어 올게 왔다...

뭔가 길고 복잡해서 애써 무시하고 있었던 BufferReader를 무조건 사용해야하는 문제다.

앞으로도 자주 사용할거 같아서 먼저 BufferReader/Writer를 검색해 보았다

BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 선언
String s = br.readLine(); 
int i = Integer.parselnt(bf.readLine());

StringTokenizer st = new StringTokenizer(s); //StringTokenizer인자값에 입력 문자열 넣음
int a = Integer.parseInt(st.nextToken()); //첫번째 호출
int b = Integer.parseInt(st.nextToken()); //두번째 호출

String array[] = s.split(" "); //공백마다 데이터 끊어서 배열에 넣음

Read한 데이터는 Line단위로만 나눠지기에 공백단위로 데이터를 가공하려면 따로 작업을 해주어야하는데, 위의 두가지 방법이 대표적이다.

첫번째 방법으로는 StringTokenizer에 nextToken()함수를 쓰면 readLine()을 통해 입력받은 값을 공백단위로 구분하여 순서대로 호출할 수 있다.

두번째 방법으로는 String.split()함수를 활용하여 배열에 공백단위로 끊어서 데이터를 넣고 사용하는 방식이다

*BufferedWriter사용

BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));   //할당된 버퍼에 값 넣어주기
String s = "abcdefg";   //출력할 문자열
bw.write(s+"\n");   //버퍼에 있는 값 전부 출력
bw.flush();   //남아있는 데이터를 모두 출력시킴
bw.close();   //스트림을 닫음

BufferedWriter 의 경우 버퍼를 잡아 놓았기 때문에 반드시 flush() / close() 를 반드시 호출해 주어 뒤처리를 해주어야 한다.

그리고 bw.write에는 System.out.println();과 같이 자동개행기능이 없기때문에 개행을 해주어야할 경우에는 \n를 통해 따로 처리해주어야 한다.

​

위에 내용을 보고 다시 BufferedReader/Writer를 사용해서 다시 해본결과..

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine()); 
		for(int i=0; i<T; i++) {
			st = new StringTokenizer(br.readLine());
			
			int a = Integer.parseInt(st.nextToken()); 
			int b = Integer.parseInt(st.nextToken()); 
			
//			bw.write((Integer.parseInt(st.nextToken(a))+Integer.parseInt(st.nextToken(b)))+"\n");
			bw.write(a+b+"\n");
		}
		bw.close();
	}

}

새로운 내용을 공부하고 이해하고 다시 적용해보고 수정하고를 계속하다보니 시간이 한시간이 넘게 걸렸다..

이거 하나 이해하는데 이렇게 오래 걸려서 언제 늘고 할란가 모르겠지만 내일 또해야지 뭐 💪💪💪

개념은 알거같은데 적용이 어려워서, 앞으로 있을 출력 문제들을 Scanner뿐만 아니라 BufferedReader/Writer도 사용하는 연습을 해야할 것 같다.. 아좌좌~