CPU란? 프로그램의 명령을 수행하는 컴퓨터 내의 중앙 처리 장치를 의미합니다. CPU burst, I/O burst, CPU bound process, I/O bound process 프로세스는 CPU 작업, I/O 작업이 반복적으로 구성됩니다 CPU 작업 사용자 프로그램 자체에서 수행 사용자 프로그램이 CPU를 직접 가지고 있음 I/O 작업 특권 명령으로 규정 사용자 프로그램이 직접 수행할 수 없고 OS를 통해 수행 운영체제의 커널이 CPU 제어권을 가지고 있음 CPU burst I/O 작업이 끝나고 다음 I/O 요청이 올 때까지 직접 CPU를 가지고 명령 수행 사용자 프로그램이 CPU를 가지고 있음 I/O burst I/O 작업이 요청되고 다시 CPU burst로 돌아가기까지의 작업 운영체제의 커..

E-Box와 S-Box는 추상화된 박스라고 생각 E-Box S-Box CPU Memory 컴퓨터 내부 디스크 프로세스 해당 프로세스의 주소 공간 동기화 이슈 원인 데이터를 읽기만 하면 문제가 생기지 않는다. 하지만 데이터를 읽어와서 수정하고 결과를 다시 저장하는 방식에서는 "누가 먼저 읽느냐"에 따라 결괏값이 달라질 수 있다 경쟁 상태(Race Condition) "여러" 주최가 "하나"의 데이터를 동시 접근하려 할 때를 Race Condition(경쟁 상태)라고 한다. ex) E-Box 2개가 동시에 S-Box 하나에 접근하여 count를 읽게 된다면 원치 않는 값이 나올 수 있다. 이때 E-Box 2개는 서로 "경쟁 상태"에 있다고 한다. 경쟁 상태 가능성 Memory CPU 멀티 프로세서 시스템에서..

오답 노트 & 새로 알게 된 점 3달 전에 해당 문제를 매개 변수 탐색과 bfs를 사용하여 문제를 해결했다. 이번에 다시 풀면서 알고리즘 분류를 보게 되었는데, "분리 집합" 이 있었다. 저번에 풀었던 여행 가자 문제와 비슷한 느낌이 들었다. 여행 가자 라는 문제에서도 분리 집합이라는 키워드가 있었다. 그래서 해당 문제도 union-find 자료구조를 이용해서 문제를 해결했다. 다만 문제에서는 "한 번의 이동에 최대 중량" 을 구하게 된다. 따라서 가중치를 기준으로 내림차순 정렬을 한다. 정렬된 노드들을 앞에서부터 순차적으로 union 한다. union을 하고 나서 start와 end가 이어진다면, 즉, find(start) == find(end)가 되면 이 때 가중치가 제일 큰 값일 때 이동할 수 있기..

오답 노트 & 새로 알게 된 점 이 문제는 두 가지 풀이를 소개해보겠다. 첫 번째 풀이는 제가 처음 접근했던 풀이법이고, 두 번째는 힌트를 얻어 풀게된 "유니온 파인드"를 사용한 풀이법이다. 첫 번째 풀이 문제에서 서로 그래프가 연결되있느냐를 물어보는 것이었다. 따라서 모든 점에서 bfs를 사용하면서 서로 연결이 되어있는지 확인했다. dist[A][B] 배열을 사용하여, A가 출발 노드, B가 거쳐가는 노드라 생각해서 연결리스트를 사용하면서 출발점은 고정하고, 거쳐가는 노드들을 모두 저장했다. 하지만 반례가 존재한다. 문제에서는 갔던 곳을 또 방문할 수 있다. 즉, 이 말은 여행 노드가 1 1 이렇게 나타날 수도 있다. 아마 문제를 푸시다가 80%에서 틀렸습니다 받으신 분들은 이 부분을 놓쳤을 것이다. ..

오답 노트 & 새로 알게 된 점 처음 문제 봤을 때, N,M 범위도 작아서 BFS 돌리면 바로 답 나오겠다 라는 생각이 들었다. 그러나 메모리 초과가 났다. 여기서 아.. 메모리 제한이 작구나 하면서 dfs를 사용하면서 혹시 목적지를 출발지로 설정하고 반대로 가면 괜찮지 않을까라는 생각이 들었지만 당연하게도 TLE가 났다. 그래서 예시 그림을 자세히 보니 중복해서 지나는 부분이 있었고, dp를 사용하면 되겠다라는 생각까지 했다. 하지만 dp 구현을 어떻게 할지 몰라 블로그들의 다양한 풀이를 참고하여 문제를 해결했다. 그래도 이제는 어떤 알고리즘을 사용해야할지 감은 오니까 다행인 것 같다.. 해당 문제와 같은 유형은 (dfs 또는 bfs + dp)는 자주 나올 수 있기 때문에 숙지하고 있어야겠다. 처음에 ..

페치 조인 페치 조인은 SQL에서 사용하는 조인의 종류가 아니다. JPQL에서 성능 최적화를 위해 제공하는 기능이다. 우리는 연관관계에서 지연 로딩을 사용한다. 하지만 페치 조인을 사용하게 되면 즉시 로딩을 하여 N+1 문제를 해결할 수 있다. 페치 조인을 할 때 나올 수 있는 값에 따라 2종류로 나눌 수 있다. 엔티티 페치 조인, 컬렉션 페치 조인 그렇다면 페치 조인을 사용할 때와 사용하지 않을 때를 비교하면서 총 4가지의 예시로 정리해보겠다. 연관관계를 그려보면 아래와 같다. 단일 값 일반 join String query1 = "select m from Member m join m.team"; List resultList = em.createQuery(query1, Member.class) .getR..

