알고리즘 (6) 썸네일형 리스트형 [백준 1269] 대칭 차집합 - JAVA 1. 문제 해석 문제에 따르면 A 집합과 B 집합이 다음과 같은 형태로 존재할 때 이들의 대칭 차집합은 아래와 같습니다. 위와 같은 형태로 집합을 구하고, 그 집합의 원소의 개수를 구하면 되는 간단한 문제입니다. Bit-string으로 표현되는 Set을 이용하기로 했습니다. Set을 Bit-string으로 표현하면 전체 집합의 크기가 N일 때, 각 집합을 N bit로 표현하고, 원소가 집합에 포함되어 있으면 해당 bit를 1로, 그렇지 않으면 0으로 표현하게 됩니다. 예를 들어서 10bit로 집합 A = {1, 3, 5, 7, 9}를 표현하면 아래와 같습니다. 어떤 원소가 집합 A에 속하는지 확인할 때는 value가 1인지 아닌지만 확인하면 되고 원소의 삽입과 삭제는 해당 bit를 1 또는 0으로 설정하.. [백준 1018번] 체스판 다시 칠하기 - Java 1. 문제 해석 흰색, 검은색의 정사각형들로 구성된 MxN 크기의 보드를 8x8 크기로 잘라서 체스판으로 활용하려고 합니다. 색 구별은 임의로 되어 있어서 보드를 자르고 난 뒤에는 체스판에 맞게 색을 덧칠한다고 합니다. 이때 색을 덧칠하는 횟수가 최소가 되는 보드 위치를 찾는 것이 요구사항입니다. 해당 문제에서 중요한 부분은 설명란의 2번째 구문입니다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, (중략) 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. (중략) 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다. 이는 맨 왼쪽 위칸이 흰색인 경우(이하 'case_white')와 검은색인 경우(이하 'case_black') 모두 고려해서 알고리즘을 작.. [백준 7568번] 덩치 문제 -Java 사람의 덩치로 등수를 정하는 문제입니다. 덩치가 큰 사람이 순위가 높은 것인데 문제에서 정의하는 "덩치가 큰 사람"은 몸무게가 더 많고 키가 더 큰 사람을 말합니다. 즉, 몸무게나 키 중 1개라도 작은 수치를 가진다면 덩치가 크다고 할 수 없습니다. 덩치를 비교한 결과는 아래의 3개로 나타납니다. A) 몸무게와 키 모두 크다. B) 몸무게와 키 어느 하나가 크지 않다. C) 몸무게와 키 모두 작다. 순위가 높아지는 결과는 A)이고, 그렇지 않은 경우는 B)와 C)입니다. 따라서 모두의 순위가 1순위로 가정하고 A)의 경우가 아니면 순위를 하락시키는 방법을 생각했습니다. 1. 알고리즘 몸무게, 키 데이터 및 덩치를 비교하는 메소드를 관리하고자 'Pair'라는 class를 정의했습니다. // 몸무게 및 키를.. [프로그래머스 2021 카카오] 숫자 문자열과 영단어 알고리즘) 영문자로 입력되는 숫자를 해당하는 숫자로 대체시키는 문제입니다. String형태여서 한 문자씩 읽을 수 있기 때문에 문자가 숫자인 경우와 영문자인 경우로 나눠서 코딩했습니다. 먼저 한 문자씩 읽어야 하므로 아래와 같이 String의 charAt() 메소드를 활용했습니다. String s = "2three45sixseven" int idx = 0; System.out.println(s.charAt(idx));// 2 읽어들인 문자가 숫자인 경우는 바로 결과값에 더해주기만 하면 됩니다. 반대로 영문자인 경우는 숫자로 변환해주고 결과값에 반영해야 되기 때문에 HashMap을 활용했습니다. // 영어단어를 숫자로 매핑 MapnumWord = new HashMap(); numWord.put("zero".. [백준 2231번] 분해합 문제 - Java 완전 탐색 알고리즘) 문제에서 정의된 N의 생성자 M들 중에서 가장 작은 생성자를 구해내는 프로그램을 작성하라고 제시하였습니다. 따라서 1부터 하나씩 분해합을 구하고, 생성자가 맞는지 확인하도록 코드를 작성하고자 했습니다. 첫 번째 시도) M을 1부터 시작해서 분해합을 구한 다음에 N과 비교하게 됩니다. 만약 분해합이 N과 동일하면 해당 값을 result 변수에 저장하고 반복문을 탈출하는 반면, 동일하지 않으면 코드를 반복 수행하게 됩니다. import java.util.Scanner; public class decompose_2231 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.next.. [백준 2798번] 블랙잭 문제 - Java 완전 탐색 알고리즘) 주어진 조건을 모두 비교해서 답을 찾는 기법으로, 재귀함수를 통해서 해당 문제를 해결해보았습니다. 첫 번째 시도) 아래의 코드를 백준에 제출한 결과로 런타임 오류가 출력되었습니다. 시간 제한과 주어진 숫자의 최대 개수를 고려했을 때, 정수의 합을 구하는 반복문 구절에서 제한시간을 넘긴 것 같았습니다. import java.util.Scanner; public class blackjack_2798 { static int N = 0, M = 0; public static void main(String[] args) { int black = -9999; Scanner sc = new Scanner(System.in); N = sc.nextInt();// 입력받을 정수들의 개수 M = sc.. 이전 1 다음
