본문 바로가기

전체보기

 (180)
프로그래머스 - 빛의 경로 사이클 30분 내로 풀 거를 이해 잘못해서 3시간 가량 소비한 문제 `_' 단편적인 것만 보고 거기에 맞추느라 고생했다. https://programmers.co.kr/learn/courses/30/lessons/86052 코딩테스트 연습 - 빛의 경로 사이클 각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다. 빛이 "S"가 써진 칸에 도달한 경우, 직진 programmers.co.kr 문제에 중요한 힌트가 하나 있는데 한 격자에서 들어오고 나가는 방향은 언제나 똑같음. 이게 무슨 말이냐면 시작을 왼쪽위에서 아래서부터 하든, 오른쪽 아래에서 위에서부터 하든 도달하는 순서만 다를 뿐이지, 반드시 해당 방향..
0-1 BFS 간단한 BFS문제인줄 알았는데, 일반적인 bfs 그래프 풀이로는 메모리초과나 시간초과가 자명한 문제였다. 나름대로 최적화 기준을 세워서 풀어봤지만 한참을 틀린 뒤 태그를 보고 검색을 해보니 바로 이해가 됐다. 왜 0-1가 붙는데? 간선의 가중치가 0과 1밖에 없어서 그렇다. 즉, 비용없이 정점을 지나는 경우와, 비용을 들여 정점을 지나는 경우로 나뉜다. 이게 되게 난해한 부분이, 매 순간마다 비용없이 정점을 지나는 경우를 고려해 큐에 넣어야 하기 때문에 메모리가 초과되거나, 무한루프를 돌아 시간초과가 나버린다. 해결 방법 덱 자료형을 사용하면 편하다. 다른 자료형을 사용해도 풀 수 있지만, 개인적으론 덱이 편했다. 비용을 들이지 않고 지나는 경우엔, 덱의 선두에 넣어야 한다. 비용을 들이고 지나는 경우엔..
백준 [2065] 나룻배 단순 큐 문제여서 쉽게 생각했다가 한번 꼬이니 쭉 꼬여서 당황한 문제 처음엔 왼쪽과 오른쪽 큐를 만들어 독립적으로 관리했는데 이렇게 되다보니 현재 방향이 왼쪽이냐 오른쪽이냐 구분하는 코드로 너무 길어져서 큐 배열 2개로 만들어서 0, 1로 관리했다. 전체 코드 (스압 주의) 더보기 import java.io.*; import java.util.*; class TimeTable { int order; // 입력된 순서 int arriveTime; // 도착한 시간 public TimeTable(int order, int arriveTime) { this.order = order; this.arriveTime = arriveTime; } public int getOrder() { return order; }..
자바 gc 약한 세대 가설 (weak generational hypothesis) 가비지 컬렉터의 역할1. 메모리 할당2. 참조된 객체가 메모리에 남아있는지 확인3. 런타임 때 더 이상 도달할 수 없는 개체의 메모리 회수 가비지 컬렉터가 실행되는 상황1. 전체 힙 또는 하위 요소가 임계값 이상이 될 때2. 요청한 메모리만큼 힙에서 할당할 수 없는 경우  Compaction가비지 컬렉터가 실행되고 난 후에는 여유 공간들이 연속돼있지 않고, 여러 chunk로 남는다.이는 큰 개체에 대한 할당을 어렵게 만들기 때문에 가비지 컬렉터는 다양한 압축 방법을 지원한다. 가비지 컬렉터의 성능 지표1. 처리량(Throughput) : 충분히 긴 시간동안 가비지 콜렉터 수행 시간을 제외한 런타임 비율2. overhead : 1번의 반대. 가비지 컬렉터의 수행 시간 비율3. pause time : 가비지..
백준 [2589] 보물섬 c++ 기준 단순 bfs로 푼다면 100~120ms의 시간으로 풀 수 있지만, 그래프 지름에 대해서 생각해 본다면 더욱 빠르게 풀 수 있다. (20ms정도) 1이 육지, 0이 바다라고 하고 지도가 다음과 같다면 3가지 조건에 대해 생각해볼 수 있다. 1. 어떤 지점의 위, 아래에 땅이 있을 때 빨간 곳처럼 위 아래로 땅이 있는 경우, 해당 지역은 단순히 거쳐가는 지역이된다 실제로 찍어보면 알겠지만 해당 지점에서 시작한 거보다 그 위 아래에서 시작한게 더 크다 2. 어떤 지점의 좌우에 땅이 있을 때 이 부분도 마찬가지로 좌우에서 시작한게 해당 지역에서 시작한 거보다 더 크다 3. 상하, 좌우가 아닌 2갈래로 퍼지는 곳 위 오른쪽, 위, 왼쪽 처럼 x,y 축으로 한 방향씩 갈라지는 곳이다 사진처럼 아래, 오..
백준 [1806] 부분합 www.acmicpc.net/problem/2003의 응용 문제 사실 응용문제랄 것도 없이 if문 하나만 추가해주면 끝난다. 여기서 주의할 점은 부분합이 S 이상을 찾는 것이다. 부분합이 S인 경우만 찾으면 안 된다. 생각보다 간단하다. 합이 S 이상인 경우, 시작점과 마지막 점의 차이를 구한 후, 이 차이가 최소값이지만 판별해주면 된다. 더보기 #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int N, S, data, MINLEN = 0x7FFFFFFF; int start = 0, end = 0, sum = 0; vector v; cin >> N >> S; for (in..
백준 [11657] 타임머신 음수 사이클이 있는 벨만 포드 알고리즘 문제 음수 사이클 탐지 구현 다 해놓고 예제도 다 맞았는데 자꾸 틀려서 뭔가 했는데 이분이 올린 테스크 케이스들 보고 알았다. www.acmicpc.net/board/view/39180 틀린 코드 더보기 #include #include #include using namespace std; #define INF 0x7FFFFFFF vector v[512]; long long upper[512]; int Bellman(int N) { int i, size, there, thereCost; upper[1] = 0; for (i = 1; i > N >> M; for (int i = 0; i > A >> B >> C; v[A].push_back..
docker linuxKit 도커 toolBox 초기 Mac이나 Window에선 리눅스 환경에서 도커를 구동해야함 toolBox란 VMware같은 툴로 리눅스 가상환경을 구축 후, 그 위에 도커 실행 컨테이너에 접근하기 위해선, hostOS -> 가상 머신 -> container를 거쳐야 하기 때문에, 이중으로 포트포워딩을 해야 함 linuxKit Mac과 Window가 자체적으로 가상화된 리눅스 환경을 제공하기 위해 사용하는 툴 한 번의 포트포워딩만으로 외부에서 컨테이너에 접근할 수 있게 해준다. Mac : Xhyve(Hyperkit) window : hyper -v hyper -v 하이퍼바이저의 type1 형태로, 윈도우 커널과 리눅스 커널이 담긴 2개의 컨테이너를 만듬 Client는 window로 둔 상태에서 Docker Da..

티스토리툴바