영한님 스프링 강의를 들으면서 스트림을 사용하시는 것을 보고, 실무에서도 스트림을 많이 사용하는구나 라는 생각이 들었다 이번 기회에 스트림을 제대로 공부해보고자, 옛날에 들었던 "윤성우의 열혈 Java"를 통해 스트림을 공부하게 됐다. 뭔가 필요한 공부를 하니 강의를 들으면서 더욱 집중할 수 있었고, 빨리 내 프로젝트에 적용해보고 싶은 욕구가 생겼다. 스트림 일련의 과정을 부드럽게 해결하기 위해 사용한다. 물이 흐르면서 필터를 거쳐 우리가 마실 수 있는 물이 되는 것처럼, 데이터가 흐르면서 여러 필터를 거치며 우리가 원하는 데이터를 얻을 수 있다. 스트림은 중간 연산과 최종 연산으로 나뉜다. 중간 연산은 마지막이 아닌 위치에서 진행되는 연산으로, 각각 순서가 바뀔 수 있다. 최종연 산은 마지막에 진행되는..

오답 노트 & 새로 알게 된 점 백트래킹으로 풀어야지 라는 생각을 했지만 구현을 하지 못했다. 구글의 힘을 빌려서 문제를 해결했다,, 처음에 수식의 길이가 N개라고 하여, 숫자는 결국 N / 2 + 1개가 있게 되고, 거기서 -1을 하면 괄호로 묶을 수 있는 수들의 경우의 수가 된다. 이걸 이용해서 순서, 중복 X인 조합을 구하여 계산하려 했지만 하지 못했다. 다른 풀이에서는 백트래킹을 이용한다. 뒤에 괄호가 있다고 생각 or 뒤에 괄호가 없다고 생각한다. 뒤에 괄호가 있다면 현재 idx에서 다음 idx+1, idx+2의 계산한 값과 현재 idx값을 계산해야한다. 그래서 예제 1번을 디버깅 하여 어떻게 계산이 이뤄지는지 손으로 작성해보았다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14..

오답 노트 & 새로 알게 된 점 해당 문제는 풀이 방법이 두 가지 있다. 첫 번째 방법은 생각하기 쉽지만 시간 복잡도가 다른 방법에 비해 크고, 다른 방법은 와 이걸 이렇게도 풀구나 하면서(나만 그럴 수 있음) 시간 복잡도가 첫 번째 방법에 비해 작다. 첫 번째 풀이 일반적으로 다익스트라를 사용한다. 다만 문제에서 출발할 때의 최소 경로 + 복귀할 때의 최소 경로 중 최댓값을 구하라했다. 일반적으로 나는 이와 같은 문제를 풀 때 다익스트라를 모든 정점에서 구한다(N번) 예제에서 start가 1, 3, 4 (2는 파티정점이므로 제외) 일 때 다익스트라를 구하여 각각 dist[X] 값을 더해주고, 또 start가 2일 때 다익스트라를 구하여 각각 dist[N] 을 더해주었다. 그리고 이 중에 최댓값을 구해줬..

오답 노트 & 새로 알게 된 점 해당 문제는 다익스트라를 이용하여 풀면 되는데, 다른 문제와 다른 점은 최소 경로 값을 출력하는 것이 아니라 가장 먼저 거쳐야 할 노드를 출력하는 것이다. 전체적인 풀이를 말하자면 1 ~ N번 노드까지 다익스트라를 구한 뒤, 각 n번 노드마다 parent를 구하여 정답 배열에 넣어준다. 값을 출력할 때는 행과 열이 같은 지점(대각선) 에는 "-" 을 넣어준다. 즉, 1 - 3 - 2가 최소 경로일 때, (1,2)의 값은 3이 된다. 1 ~ N번 노드까지 다익스트라를 이용하여 최소 경로를 구하면서, 최소 경로가 갱신될 때마다 즉, if(dist[node.idx] != node.dist) continue; if(dist[node.idx] + in.wei >= dist[in.t..

오답 노트 & 새로 알게 된 점 이 문제는 (N,M)의 최소 경로가 아닌 벽을 최소로 부수면서 (N,M)에 도착해야한다. 가중치가 0 또는 1이기 때문에 일반적인 BFS를 사용할 수 없다. ( 0-1 BFS 라는 것이 있다) 따라서 가중치가 0을 포함하는 양수일 때 사용하는 알고리즘인 다익스트라를 사용한다. 방문처리는 dist의 값이 현재 방문할 dist값보다 크거나 같게 되면 continue를 한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 ..

오답 노트 & 새로 알게 된 점 이 문제를 푸는데 6시간이 걸린 듯 하다. 총 23트 끝에 문제를 맞게 됐다. 진짜 끔찍하고 무시무시했던 문제였다. 문제를 정리해보면 1. 숫자를 문자열로 풀어서 입력을 줌 2. 문자열을 숫자로 변환하여 계산을 함 3. 계산된 값을 다시 문자열로 풀어야 함 처음에 문자열을 완탐하면서 연산을 배열에 넣어줬다. 왜? 연산의 갯수가 숫자문자열의 개수보다 많다면 잘못된 수식임을 판별하기 위해서이다. StringTokenizer를 이용하여 연산자를 구분자로 문자열을 파싱하면서, 정답을 출력하기 위해 Stringbuilder에 값을 넣어주면서, 숫자를 변환하여 덱에 넣어주었다. 덱에 넣어준 이유는 값을 계산하기 위해서이다 -> 근데 왜 덱을 사용했을까? -> 계산하기 위해서는 두 개..