우디의 성장일기

programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 로직 BFS를 이용하여 1에서 각 노드까지의 최단거리들을 구하고 그 중 가장 긴 거리를 가진 노드 개수를 카운트하여 리턴해주었다. 코드 import java.util.*; class Solution { public int solution(int n, int[][] edge) { int[] distances = new int[n+1]; distances[1] = 1; Hashtable edgeInfo = new Hashtable(n); // ini..

programmers.co.kr/learn/courses/10302/lessons/62951 [Java/문제풀이] 코딩테스트 광탈 방지 Kit: Java편 - Step 1. 게임 맵 최단거리 직접 풀어보기 × 프로그래머스의 모든 동영상 강의는 구매 후 열람 기간 제한이 없습니다. 또한 이 강의는 Java 기반으로 준비되어 있느니 해당 언어에 대한 지식은 필수입니다! 코딩테스트 준비,당신만 힘든게 programmers.co.kr 로직 그렇게 어렵지는 않았다 최단거리 문제는 보통 BFS가 유리하다. 단 path를 다 기억해야하는 경우에는 DFS 방식을 사용하는 것이 좋다. 처음에는 x, y좌표를 어떻게 queue에 넣을까 하다가 그냥 Node라는 inner class를 만들어서 진행했다. (inner Cla..

3차례에 걸쳐.... 완성된 코드... 로직 실패한 코드라 의미없을 수도 있겠지만 간단하게 말하면, 전체 리스트에서 k 만큼의 길이로 쪼개 만들어진 리스트를 subList라고 가정하자 예를 들어, { 2, 4, 5, 6, 2, 1, 4, 2 } 라는 전체 리스트가 주어지고 k = 3이라고 가정하면 subList는 {2, 4, 5}, {4, 5, 6}, {5, 6, 2}, ... 이 된다. 그리고 각 subList에서 max값을 찾고, 그렇게 구한 subList max값들 중 가장 작은 값을 선택한다. 가장 작은 값이 곧 최종적인 리턴값이 된다. 설명하기 좀 복잡해서 자세한건 나중에 (아이패드로 설명하자) 아무튼 선형탐색이라서 O(n^2)이 걸린다. 테스트 케이스 모두 돌아가는데 정확도 테스트 13번이라는..

programmers.co.kr/learn/courses/30/lessons/64065 코딩테스트 연습 - 튜플 "{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4] "{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4] "{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1] programmers.co.kr 로직은 쉬웠지만... 자바로 문자열 처리하는게 오랜만이라 시간이 좀 걸렸다. 로직 #2 코드 로직으로 적겠다. s는 하나의 스트링형태로 되어있기 때문에 "{"와 "}"를 모두 제거하고, ","를 기준으로 분할하여 숫자들만 모아 하나의 list로 만든다. 숫자를 카운트 하여 카운트 정보를 Hashtable에 넣어준다(Hasht..

programmers.co.kr/learn/courses/30/lessons/1829 코딩테스트 연습 - 카카오프렌즈 컬러링북 6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5] programmers.co.kr 코드를 쓰는데는 그렇게 시간이 오래 걸리지 않았지만 int[][] picture를 long[][] 타입으로 바꾸어야 정확도 테스트를 통과하기 때문에 그걸 몰라 애를 먹었다.. 사실 왜 이렇게 바꿔야하는지도 잘 모르겠지만..ㅠ picture의 원소는 0 이상 2^31 - 1 이하의 임의의 값이다. 라고 되어있었기 때문에 picture 원소들은 모두 int범위 내에 존재할텐데.. 호..

programmers.co.kr/learn/courses/30/lessons/64061 코딩테스트 연습 - 크레인 인형뽑기 게임 [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]] [1,5,3,5,1,2,1,4] 4 programmers.co.kr 맨 처음 이 문제를 봤을 때가 기억난다..ㅎㅎ 데이터 구조 배우기도 전에 멋모르고 도전했던 카카오 코테...ㅋ 무참히 깨졌었지... 지금 보니까 쉬운 문제인데 그때는 한숨만 나왔는데ㅋㅋㅋㅋ 취준하면서 나의 무능함을 깨닫고 있는 와중에 이런 느낌.. 나쁘지 않은걸 나.. 헛살진 않았나보다 헛헛😂😂 이제 푸는 것 이상으로 효율! 클린 코드!! 노력해야지요 또 한 번의 마일스톤에서 나를 되돌아 봤을 때 성장..

로직 탐색하려는 letter가 현재 skill안에 있는지 없는지 O(1)시간으로 확인하기 위해서 set을 만든다 skill_trees를 선회하면서 skill_tree의 각 요소들이 skill 순서에 맞게 나열되어있는지 확인한다. 각 skill_tree를 확인할 때마다, skill의 위치를 나타내는 index를 0으로 세팅해준다. 현재 탐색하려는 letter가 skill 안에 있는지를 확인하고 없으면 pass하고 다음 letter~ 있으면 아래의 작업을 수행한다. letter == skill[index] 일 경우에는 정상상태이므로 index ++ 해주고 pass하고 다음 letter~ letter != skill[index] 일 경우에는 잡았다 요놈.. count-- 해주고 break 그리고 index가 ..

교착상태(deadlock) 2개 이상의 스레드 혹은 프로세스가 서로 상대방의 작업이 종료되기 만을 기다리는 상태. 즉, 절대로 참이 될 수 없는 조건을 기다리면서 정지되어있는 경우를 말한다. 상호 배제 : 공유 자원에 대해 배타적인 접근권을 요구한다. 점유 대기 : 프로세스 혹은 스레드가 할당된 자원을 점유한 채 다른 자원을 기다린다 비선점 : 프로세스 혹은 스레드가 할당된 자원의 사용을 끝낼 때까지 다른 작업이 그 자원을 차지할 수 없다. 순환 대기 : 각 프로세스 혹은 스레드가 순환적으로 다음 프로세스 혹은 스레드가 요구하는 자원을 가지고 있다. 이에 대한 쉬운 예시가 '식사하는 철학자 문제' 이다 다섯 명의 철학자들이 원탁에 둘러앉아 각각 하나의 젓가락을 가지고 있는 상태이므로 어느 누구도 젓가락 ..

뮤택스(Mutax) == Binary Semaphore 임계구역(critical section)에 하나의 스레드 혹은 프로세스만 들어갈 수 있다. 키를 통해서 뮤텍스를 잠그거나(locking) 여는(unlocking) 두 가지 상태를 취하여 상호 배타성을 제공한다. 세마포어(Semaphore) == Counting Semaphore 임계구역(critical section)에 여러 개의 스레드가 들어갈 수 있다. 세마포어 s는 몇 개의 스레드가 해당 임계구역에 접근할 수 있는지를 나타내는 전역 변수이다( 비음수 정수 값 ). 이는 P와 V라는 특정 연산을 통해서만 조작이 가능하다. 간단히 말하면 P는 임계구역으로 진입할 때, V는 임계구역을 빠져나올 때 수행하는 연산이다. P(s) : wait(s) { w..

스레드 ( Thread ) 하나의 프로세스에 여러 개의 쓰레드 생성이 가능하다. 또한 동시에 여러 개의 쓰레드를 병렬적으로 실행할 수 있다. 프로세스 안에 있기 때문에 프로세스의 데이터에 모두 접근이 가능하기 때문에 자원을 효율적으로 공유할 수 있다. 쓰레드는 프로세스(가상 메모리) 내부에서 별도의 stack 영역, stack pointer 등을 포함하는 별도의 쓰레드 컨텍스트를 가진다. 이외에 Heap, bss, data, code 세그먼트는 모든 쓰레드가 공유하고 있다. (리눅스에서는 Light weight process라고도 불린다). 멀티 스레드 ( Multi Thread ) 소프트웨어 병행 작업 처리를 위해 이용하는 기법이다. 프로세스를 여러개의 Thread로 분할하고 분할된 thread들을 병..