문제 문제 바로가기> BOJ 1806번: 부분합 1806번: 부분합 첫째 줄에 N (10 ≤ N > N >> S; for(int i=0; i> num[i]; } void solution(){..

문제 문제 바로가기> BOJ 1253번: 좋다 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 풀이 정렬 후 두 포인터를 이용하여 "좋은" 수를 찾을 수 있다. * 서로 다른 두 수의 합은 해당 수를 사용해서 만들어지면 안된다! #include #include #define MAX 2001 using namespace std; int N; int num[MAX]; void input(){ cin >> N; for(int i=0; i> num[i]; } void solution(){ sort(num, num+N); // 정렬 int ans..

문제 문제 바로가기> BOJ 2887번: 행성 터널 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 풀이 MST를 만드는 문제이다. 다만, 메모리 초과 방지를 위해 정렬을 사용하여 O(N2)이 아닌, O(3N)개의 비용 후보만 가지도록 해야한다! #include #include #include #include #define MAX 100001 using namespace std; vector X, Y, Z; struct edge{ int a, b, dist; bool opera..

문제 문제 바로가기> BOJ 5430번: AC 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 풀이 덱에 들어갈 숫자의 길이가 1 이상일 수 있다. (0 T; while(T--){ string p; cin >> p; int size; cin >> size; string arr; cin >> arr; deque dq; string num = ""; for(int i=1; i

문제 문제 바로가기> BOJ 13549번: 숨바꼭질 3 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 순간이동을 하는데는 시간이 소요되지 않으므로, 해당 위치에 최단 거리로 도착할 수 있도록, 시간을 업데이트해 줄 필요가 있다! #include #include #define MAX 100001 using namespace std; int N, K; int visit_time[MAX]; int main(){ ios_base::sync_with_stdio(0); cin.ti..

문제 문제 바로가기> 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..