문제 문제 바로가기> BOJ 1697번: 숨바꼭질 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 기존의 방문한 지점을 제외하고, 이동할 수 있는 총 3가지 방법으로 이동하면서 수빈이가 동생을 찾을 수 있는 가장 빠른 시간을 찾아주면 된다! #include #include #define MAX 100001 using namespace std; int N, K; bool visited[MAX]; int main(){ ios_base::sync_with_stdio(0); cin.t..

문제 문제 바로가기> BOJ 2294번: 동전 2 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 풀이 dp[j] : 가치의 합 j를 만드는 데 사용한 동전의 최소 개수 1. j == coin[i] 인 경우, 동전 하나만으로 j를 만들 수 있으므로, dp[j] = 1 2. j > coin[i] 인 경우, 해당 동전을 사용해서 더 적은 동전으로 j를 만들 수 있는지, dp[j] = min(dp[j], dp[j-coin[i]]+1) #include #define INF 9876543..

문제 문제 바로가기> BOJ 2293번: 동전 1 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 2차원 배열로 풀면 메모리 초과가 발생하므로 1차원 배열로 풀어야 한다. i원 동전을 사용하여 j원을 만들 때 j-coin[i]의 누적합만 알면 되므로 1차원 배열로 풀 수 있다. #include #define MAX 101 #define MAX_K 10001 using namespace std; int n, k; int coin[MAX], dp[MAX_K]; void input(){ cin >> n >> k..

면접관에게 극찬 받는 PT 면접 발표 방법 위 영상을 토대로 PT 면접 준비하는 방법을 정리해 보겠다. PT 면접을 주요 평가 요소 출제 유형 1. 문제 해결형 ~한 상황에서 ~걸 해결/제안/극복해 보세요. 2. 주제 설명형 (특히 이공계) A에 대해 설명해보세요. 3. 시사 관련 ~한 사회적 이슈에 대한 견해를 밝혀보세요. PT 면접 구조 안녕하십니까. 지원자 000입니다. 저는 ~한 주제에 대해 발표를 진행하고자 합니다. (면접의 과정으로서도 굉장히 진지하게 이 질문에 대한 답을 구하기 위해서 노력을 했지만 또 한편으로는 제가 현직자의 입장에서 회사와 관련된 중요한 이슈를 해결한다라는 굉장히 큰 책임감을 가지고 이 문제를 풀어냈습니다.) 발표 내용은 크게 네 가지로 구분해서 면접관님게 말씀드리고자 합..

