소프트웨어 이론

[Java] LIS, LCS

작성자:
Featured image for [Java] LIS, LCS

  1. LIS란? 2. LIS의 길이 구하기 동적 계획법으로 최장증가수열의 길이를 구하는 방법에 대하여 알아보자. 최장 증가 부분 수열 최장 증가 부분 수열 문제는 동적 계획법 으로 풀 수 있는 유명한 알고리즘 문제이다. 정의 어떤 임의의 수열이 주 설명 참고. 가. O(N^2) 이 알고리즘에서, dp[i]는 배열의 i번째 요소를 마지막으로 하는 LIS의 길이를 저장한다. 배열의 모든 … 더 읽기

[Java] Knapsack

작성자:
Featured image for [Java] Knapsack

1. Knapsack Knapsack 문제는 조합 최적화 문제의 일종으로 주어진 물건들의 가치와 무게, 그리고 배낭의 총용량이 주어졌을 때, 배낭에 넣은 물건들의 가치의 합이 최대가 되도록 하는 물건들의 부분집합을 찾는 문제이다. 동적 계획법(Dynamic Programming)으로 풀 수 있다. 2. 공간 복잡도 개선 기존의 동적 계획법(DP)은 O(NK)의 공간 복잡도를 가지고 있다. (여기서 N은 물건의 개수, K는 배낭의 최대 무게를 … 더 읽기

[컴퓨터구조론] 마이크로-프로그램

작성자:
Featured image for [컴퓨터구조론] 마이크로-프로그램

1. 제어 유니트의 기능 명령어들을 인출하여 해독하고 실행하는 과정이 순차적으로 발생되도록 하기 위해서 그 순간마다 적절한 제어 신호들이 생성되어 해당 하드웨어 모듈로 보 내져야 한다. Control Unit. (a.k.a CU)는 … 컴퓨터 프로그램을 구성하고 있는 명령어들을 해독하고, 그 결과에 따라 명령어 실행에 필요한 동작들을 수행시키기 위한 제어 신호들을 발생하는 장치이다. 즉, 명령어 사이클이 적절히 수행되도록 모든 … 더 읽기

[컴퓨터구조론] 컴퓨터의 구조과 설계 1

작성자:
Featured image for [컴퓨터구조론] 컴퓨터의 구조과 설계 1

0. Basic Computer 아래 모든 설명은 Basic Computer를 기준으로 진행한다. 1. 명령어 코드 (Instruction Codes) 컴퓨터의 동작은 레지스터 내에 저장된 데이터에 대한 마이크로 연산의 시퀀스에 의해 정의된다. 항목 설명 프로그램 사용자가 원하는 연산과 피연산자가 처리되는 순서를 기술한 컴퓨터 명령어의 집합 컴퓨터 명령어 컴퓨터에 대한 일련의 마이크로 연산을 기술 마이크로 연산 레지스터에 저장된 데이터를 가지고 실행되는 … 더 읽기

[알고리즘] 2457. 공주님의 정원

작성자:
Featured image for [알고리즘] 2457. 공주님의 정원

0. 문제 2457번: 공주님의 정원 1. 문제 이해 회의실 배정(Activity-Selection) 문제는 아닌 것 같다. 2. 제출 어떤 것을 기준으로 정렬할지 판단하는 것이 어려웠다. 3월 1일부터 11월 30일까지 하루도 빠짐없이 꽃을 피워야 하기 때문에 꽃이 피는 날이 빠른 순서로 정렬했다.

[알고리즘] 풀었던 문제 (240227 ~ 29)

작성자:
Featured image for [알고리즘] 풀었던 문제 (240227 ~ 29)

11726. 2 x n 타일링 11726번: 2×n 타일링 11727. 2 x n 타일링 2 11727번: 2×n 타일링 2 5653. 줄기세포배양 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! 1941. 소문난 칠공주 1941번: 소문난 칠공주

[알고리즘] 2383. 점심식사시간

작성자:
Featured image for [알고리즘] 2383. 점심식사시간

0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! 1. 문제 이해 2. 제출 이런 소위 “시간 관리”를 해야 하는 문제는 보통 특정 상황에서 어떻게 동작하는지 자세하게 분석해 준다. 올바르게 구현했는지 확인하기 위해서 모든 부분집합에 대하여 실행하지 말자. go(new int[]{0,0,0,1,1,1}, true);로 예시와 동일한 상황으로 테스트하는 것이 도움이 되었다. “시간 … 더 읽기

[알고리즘] 1767. 프로세서 연결하기

작성자:
Featured image for [알고리즘] 1767. 프로세서 연결하기

0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! 1. 문제 이해 2. 제출 가. 오답 근본 없이 풀었다. 완탐으로 풀면 비효율적이라고 생각해서 그랬다. 나. 완전 탐색으로 풀기 진짜 일부의 유명한 그리디 알고리즘을 제외하고선 완전탐색으로 풀자.주어진 시간 안에 문제를 풀어야 하는데 머리 아프게 고민할 시간이 없다.근본 있게 풀기.