알고리즘/이것저것47

• 

  [백준] 1253번: 좋다 - java 구상하기 정렬이 필수다. => 정렬이 된 숫자 배열을 투포인터로 탐색한다면, O(n) 안에 어떤 숫자가 두 개의 합으로 나타낼 수 있는지를 확인할 수 있다. left, right 값을 설정해주는데, 정렬을 해주었다고 right값을 (현재 숫자의 인덱스 - 1) 로 해서는 안된다!! -> 음수가 있어서 현재 숫자보다 큰 수와 더해도 현재 숫자가 나올 수 있다 각 포인터 값의 합이 현재 숫자보다 크다면, 더 작은 수와 더해야하므로 right-- 반대로 현재 숫자보다 작다면, 더 큰 수와 더해야 하므로 left++ 나의 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.. 알고리즘/이것저것 2023. 4. 17.

• 

  [swea] 5607번: [Professional] 조합 - java 페르마의 소정리를 모르면 못 푸는 문제... 페르마의 소정리란 p가 소수이고, a가 p로 나누어지지 않는 정수 일 때 성립하는 법칙이다. 이 문제에서 정답을 구하기 위해선 결국 (n! / r! (n-r)!) 를 1234567891 로 나눈 나머지 값, 즉, (n! / r! (n-r)!) % 1234567891 을 구해야 한다. 결국 모듈러의 연산 공식을 활용해야 하는데, 모듈러 연산에서 나눗셈 연산은 허용되지 않는다! 즉, r! (n-r)! 의 분모에 대한 모듈러 연산은 분배법칙을 적용할 수가 없음을 뜻한다. 따라서 모듈러 연산의 곱셈의 분배법칙을 이용해야 한다!! (n! / r! (n-r)!) 을 곱셈꼴로 만들기 위해선 역원을 이용해야 한다! 와 같다. 이때, 페르마의 소정리를 이용한다면 아래와 같다... 알고리즘/이것저것 2023. 4. 6.