Union-Find Disjoint set (서로 중복되지 않는 부분 집합들로 나눠진 원소 정보를 저장/조작하는 자료구조)을 표현할 때 사용하는 알고리즘으로, 두 node가 같은 집합에 속하는지 판별할 때 유용하게 사용할 수 있다! 구현 1. 초기화 다음과 같이 모든 값이 자기 자신을 가리키도록 초기화해준다! 모든 값이 자기 집합의 대표값?이 되는 것이다. 처음에는 각 집합의 원소가 하나니까 어찌보면 당연한 일이다. int root[1000001]; for(int i=1; i>n>>m; for(int i=0; ioper>>a>>b; if(oper == 0) union_(a, b); else if(find_(a)==find_(b)) cout

문제 문제 바로가기 > BOJ 10021번: Watering the Fields 10021번: Watering the Fields Input Details There are 3 fields, at locations (0,2), (5,0), and (4,3). The contractor will only install pipes of cost at least 11. Output Details FJ cannot build a pipe between the fields at (4,3) and (5,0), since its cost would be only 10. He therefore b www.acmicpc.net 풀이 모든 필드를 최소 비용으로 연결하기 위하여 MST(최소 신장 트리)를 만들어서 문제를 풀..

문제 문제 바로가기> BOJ 9465번: 스티커 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이 다이나믹을 이용해서 푸는 문제였다. dp[i][j-1] + dp[1][j]가 dp[2][j] 보다 작은 경우 dp[1][j-2] + dp[2][j]를 해주는 것이 최대값이 된다. 이를 i가 1인 경우와 2인 경우로 나누어 각각의 위치에서 스티커의 점수를 더하여 얻을 수 있는 최대값을 구해주었다! #include #define MAX 100001 using namespace std; int N; in..

문제 문제 바로가기> BOJ 2178번: 미로 탐색 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이 BFS를 이용하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구할 수 있다! #include #include #define MAX 101 #define INF 987654321 using namespace std; int N, M; int maze[MAX][MAX]; int dist[MAX][MAX]; int dy[] = {-1,1,0,0}; int dx[] = {0,0,-1,1}; void input(){ cin >>..

문제 문제 바로가기> BOJ 1260번: DFS와 BFS 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 DFS와 BFS를 구현할 수 있는지를 보는 간단한 문제이다. 주의해야할 점은 "정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문"하기 때문에 미리 연결되는 node를 정렬해 두어야한다는 것이다! #include #include #include #include #define MAX 1001 using namespace std; int N, M, V; bo..

문제 문제 바로가기> BOJ 15591번: MooTube (Silver) 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 풀이 BFS를 이용해 탐색을 진행하면서, USADO(가중치)가 k이상인지 검사 해주었다! 전체 경로에서의 최소값이 최종 USADO가 되므로, 가는 경로에서 가중치가 한번이라도 k이상이면 그 동영상은 추천 받을 수 없다. #include #include #include #define MAX 5001 #define INF 1000000001 u..

스케줄링 OS는 CPU 등의 자원을 프로세스에 적절히 배정함으로써 시스템의 성능을 개선할 수 있음 프로세스가 작업을 수행하려면 스케줄러로부터 cpu를 할당 받아야 함 프로세스 실행 = (CPU 실행 + I/O 대기) 의 사이클 = CPU - I/O Burst Cycle CPU Scheduling = CPU 를 잘 사용하기 위해 프로세스를 잘 배정하기 ! 프로세스를 스케줄링하기 위한 Queue 프로세스를 스케줄링하기 위한 Queue 에는 세 가지 종류가 존재함 Job Queue : 현재 시스템 내에 있는 모든 프로세스의 집합 Ready Queue : 현재 메모리 내에 있으면서 CPU 를 잡아서 실행되기를 기다리는 프로세스의 집합 Device Queue : Device I/O 작업을 대기하고 있는 프로세스의..

문제 문제 바로가기> BOJ 2579번: 계단 오르기 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 주어진 조건을 만족하면서 다음 계단에 도착하는 방법은 다음과 같이 총 2가지이다. 1. 두 계단 전에서 현재 계단으로 : dp[i-2]+arr[i] 2. 한 계단 전에서 현재 계단으로 : dp[i-3]+arr[i-1]+arr[i] 따라서 위 점화식을 토대로 max 값을 찾아내면 된다! #include #define MAX 301 using namespace std; int N; int arr[MAX], dp[MAX]..

메모리 구조 코드 영역: 실행할 프로그램의 코드 데이터 영역: 전역 변수, 정적 변수 (프로그램 시작과 동시에 할당, 프로그램이 종료되어야 소멸) 힙 영역: 사용자의 동적 할당 스택 영역: 지역 변수, 매개 변수 (함수 호출 시 ! 함수 호출이 완료되면 사라짐) 프로세스 (Process) : 메모리에 올라와 실행되고 있는 프로그램 (OS는 모든 프로그램을 프로세스 형태로 실행함) OS로 부터 독립된 영역을 할당 받음 (통신을 위해서는 IPC: Inter-Process Communication 사용) 프로세스는 최소 한개의 쓰레드 (메인 쓰레드)를 가짐 new(생성), running(실행), waiting(I/O, event wait, waiting-> ready), ready(by interrupt), ..

운영체제 (Operating System) : 하드웨어를 관리하고, 컴퓨터 시스템의 자원들을 효율적으로 관리하며, 응용 프로그램과 하드웨어 간의 인터페이스로써 다른 응용 프로그램이 유용한 작업을 할 수 있도록 환경을 제공하는 프로그램 운영체제의 역할 1. 프로세스 관리 2. 저장장치 관리 1차 저장장치(Main Memory) 프로세스에 할당하는 메모리 영역의 할당과 해제 메인 메모리의 효율적 활용을 위한 가상 메모리 기능 2차 저장장치(HDD, NAND Flash Memory 등) 파일 형식의 데이터 저장 파일 데이터 관리를 위한 파일 시스템을 OS에서 관리 ( FAT, NTFS, EXT2, JFS, XFS 등 ) 3. 네트워킹 : 응용 프로그램이 네트워크를 사용하려면 운영체제에서 네트워크 프로토콜을 지..

문제 문제 바로가기> BOJ 12865번: 평범한 배낭 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 0-1 knapsack 문제로, 다이나믹 프로그래밍을 이용하여 해결할 수 있다. dp[i][j] : i개의 물건을 가지고, 최대 무게가 j 일 때 담을 수 있는 최대 가치 #include #define MAX 101 #define MAX_K 100001 using namespace std; int N, K; int weight[MAX], ..