문제 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..
분류 전체보기
학습할 것 프리미티브 타입 종류와 값의 범위 그리고 기본 값 프리미티브 타입과 레퍼런스 타입 리터럴 변수 선언 및 초기화하는 방법 변수의 스코프와 라이프타임 타입 변환, 캐스팅 그리고 타입 프로모션 1차 및 2차 배열 선언하기 타입 추론, var 1. 프리미티브 타입 종류와 범위 그리고 기본 값 프리미티브 타입은 기본 타입으로, 정수형 타입, 실수형 타입, 문자형 타입, 논리형 타입으로 나눌 수 있다. 기본형은 모두 8가지 타입이 있다. 이미지 출처 프리미티브 타입의 설명은 다음 표에 정리하였다. 프리미티브형에는 기본값이 존재해 NULL값이 존재하지 않음. 실제 값은 스택 메모리에 저장되며 저장 가능한 범위를 넘게 값을 저장하면 컴파일 에러가 발생한다. 프리미티브 타입 저장 공간 이미지 출처 프리미티브 ..
문제 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 ..
학습목표 1. JVM이란 무엇인가 2. 컴파일 하는 방법 3. 실행하는 방법 4. 바이트코드란 무엇인가 5. JIT 컴파일러란 무엇이며 어떻게 동작하는가 6. JVM의 구조 7. JDK와 JRE의 차이 1. JVM이란 'Java Virtual Machine' 을 줄인 것으로 자바를 실행하기 위한 가상 기계이다. 이미지 출처 Java는 OS에 종속적이지 않는 특징이 있다. Java가 나오기 전 기존의 언어는 각 운영체제에 맞게 코드를 작성하는 많은 노력이 필요하였지만 Java는 운영체제에 독립적이기 때문에 운영체제가 바뀌어도 동일한 코드로 똑같이 동작한다. 이 이유는 JVM이라는 것 때문이다. 이미지 출처 JVM은 가상 컴퓨터로 독립적인 실행이 가능한데 일반 애플리케이션은 OS와 맞붙어 있어 OS에 종속적..
문제 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..
플로이드-워셜 알고리즘은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다. for문을 3번 사용하기 때문에 시간복잡도 O(N^3)이다. 플로이드-워셜 알고리즘은 2차원 테이블에 최단 거리 정보를 저장한다. (모든 지점에서 다른 모든 지점까지의 최단 거리를 저장해야 하기 때문) 그래프가 다음과 같다고 하자. 모든 정점 사이의 최단 경로를 다음 방법을 통해 찾는다. 1. n*n 2차원인 행렬 A0를 만든다. 여기서 n은 정점(노드)의 개수이다. n*n 배열에서 행, 열은 i, j로 인덱싱 된다. (i와 j는 그래프의 정점(노드) 이다) 2. 각 A[i][j]는 i번째 꼭짓점에서 j번째 정점까지 떨어진 거리로 채워진다. i번째 정점에서 j번째 정점까지 경로가 없으면 해당 원소를 무한대로..
