문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 LIS 라는 DP문제이다. (LIS 알고리즘에 대한 내용은 추후 블로그에 업로드 예정) dp리스트에 현재 자신 숫자를 포함해 만들 수 있는 부분 수열 크기를 저장한다. numList 10 20 10 30 20 50 dp 1 2 1 3 2 4 n = int(input()) numList = list(map(in..
Problem Solving/CT-Python
문제 SWEA-5215. 햄버거 다이어트 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 DFS를 이용해 풀이하였음. 햄버거 재료수(N), 넘지 말아야 하는 칼로리수(L)을 입력받고 리스트를 생성하고 재료의 맛과 칼로리를 저장한 후 재료가 저장된 리스트의 인덱스 0 부터 끝까지 깊이 우선 탐색함. 탐색할때마다 칼로리가 넘어가면 탐색을 수행하지 않고 기존에 저장된 최대 맛보다 크면 갱신 과정을 거침 재료를 썼을 때, 안 썼을 때 를 각각 탐색함. def dfs(index, sTaste, sKcal): global maxTaste # 총 칼로리를 넘으면 리턴 if sKcal > L: return # taste..
문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 다이나믹 프로그래밍으로 푸는 대표적 문제 문제에서 구하고자 하는 값은 정수 X가 주어졌을 때 3으로 나누어 떨어지면 3으로 나누고 2로 나누어 떨어지면 2로 나누고 그 이외는 1을 뺀다. 규칙에 따라 연산 횟수의 최솟값을 구하는 문제다. 처음에 그리디 문제인줄 알고 n//3, n//2 , n-1 순서대로 구하였지만 이렇게 풀면 최솟값을 구할 수 없다. 10을 입력해 위와같이 풀면 10 -> 5 -> 4 -> 2 -> 1 (5번) 여기서 10에 n-1 먼저 계산하면 10 -> 9 -> 3 -> 1 (4..
문제 문제링크 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 주어진 두 수(A, B) 사이 숫자들 중 현재 숫자와 제곱근 수 값이 팰린드롬 수 인 값의 개수들을 구하는 문제 팰린드롬 수는 어떤 단어를 뒤에서부터 읽어도 똑같다면 그 단어를 팰린드롬이라고 한다 6번 라인: 범위를 A부터 B까지 탐색하면서 해당 정수의 제곱근이 정수인지를 체크한다. 7~9번라인: 해당 숫자와 제곱근을 문자열 형식으로 바꿔서 문자열을 뒤집어 팰린드롬 수 인지 확인함 10번라인: 카운트 수 증가 for tc in range(int(input())): A, B = map(int, input().split()) cnt = 0 for ..
문제 https://programmers.co.kr/learn/courses/30/lessons/42842# 코딩테스트 연습 - 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 programmers.co.kr 풀이 문제를 다 풀었지만 테스트케이스 4번에서 자꾸 오류가 났었는데 (이 사람도 나와 같은 문제를 겪었다. https://programmers.co.kr/questions/6882) 30분동안 헤메다가 답을 찾았다. (여기를 참조함 https://programmers.co.kr/questions/11500) 위와 같이 가로가 가장 큰 순서대로 정렬하여..
문제 https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 풀이 처음에는 1일차부터 마지막일수까지 각 날짜마다 점수가 큰 과제를 해결하는 문제인줄 알았는데 접근을 잘못하였고 고민을 오래하여도 답을 찾을 수 없어서 블로그를 통해 아이디어를 얻었다. (여기서 얻었다: https://chinpa.tistory.com/34) 마지막 일수부터 1일차까지 해당 날짜에 수행할 수 있는 가장 높은 과제를 해결하면 된다. 6일차 => [6, 5] 5일차 => X 4일차 => [4, 60], [4, 40], [..
문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 bfs를 이용하여 익은 토마도가 며칠이 지나면 모든 토마토를 다 익는지 구하는 문제다. 먼저 그래프를 돌면서 토마토가 있는 좌표를 큐에 넣고 bfs로 하나씩 pop하면서 토마토가 있는(문제에서는0) 곳에 원소값을 1씩 증가시킨다. 예제 입력이 다음과 같이 주어졌을 때 6 4 1 -1 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 -1 1 gr..
문제 https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 3가지 풀이 방법으로 풀었다. BFS 풀이방법이 실행시간이 제일 짧았으며 그 다음은 DFS, 마지막으로 플로이드-와샬 알고리즘을 사용한 방법이 제일 느렸다. 먼저 BFS로 푼 방법이다. 각 정점마다 방문했는지 visited에 저장하고 간선으로 해당 정점이 연결되어 있다면 check에 1을 기록하였다. 이때 visited는 각 정점을 방문하면서 방문했는지 기록해야 한다. # BFS from collections import deq..
문제 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 풀이 지역의 높이를 리스트로 입력받으면서 가장 큰 값을 찾음 1부터 가장 큰 값까지 물에 잠기지 않는 범위를 DFS/BFS 알고리즘을 통해 찾아서 결과 리스트에 저장 결과 리스트 중에서 가장 큰 값이 문제에서 찾고자 하는 답. # DFS 사용 import sys sys.setrecursionlimit(100000) n = int(input()) graph = [] max_num = 0 result ..
문제 https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net 오답 풀이 (시간초과) 아래 풀이는 시간초과가 발생한 풀이이다. 단순하게 i 번째 원소가 i+1 번째부터 전체 원소까지 탐색할 때 큰 원소를 만나면 인덱스 사이의 거리를 구해 결과에 추가하는 방법으로 코드를 작성하였는데 이렇게 하면 너무 많이 for문을 돌아서 시간초과가 발생한다. import sys input = sys.stdin.readline from collections imp..
