알고리즘216

• [백준] 1890번: 점프 - java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int[][] arr = new int[n][n]; long[][] dp = new long[n][n]; for (int i = 0; i < n; i++) { String[] input = br.r.. 알고리즘/동적프로그래밍(DP) 2023. 2. 2.

• [swea] 1244번: 최대상금 - 파이썬(python) 완전탐색을 이용한 풀이. 갈피를 잡지 못해 다른 분들의 코드를 참고했다. 0번째 인덱스부터 탐색을 시작하는데, 현재인덱스값 이상인 값이 있다면, 현재 인덱스의 값과 교환한다. 그런다음,(현재 탐색중인 인덱스 (i) , 교환횟수+1) 을 dfs 인자로 주고 탐색한다. 만약 교환횟수를 모두 써버렸다면, 최댓값보다 현재 교환된 숫자결과가 더 크다면 갱신한다. 만약, 이미 내림차순 정렬이 되어있어 교환횟수가 남아있는 상태라면, 홀수라면 마지막 1,2번째 인덱스를 바꾸고, 짝수라면 그대로 둔다. 나의 풀이 def dfs(idx, n): global max_val if n == int(cnt): max_val = max(max_val, int(''.join(data))) return for i in range(id.. 알고리즘/완전탐색 2022. 11. 14.

• [swea] 2806번: N-Queen - 파이썬(python) 백트래킹에 대한 문제를 거의 풀어보지 않아서, N-Queen 문제도 처음 접해보았다. BFS 와 대체로 비슷하지만, 더 이상 탐색할 필요가 없는걸 쳐내는 행위를 백트래킹 이라고 한다. 따라서, 한 행씩 퀸을 놓아보는데, 지금까지 같은열 or 대각선에 퀸이 있지 않다면 계속해서 BFS 를 진행하는 것이다. 이때, 한 행씩 퀸을 순서대로 놓기 때문에, 같은 행에 여러 퀸이 놓이는 경우는 고려하지 않아도 된다. row 리스트의 경우, 각 인덱스가 행번호를 의미하고, 각 인덱스값은 열번호를 의미한다. 즉, row의 i번째 행에 있는 값이 j라면, 퀸이 (i,j) 에 위치함을 뜻한다. 또한, visited 리스트를 두어 i번째 열에 퀸이 위치하는지를 확인할 수 있다. 이로 인해, visited[col] 에 이미 .. 알고리즘/DFS, BFS 2022. 11. 13.

• 

  [swea] 3282번: 0/1 Knapsack - 파이썬(python) 처음엔 백트래킹으로 문제를 풀었는데, 제한시간 초과로 실패하게 되었다. 백트랙킹의 경우 보통 시간 복잡도가 2^n 에 근접하다. 따라서 n이 20이하인 경우에만 백트래킹을 사용해야 한다. 이 문제의 경우 n=100 이므로, 2^100은 당연히 시간초과를 일으킬 것이다.... 따라서 dp를 사용하자! dp[i][j] 에서 i는 i번째 물건까지 선택할 수 있음을 뜻하고, j는 j무게까지 물건을 담을 수 있음을 뜻한다. 현재 물건무게가 j 보다 크다면, 해당 물건을 선택할 수 없으므로 [이전 물건][같은 무게] (dp[i-1][j]) 를 입력해준다. 현재 물건무게가 j이하라면, 둘 중 더 큰 값을 선택한다. 현재 물건을 넣어준다. 현재물건가치 + knapsack[i-1][j-weight] (이전물건, j-현재.. 알고리즘/동적프로그래밍(DP) 2022. 11. 12.

• 

  [swea] 3304번: 최장 공통 부분 수열 - 파이썬(python) s1 = CAPCAK, s2 = ACAYKP 의 문자열에서 최장 공통부분, Longest Common Subsequence (LCS) 을 찾자. dp값을 구하는 방법은 다음과 같다. if (arr[i] == arr[j]) dp[i][j] = dp[i-1][j-1] + 1; if (arr[i] != arr[j]) dp[i][j] = max(dp[i][j-1], dp[i-1][j]); 만약 s1의 i번째 문자열과 s2의 j번째 문자열이 같다면, 이는 dp[i-1][j-1] +1 과 같을 것이다. s1의 i-1번째까지와 s2의 j-1번째까지 비교한 값 + 1 의 값이기 때문이다. ex) dp[2][3] 의 경우, dp[1][2] (C와 AC 를 비교한 값 : 1) + 1과 같다. 만약 s1의 i번째 문자열과 .. 알고리즘/동적프로그래밍(DP) 2022. 11. 12.

• [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] 5215번: 햄버거 다이어트 - 파이썬(python) 재료리스트, 칼로리리스트의 0~n-1 까지의 인덱스에 재료점수와 재료의 칼로리를 저장해둔다. 그런 다음 i번째 재료를 추가할지, 추가하지 않을지의 여부에 따라 DFS 를 진행해간다. i가 n 이라면, 1~n까지의 재료에 대해 모든 선택을 완료한 것이므로, DFS 를 종료한다. * 지금까지 구한 점수 + 현재 인덱스부터 끝 인덱스까지 점수를 모두 더한 값이 현재 max_score 이하라면, 굳이 검사를 하지 않아도 최댓값이 갱신되지 않으므로 바로 return 할 수 있다. 이는 시간을 줄일 수 있는 아주 좋은 방법이다. 나의 풀이 def dfs(i, total, calorie): global max_score if i == n: max_score = max(max_score, total) return # .. 알고리즘/DFS, BFS 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.