문제 링크 : https://softeer.ai/practice/6266 사용 언어 : JAVA 내 생각 초기 생각 처음에는 HashMap를 만들어서 회의 시간마다 true로 체크하고, 출력할 때 다시 계산하는 방식을 사용하려 했다. 그런데 회의실이 빈 start시간, end시간을 일일이 구하는게 너무 귀찮아서 다른 방식을 생각했다. 개선 회의가 (9-10), (12-13), (16-17) 이렇게 있다면, 회의실이 비어있는 시간대는 (10-12), (13-16), (17-18) 이렇게 된다. 아래의 (1)처럼 주어진 회의 시작/종료 쌍을 (2)처럼 변경하여 새로운 쌍을 짓는 것이다. (1) (회의1 시작, 회의1 종료) / (회의2 시작, 회의2 종료) / ... / (회의N 시작, 회의N 종료) (2)..
가상환경 생성 및 활성화virtualenv 설치프로젝트 폴더 하나 생성 후$ pip install virtualenv가상환경 만들기// python 3.7 이상$ python -m venv myenv// python 3.7 이하$ virtualenv myenv가상 환경 활성화$ source myenv/Scripts/activate하면 하단에 (myenv)가 에코되면서 가상 환경 활성화가 완료된다.VSCode 인터프리터 선택(반드시 가상 환경이 활성화된 상태에서 진행)ctrl+shift+p → python interpreter → ‘myenv’: venv후에 터미널 창 (git bash) 열면 자동으로 가상 환경이 활성화된다. django 설치$ pip install django==3.2.12반드시 버전을..
문제 링크 : https://www.acmicpc.net/problem/14500 사용 언어 : JAVA 내 생각 초기 생각 모든 N X M 칸을 돌면서 5가지 테트로미노를 모두 대조, 최댓값을 갱신한다. 근데 테트로미노의 블록들을 회전시키는 함수를 짜는게 까다로워서,, 그냥 회전으로 만들 수 있는 모든 모양을 2차원 배열로 만들어서 돌렸다. 그래서 이 정보를 담을 ArrayList 를 생성하고 수기로 열심히 넣어줌 코드는 아래와 같다. 더보기 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTok..
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/49191 사용 언어 : JAVA 내 생각 초기 생각 처음에는 Topology Sort를 활용한 문제인 줄 알았는데 아무리 생각해도 정렬을 하고서 어떻게 순위를 계산할 방법이 떠오르지 않았다... 결국 구글 신의 도움을 받고, "플로이드 와샬"을 활용해야 한다는 것을 알게되었다. 적용 어떻게 플로이드 와샬을 사용할 수 있을까? 일단 2차원의 인접 배열을 만든다. 그리고 가중치를 세가지를 사용할 것인데, 각각 1, 0, -1이다. (사실 값은 중요하지 않고 세가지 상태를 나타낼 수 있으면 된다) array[A][B] == ? 1: A가 B를 이긴다 0: 알 수 없다. -1: A가 B에게 진..
링크 : https://school.programmers.co.kr/learn/courses/30/lessons/86053 사용 언어 : JAVA 풀이 변수, 조건 정리 a : 신도시에 필요한 금 총량 b : 신도시에 필요한 은 총량 g[i] : i번째 도시가 가지고 있는 금 총량 s[i] : i번째 도시가 가지고 있는 은 총량 w[i] : i번째 도시가 트럭에 적재할 수 있는 최대 적재량 t[i] : i번째 도시에서 신도시까지 편도로 이동 시 걸리는 시간 각 도시에서 출발하는 모든 트럭은 동시에 운행할 수 있으며, 마지막까지 움직이는 트럭의 이동 시간까지만 구하면 된다. 아이디어 목표 금 a kg과 은 b kg을 전달할 수 있는 가장 빠른 시간을 구한다. 이럴 때 사용할 수 있는게 이분 탐색이다. 스무..
위상 정렬(Topological Sorting)정의방향 그래프에서 각 정점들이 어떤 순서로 방문되어야 하는지를 결정하는 알고리즘.그래프에서 어떤 정점이 다른 정점에 의존하는 관계가 있을 때, 그래프를 순서대로 방문하기 위해 위상 정렬을 사용할 수 있다.위상 정렬은 다양한 분야에서 사용된다. 예를 들어, 컴파일러에서는 소스 코드의 의존성을 파악하기 위해 위상 정렬을 사용한다. 그 외에도 작업 스케줄링, 프로젝트 관리, 그래프 이론 등 다양한 분야에서 유용하게 사용된다. 예제https://www.acmicpc.net/problem/14567선수과목처럼 어떤 상태에 도달하기 위해 우선적으로 도달해야 할 상태가 있고, 이것을 준수한 채 모든 정점을 방문할 수 있는 순서를 구하는 것이다. 해당 문제에서는 그래프의..
Page Fault 가상메모리에서 물리 메모리에 올려두지 않은 페이지에 대한 요청이 들어와 발생하는 예외 페이지 폴트가 발생하면 운영 체제는 그 데이터를 메모리로 가져와서 마치 페이지 폴트가 전혀 발생하지 않은 것처럼 프로그램이 계속적으로 작동하게 해준다. 원인 Major Page Fault 요청한 페이지가 물리 메모리로부터 page-out 되어 보조기억장치의 가상 메모리에 저장되어있다면 해당 페이지를 다시 물리 메모리로 page-in 해야 하는데 이것을 major page fault라고 한다. major page fault는 Disk I/O를 발생시킨다. Minor Page Fault 요청한 페이지가 물리 메모리에는 로드되었지만 MMU에는 로드되어있지 않다고 표시된 경우 이를 Minor page fau..
Virtual memory 프로세스 전체가 메모리에 올라와 있지 않아도 실행이 가능하도록 하는 기법 당장 실행에 필요한 부분만 주기억장치(RAM)에 저장하고, 나머지는 보조기억장치(HDD)에 두고 동작하도록 하는 방법. 프로세스의 일부 메모리만 올려서 전체 프로세스를 병렬적으로 돌리게 함. 물리적 메모리에 제약을 덜 받으며 더 많은 프로세스를 한꺼번에 돌릴 수 있다. 장점 프로그래밍 용이성 이용률, 처리율 상성 단점 메모리 디스크 간 이동량 증가 → 속도 떨어짐, 교체 공간 확보 필요 페이지 부재 시 처리 방법 필요 왜 필요한가 프로그램이 실행되려면 우선 주기억장치에 들어가야 하는데, 다음과 같이 크기 5의 프로그램이 실행을 위해 크기 10의 주기억장치로 들어갈 때는 아무런 문제가 발생하지 않는다. 하지..
아래 프로그래머스 문제를 풀다가 발견한 문제이다. 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 대충 나는 kruskal 알고리즘을 사용하였고, union find 부분의 함수를 구현하고 있었다. 그런데 분명 TC도 다 맞고 로직 상의 문제는 없었을 코드가 계속 정확도 50점이 나왔다. 문제가 될 부분이 union find 밖에 없었기 때문에 수정하기 위해 IDE로 옮겼더니 인텔리제이가 힌트를 줬다 ^^; // 문제에서 vertex의 번호가 0~N 범위 밖일 수 있기 때문에 parent 정보를 HashMap으로 만들어 저장했다. // key: vertex..
Prim VS Dijkstra두 알고리즘은 동작 방식은 비슷하지만 사용의 목적이 다르다.특징프림 알고리즘다익스트라 알고리즘목적최소 신장 트리(MST) 생성출발점으로부터 각 노드까지의 최단 경로 탐색비슷한 알고리즘Kruskal벨만 포드, 플로이드 와샬결과모든 노드를 최소 비용으로 연결하는 트리출발 노드에서 다른 노드로 가는 최단 거리간선의 가중치음수 간선 허용 가능음수 간선 허용 불가시작점시작점은 임의의 노드여도 무관출발점이 명확하게 정해져야 함중간 목표매 단계에서 MST에 포함되지 않은 가장 비용이 적은 간선을 선택매 단계에서 출발점으로부터 최단 거리 노드를 선택동작 방식1. 특정 노드를 MST에 추가2. 해당 노드(MST 대표)에서 다른 노드들 까지의 거리를 구함 -> dist[]3. dist[] 기준..
