JOHOONDAY
본문 바로가기
728x90

전체 글140

백준 No.1944 [복제 로봇] 백준 No.1944 [복제 로봇] 문제 1944번: 복제 로봇 (acmicpc.net) 1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net 설명 * MST * BFS 위와 같은 테스트 케이스가 있다고 하자! 먼저, bfs 를 통해 위와 같이 하나의 시작점과 각 Key 들이 이루는 그래프를 구했다. 그래프의 간선들은, 연결된 두 노드의 최소 거리이다. Key는 최대 250개, 지도 크기는 최대 50 * 50 == 2,500 이니까, Key 하나하나 2,500 크기의 맵을 BFS 해도 .. 2023. 2. 5.
[Java] 자료형 (Data type) [Java] 자료형 (Data type) boolean, byte, short, int, long, char, float, double, String 설명 참거짓 ( boolean ) boolean bool1 = true; // 1bit System.out.printf(" Print bool1 : %b\n", bool1); 정수형 ( byte, short, int, long ) byte byte1 = 2;// 1 byte short short1 = 4;// 2 byte int int1 = 1;// 4 byte long long1 = 9000000000000000000L;// 8 byte System.out.printf(" Print byte1 : %d\n", byte1); System.out.printf.. 2023. 1. 19.
인오더, 프리오더, 포스트오더 (Inorder, Preorder, Postorder) 인오더, 프리오더, 포스트오더 (Inorder, Preorder, Postorder) 이진 트리를 순회하는 세 개의 방법 정의 이진 트리(Binary Tree) 를 순회(Traversal)할 때 위와 같이 세 가지 방법이 존재한다. Inorder (중위 순회) : left Node -> root Node -> right Node preorder (전위 순회) : root Node -> left Node -> right Node postorder (후위 순회) : left Node -> right Node -> root Node 중위 순회 (Inorder Traversal) left Node -> root Node -> right Node 순서로 순회한다. 위 트리에선 (1) -> (3) -> (4) ->.. 2023. 1. 15.
이진 트리 (Binary Tree) 이진 트리 (Binary Tree) 정의 임의의 노드의 자식 노드가, 최대 2개를 넘지 않는 트리 설명 컴퓨터 과학에서 정말 많이 사용되는 자료구조이다. 임의의 노드의 자식 노드가, 최대 2개를 넘지 않는다. 또한 이진 트리에서 부트리(Sub-Tree) 또한 이진 트리이다. Root : Tree의 최상위 노드 Parent / Child : 위 예시에서 임의의 노드 A노드는 B, C 노드의 Parent 이며, B, C 노드는 A 노드의 Child 노드이다. Sibling : 같은 Parent 노드를 가진 두 노드 Leaf Node : Child 노드가 없는 노드 Depth : 임의의 노드에서, Root 노드 까지의 간선의 수 Height : 최대 Depth의 값 Sub Tree : 트리에서, 임의의 노드를.. 2023. 1. 14.
2023년 상반기 삼성 신입사원 입문교육, SVP 후기 2023년 상반기 삼성 신입사원 입문교육, SVP 후기 2022년 12월 26일 ~ 2023년 1월 6일 코로나 이후, 처음으로 2주 전면 오프라인 SVP가 진행되었다. 1주차는 고양에 있는 연수원에서, 2주차는 유명한 창조관에서 진행되었다. 모든 것들의 시작이 그렇듯, 기대 반 걱정 반 으로 시작되었다! 한 조에 10명 남짓으로 여러개의 조가 구성되었다. 원래는 한 조에 더 많은 분들이 함께 했어야 했지만, 코로나 때문에 몇몇 분들이 함께하지 못한 아쉬움이 있다. 모두 대강의장에서 모여 2주간의 일정에 대한 소개를 받고, 각 팀을 이끌어주시는 선배님들을 뵙고 팀원들과 친해지는 시간을 가졌다. 우리팀은 나 혼자 SDS, 두 분은 SDI, 나머지 분들은 전자였다. 혼자 SDS인 점이 좀 아쉬웠지만, 그래도.. 2023. 1. 8.
백준 No.2008 [사다리 게임] 백준 No.2008 [사다리 게임] 문제 2008번: 사다리 게임 (acmicpc.net) 2008번: 사다리 게임 사다리 게임을 할 때 사용되는 사다리가 있다. 세로선은 N개가 있고, 가로선은 M개가 있다. 세로선은 맨 왼쪽 것부터 1, 2, …, N의 번호가, 가로선은 맨 위의 것부터 1, 2, …, M으로 번호가 붙어 있 www.acmicpc.net 설명 * dp 2차원 dp 를 이용하여 풀이가 가능하다. dp[i][k] : i 번째 가로선까지 체크를 했을 때 시작점에서 k 번째 세로선까지 오기까지의 최소비용 위 값을 결정하기 위해선 이전 dp 값의 왼쪽, 현재 위치, 오른쪽 인 dp[i - 1][k - 1], dp[i - 1][k], dp[i - 1][k + 1] 을 고려한다. 1) dp[i - .. 2022. 12. 4.
백준 No.1167 [트리의 지름] 백준 No.1167 [트리의 지름] 문제 1167번: 트리의 지름 (acmicpc.net) 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 설명 * DFS 백준 No.1967 [트리의 지름] (tistory.com) 백준 No.1967 [트리의 지름] 백준 No.1967 [트리의 지름] 문제 1967번: 트리의 지름 (acmicpc.net) 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온.. 2022. 11. 28.
백준 No.1967 [트리의 지름] 백준 No.1967 [트리의 지름] 문제 1967번: 트리의 지름 (acmicpc.net) 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 설명 * DFS 트리의 지름은 트리의 정점들간 경로들 중 가장 긴 거리를 말한다. DFS를 통해 크게 두 단계로 해결할 수 있다. DFS를 통해 임의의 정점에서 가장 먼 정점을 확인한다. DFS를 통해 위 확인된 정점에서 가장 먼 정점까지의 거리가 트리의 지름이다. 저 방법으로 어떻게 트리의 지름이 구해질까? 위 경우는 [A 정점]에서 가장 먼 정점이 .. 2022. 11. 28.
백준 No.1725 [히스토그램] 백준 No.1725 [히스토그램] 문제 1725번: 히스토그램 (acmicpc.net) 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net 설명 * 스택 스택 자료구조를 이용하여 히스토그램 그래프상에서 가장 넓은 직사각형을 구하는 문제이다. 아래 특징을 고려해야 한다. [특징] 1. k 번째 값을 입력받았을 땐, k - 1 번째 값까지 다뤄진 stack 을 다룬 뒤, 마지막으로 k 번째 값을 stack에 push 한다. => k 번째 값은 그대로 push 되는게 아니라, stack에서.. 2022. 11. 13.
프로세스(Process)란? 프로세스 (Process) 정의 디스크에 정적으로 존재하는 실행파일을 실행하면, 메모리에 업로드가 되면서 동적 상태가 된다. 이 상태를 프로세스(Process)라고 한다. 설명 # Stack 영역 지역 변수 (Local variable), 매개 변수 (Parameter), 리턴 주소 등의 값들이 저장된다. # Heap 영역 프로그램이 실행되는 동안 동적으로 할당되는 메모리 영역이다. # Data 영역 (BSS, Gvar) Data 영역은 BSS (Blocked Stated Symbol) 과 Gvar (Global Variable) 로 나뉜다. 초기화가 된 데이터는 Gvar 영역에, 초기화가 아직 되지 않은 데이터는 BSS 영역에 저장이 된다. # Text 영역 컴파일 했을 때 발생한 기계어들이 저장되어 .. 2022. 10. 29.
프로세스 스케줄링(Process scheduling) 프로세스 스케줄링(Process scheduling) 정의 CPU의 사용률을 최대화 시키기 위한 멀티 프로그래밍의 수단이다. 모든 프로세스들을 동시에 실행하기 위한 작업이다. 설명 실제로는 한 CPU에선 한 프로세스만 실행이 가능하지만, 프로세스들에 해당되는 CPU 코어를 계속해서 신속하게 바꿔줌으로써 (Time sharing) 사용자의 입장에선 모든 프로세스가 계속해서 실행되는 것 처럼 보이게 한다. [Time sharing] 짧은 간격으로 CPU에 각 프로세스를 할당하여 사용자의 입장에선 마치 실행되고 있는 프로세스들이 모두 동시에 동작하고 있는 것 처럼 만드는 것 이다. 이러한 Process Scheduling을 위한 Queue는 3가지가 존재한다. * Job Queue - 현재 시스템 내에 있는 .. 2022. 10. 27.
프로세스(Process)와 스레드(Thread)의 차이 프로세스(Process)와 스레드(Thread)의 차이 Process 프로세스란? : HDD나 SSD와 같은 디스크에 저장되어 있는 프로그램을 구동하여 프로그램 자체와 상태가 메모리에 적재되어 실행되는 작업 단위이다. 프로세스를 생성하게 되면 Kernel 공간에 PCB(Process Control Block)이 만들어진다. * Register section - CPU가 프로세스를 처리하는 과정에서 필요한 정보를 임시로 기억하는 저장장소 - 컨텍스트 스위칭(Context Switching)에 관여한다. * Stack section - 지역 변수 (Local variables), 매개 변수 (Parameter), 리턴 주소 등의 값들이 저장된다. - 프로그램이 종료될 시 자동으로 값이 반환된다. * Heap.. 2022. 10. 21.
백준 No.1167 [트리의 지름] BOJ No.1167 [트리의 지름] 문제 1167번: 트리의 지름 (acmicpc.net) 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 설명 * Tree * DFS 트리의 지름이란, 트리 상에서 가장 먼 거리를 가지는 두 정점 사이의 경로이다. 위 예시 트리에서 H 노드와 G 노드 사이의 거리는 23이며, 이 경로가 트리의 지름이 된다. 트리의 지름은 다음과 같은 순서로 구해진다. 1. DFS를 통해 임의의 정점(x)으로부터 가장 먼 정점(y)을 구한다. 2. DFS를 통해 구해진 (y).. 2022. 7. 13.
백준 No.10986 [나머지 합] BOJ No.10986 [나머지 합] 문제 10986번: 나머지 합 (acmicpc.net) 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 설명 * 구간 합 (Prefix sum) 구간 합을 간단하게 활용 한 문제이다. 참고 Link : 2022.04.19 - [Algorithm (C++ based)/Algorithm 이론] - 구간 합 (Prefix sum) 만약 4번째 원소 (index == 3) 부터 19번째 원소 (index == 18) 까지 구간 합이 .. 2022. 4. 19.
구간 합 (Prefix sum) 구간 합 (Prefix sum) array 에서 누적 합을 통해 구간 합을 구할 수 있다. 정의 Array 에서 누적 합을 통해 원하는 구간의 합을 구할 수 있다. 설명 1차원 Array 에서의 구간 합 arr Array 는 1차원 배열이고, sum Array 는 0 번째 index 를 가지는 원소부터 그 index 값의 원소까지의 누적 합 배열이다. 위와 같이 3번째(index == 2) 원소 부터 7번째(index == 6) 원소 까지의 구간 합을 구하고 싶으면? sum[6] - sum[1] 을 하면 구할 수 있다 ;) 관련 Code sum[0] = arr[0]; for (int i = 1; i < n; i++) { sum[i] += sum[i - 1] + arr[i]; } // 6 ~ 17 번째 원.. 2022. 4. 19.
728x90