• 

  [백준] 1493번: 박스 채우기 - java 나의 풀이 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayList; import java.util.StringTokenizer; public class Main { static BufferedReader br; static BufferedWriter bw; static StringBuilder sb; static StringTokenizer st; static int L, W, H, N, min_cnt; static int[] cu.. 알고리즘/이것저것 2023. 3. 6.

• 

  [백준] 21939번: 문제 추천 시스템 Version 1 - java 명령어 이 문제는 사실상 단순 구현이다. 그러나 어떤 자료구조를 사용할지에 따라 속도에서 차이가 날 수 있을 듯 하다. 처음에는 PriorityQueue를 사용해서 최대힙, 최소힙을 두개 구했었다. 그러나 treeset 을 이용하면 한 개의 객체만으로도 first(), last() 메소드를 통해 최대,최소 데이터를 구할 수 있기에, treeset을 사용하기로 하였다. TreeSet & HashMap import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashMap; import java.util.Map; import java.util.StringTokenizer.. 알고리즘/이것저것 2023. 2. 12.

• 

  [백준] 2023번: 신기한 소수 - java import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Scanner; /** * 신기한 소수 : 에라토스테네스의 체 => 시간 초과!! * @author SSAFY * */ public class Main { static int n; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); int arr[] = {2,3,5,7}; for(Integer i : arr) recur(1,i); } public static void recur(int length, int num) { if.. 알고리즘/이것저것 2023. 2. 9.

• 

  [백준] 12891번: DNA 비밀번호 - java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { static int s_len; static int p_len; static char[] str; static int[] checkArr = new int[4]; static int[] myArr = new int[4]; static int checkCnt = 0; // {‘A’, ‘C’, ‘G’, ‘T’} 중 최소 개수를 일치한 문자 개수 (0~4) static int answer = 0; // 만들.. 알고리즘/이것저것 2023. 2. 9.

• [swea] 4371번: 항구에 들어오는 배 - 파이썬(python) 모든 배는 1일에 들어온다. 즐거운날은 오름차순으로 정렬이 되어있으므로, 2번째 날짜부터 마지막 날짜까지 탐색하면서 주기를 계산한다. 계산한 주기마다 해당되는 날짜가 ship 집합에 들어있지 않다면 ship 이라는 집합에 추가하고, 배의 개수를 1 증가한다. ex) 즐거운 날 :1 4 6 7 9 10 11 13 16 17 19 첫번째 주기 : 4-1 = 3 ship -> 4,7,10,13,16,19 두번째 주기 : 6-1 = 5 ship -> 4,6,7,10,11,13,16,19 세번째 주기 : 7-1 = 6 -> 이미 ship 에 들어있으므로, 해당 주기의 약수값을 가지는 주기가 이미 존재하는 것이다. 따라서 패스 세번째 주기 : 9-1 = 8 ship -> 4,6,7,9,10,11,13,16,17,1.. 알고리즘/이것저것 2022. 11. 7.

• [swea] 5293번: 이진 문자열 복원 - 파이썬(python) DFS 로 풀었다가 시간초과로 낭패를 본 문제.. 무작정 문제를 보자마자 달려들지 말고, 천천히 규칙을 찾아보는 습관을 가지자. 꼭 알아야 할 규칙은, 01패턴과 10패턴은 항상 개수가 같거나, 혹은 개수 차이가 1이라는 것이다. 위 규칙만 안다면, 아래 코드를 쉽게 구현할 수 있을 것이다. a : 00패턴의 개수 b : 01패턴의 개수 c : 10패턴의 개수 d : 11패턴의 개수 1. "0" * (a+1) 2. "1" * (d+1) 3. "0" * (a+1) + "10" * (b-1) + "1" * (d+1) + "0" 4. "0" * (a+1) + "10" * (b-1) + "1" * (d+1) 5. "1" * (d+1) + "01" * b + "0" * (a+1) 6. 나머지의 경우는 존재할 수 .. 알고리즘/이것저것 2022. 11. 7.

• [swea] 6019번: 기차 사이의 파리 - 파이썬(python) 나는 반복문을 이용해서 문제를 단계별로 구현했는데, 답은 나오나 시간초과로 실패하였다. 따라서 다른 분들의 코드를 참고하였더니, 알고보니 엄청 간단한 문제였다ㅠㅠ 그냥 단순한 수학문제이다...ㅋ 이래서 생각을 하고 풀어야 하나보다. 서로 다른 기차 A,B 는 양 끝에서 서로를 향해 달려온다. 따라서 두 기차가 충돌하는 시간은 A와 B의 최초 거리 / (A의 속력+B의 속력) 이다. 여기에 파리에는 매초마다 같은 속력으로 움직이므로, 위에서 구한 시간 * 파리의 속력이 파리가 움직인 총 거리가 될 것이다. 나의 풀이 T = int(input()) answer = [] for t in range(1, T+1): d, a, b, f = map(int, input().split()) move = d/(a+b) .. 알고리즘/이것저것 2022. 11. 6.

• [swea] 7584번: 자가 복제 문자열 - 파이썬(python) 입력범위가 K(1 ≤ K ≤ 1018) 이므로 모든 P값을 찾으려고 하면 낭패이다. 따라서 규칙을 찾아야 한다. p=“001001100011011...” 으로 진행되는데0인 숫자의 인덱스는 0,1,4,5,7,8,9,12,15,16,17,19,20,24,25,28...1인 숫자의 인덱스는 2,5,6,10,11,13,14,18,21,22,23,26,28,29... 와 같다.따라서 4의 배수면 0의 값이고,4의 배수가 아닌 2의 배수면 1임을 알 수 있다.홀수인덱스의 경우 (i-1)/2 의 값에 따라 결정된다. 나의 풀이 T = int(input()) answer = [] for t in range(1, T+1): k = int(input()) - 1 while k >= 0: if k % 2 == 1: k =.. 알고리즘/이것저것 2022. 11. 6.

• [swea] 14413번: 격자판 칠하기 - 파이썬(python) T = int(input()) for t in range(1, T+1): n, m = map(int, input().split()) arr = [] for _ in range(n): arr.append(list(input())) board = [0,0,0,0] for x in range(n) : for y in range(m) : if arr[x][y] == "#" : if (x+y) % 2 == 0 : board[0] += 1 else : board[1] += 1 elif arr[x][y] == "." : if (x+y) % 2 == 0 : board[2] += 1 else : board[3] += 1 if (board[0] != 0 and board[1] != 0) or (board[0] != 0 a.. 알고리즘/이것저것 2022. 11. 1.

• [swea] 1928번: Base64 Decoder - 파이썬(python) 출처 : https://swexpertacademy.com/main/solvingProblem/solvingProblem.do Encoding 순서 는 다음과 같다. 1. 우선 24비트 버퍼에 위쪽(MSB)부터 한 byte씩 3 byte의 문자를 집어넣는다. 2. 버퍼의 위쪽부터 6비트씩 잘라 그 값을 읽고, 각각의 값을 아래 [표-1] 의 문자로 Encoding 한다. 문제 는 다음과 같다. 입력으로 Base64 Encoding 된 String 이 주어졌을 때, 해당 String 을 Decoding 하여, 원문을 출력하는 프로그램을 작성하시오. 즉, 인코딩된 string 을 인코딩 과정의 역순으로 진행하여, 원문을 출력해야 한다. Step 1 먼저, input 의 각 문자는 어떤 값을 표1의 문자로 인.. 알고리즘/이것저것 2022. 10. 31.