SW개발/코딩테스트

    [백준]1018번 체스판 다시 칠하기 - 완전 탐색
    SW개발/코딩테스트

    [백준]1018번 체스판 다시 칠하기 - 완전 탐색

    https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net n, m = map(int, input().split()) chess = [[0] * m for i in range(n)] for i in range(n): chess[i] = list(input()) change = 32 # 가장 최대로 많이 바꾸는 경우 for i in range(n): for j in range(m): if i + 8

    [백준]7568번 덩치 - 완전 탐색
    SW개발/코딩테스트

    [백준]7568번 덩치 - 완전 탐색

    n = int(input()) person = [[0] * 2 for i in range(n)] answer = [1] * n # 순위 카운트 for i in range(n): person[i][0], person[i][1] = map(int, input().split()) for i in range(n): for j in range(n): if person[i][0] < person[j][0] and person[i][1] < person[j][1]: # 자신보다 키 몸무게 클 경우에만 answer[i] += 1 # 카운트를 함 for i in range(n): print(answer[i] , end=' ') # 출력 코드 설명 몸무게와 키를 저장하기 위한 person, 순위를 매기기 위한 answer..

    [백준]2231번 분해합 - 완전 탐색
    SW개발/코딩테스트

    [백준]2231번 분해합 - 완전 탐색

    n = int(input()) for i in range(1, n + 1): a = list(str(i)) if i + sum(map(int, a)) == n: print(i) break if i == n: print(0) 코드 설명 반복문은 1부터 n 까지 진행한다. 입력을 받을때 숫자를 분해시켜 저장하기 위해 str() 로 변환후 list() 함수를 이용한다. 만약 본래의 숫자 + 분해시켜 저장한 숫자의 합이 n 과 같다면 그 수를 출력시키고 종료한다. 마지막 반복인 i == n 이 될 경우에는 생성자가 없으므로 0을 출력한다. Point : 숫자를 분해하는 작업을 위해 list 형으로의 변환이 필요하다. 또한 1부터 반복되기에 조건을 만족하면 그것이 바로 가장 작은 생성자가 된다.

    [백준]2798번 블랙잭 - 완전 탐색
    SW개발/코딩테스트

    [백준]2798번 블랙잭 - 완전 탐색

    n, m = map(int, input().split()) num = list(map(int, input().split())) length = len(num) ans = 0 # 3중 포문을 통하여 차례로 탐색 for i in range(length - 2): for j in range(i + 1, length - 1): for x in range(j + 1, length): if num[i] + num[j] + num[x] > m: # 3개를 더한 값이 크다면 넘어감 continue else: # m 보다 크지 않다면 저장된 값과 새로 더한 값중 큰것을 선택 ans = max(ans, num[i] + num[j] + num[x]) print(ans) 코드 설명 모든 경우를 탐색하는 완전 탐색의 문제이므로..

    [백준]12865번 평범한 배낭 - DP
    SW개발/코딩테스트

    [백준]12865번 평범한 배낭 - DP

    n, k = map(int, input().split()) weight = [[0] * 2 for i in range(n + 1)] # 1부터 인덱스를 사용하기 위해 dp = [[0] * (k + 1) for i in range(n + 1)] # 가방의 크기 * 갯수 for i in range(1, n + 1): weight[i][0], weight[i][1] = map(int, input().split()) for i in range(1, n + 1): for j in range(1, k + 1): if j - weight[i][0] >= 0: # 가방의 크기 - 물건의 크기 >= 0 -> 즉 가방에 넘치지 않게 담을 수 있는가? # 이전의 값(i-1)과 물건을 담기전+물건의 가치 중 큰 것 선택 dp..

    [백준]1912번 연속합 - DP
    SW개발/코딩테스트

    [백준]1912번 연속합 - DP

    n = int(input()) num = list(map(int, input().split())) dp = [0] * n dp[0] = num[0] for i in range(1, n): dp[i] = max(dp[i - 1] + num[i], num[i]) # 직전수+현재수와 현재수를 비교해 큰것을 저장 print(max(dp)) 코드 설명 먼저 n이 1인 경우를 대비해 dp[0]에는 num[0] 값을 넣어준다. 반복문을 통해 직전수+현재수 vs 현재수 중 큰 값을 저장시키면서 반복한다. 저장된 값중 가장 큰 값을 출력하면 연속합중 가장 큰 값을 구할 수 있다. Point : 큰 값을 저장시키기 위해서 직전까지 누적된 합과 현재의 수를 비교하여 큰 것을 저장한다. 이 과정을 진행하는 이유는 직전까지의 ..

    [백준]9251번 LCS - DP
    SW개발/코딩테스트

    [백준]9251번 LCS - DP

    string1 = "0" + input() string2 = "0" + input() dp = [[0] * len(string1) for i in range(len(string2))] for i in range(1, len(string2)): # 두번째 문자열을 한 개씩 반복하기 위해 for j in range(1, len(string1)): if string2[i] == string1[j]: # 만약 같은 문자인 경우 dp[i][j] = dp[i - 1][j - 1] + 1 # BG G -> BGC GC 가 된 경우 "C" 라는 값이 동일하게 들어온 것. # 따라서 대각선 왼쪽의 기억되어있는 값 + 1 else: # 다른 문자인 경우 dp[i][j] = max(dp[i - 1][j], dp[i][j -..

    [백준]2565번 전깃줄 - DP
    SW개발/코딩테스트

    [백준]2565번 전깃줄 - DP

    n = int(input()) line = [[0] * 2 for i in range(n)] for i in range(n): line[i][0], line[i][1] = map(int, input().split()) line.sort(key=lambda x: x[0]) length = [0] * n for i in range(n): length[i] = 1 for j in range(i): if line[j][1] < line[i][1]: length[i] = max(length[i], length[j] + 1) print(n-max(length)) 코드 설명 먼저 전깃줄의 이어진 정보를 line 이차원 리스트에 저장한다. 그 후 한쪽의 전봇대를 기준으로 번호를 정렬하여 준다. n 번의 반복문을 진행하..

    [백준]11054번 가장 긴 바이토닉 부분 수열 - DP
    SW개발/코딩테스트

    [백준]11054번 가장 긴 바이토닉 부분 수열 - DP

    n = int(input()) num = list(map(int, input().split())) dp1 = [0] * n dp2 = [0] * n for i in range(n): dp1[i] = 1 for j in range(i): if num[j] < num[i]: dp1[i] = max(dp1[i], dp1[j] + 1) num.reverse() for i in range(n): dp2[i] = 1 for j in range(i): if num[j] < num[i]: dp2[i] = max(dp2[i], dp2[j] + 1) dp2.reverse() ans = [0] * n for i in range(n): ans[i] = dp1[i] + dp2[i] - 1 print(max(ans)) 코드 설명..

    [백준]11053번 가장 긴 증가하는 부분 수열 - DP
    SW개발/코딩테스트

    [백준]11053번 가장 긴 증가하는 부분 수열 - DP

    n = int(input()) num = list(map(int, input().split())) length = [0] * n for i in range(n): length[i] = 1 for j in range(i): if num[j] < num[i]: length[i] = max(length[i], length[j] + 1) print(max(length)) 코드 설명 LIS 알고리즘을 구현하는 문제이다. 부분 수열의 길이를 저장하는 length 리스트를 [0] * n 의 길이만큼 초기화 한다. 반복문 안에서 기본길이는 1로 만들어 준다. i 번째 전에 존재하는 값들 중에 i 번째의 값보다 큰 수가 존재할 경우에는 현재 i 번째의 수열 길이와 j + 1 의 수열 길이중 큰 값으로 업데이트한다. le..

티스토리툴바