Junior-Developer

1일 1커밋! 1일 1 백준!

문제풀이/백준oj

www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net -풀이- 간단한 bfs문제이다. 1. BFS를 이용하여 배열을 돌며 먹을 수 있는 먹이와 그 먹이까지의 거리를 구해서 vector에 넣어준다. 2. 모든 먹이들을 우선순위에 맞게 정렬을 해준다. -1순위:먹을 수 있는 먹이중 가장 짧은 거리 -2순위:짧은거리가 여러개면 가장 위에있는 먹이 -3순위:2순위도 많다면 가장 왼쪽에 있는 먹이 3. 2번의 결과가 0개이면, 어미 상어를 호출한다. 4. 3번에서 ..

2021. 4. 12.

문제풀이/백준oj

www.acmicpc.net/problem/8012 8012번: 한동이는 영업사원! 한동이는 경상도내를 돌아다니면서 열심히 일하는 영업사원이다. 예전에는 자기가 원하는 도시만 골라서 다닐 수 있었지만 시대가 바뀌어서 이제 그렇게는 하지 못하게 되었다. 시대가 바뀜에 www.acmicpc.net -풀이- 트리를 선언하고 m개의 도시를 순서대로 움직일때 최소시간을 출력해야 한다. a노드에서 b노드까지의 최소 거리를 구할 때 , 다익스트라를 사용해보았는데, 매번 다익스트라를 돌리기엔 시간초과가 났다. 그럼 어떻게 하면 좋을지 생각을 해보았는데, 어차피 최소한으로 움직이려면 a-> a와 b의 최소 공통조상->b 로 움직여야 최소거리가 된다. 그럼 한개의 간선의 이동시간이 1이므로, 한 노드의 깊이가 루트(1번노..

2021. 3. 24.

문제풀이/구름

level.goorm.io/exam/49109/jmos/quiz/1 구름LEVEL 코딩테스트에서 가장 높은 비중을 차지하는 알고리즘 문제를 제작하고 풀이할 수 있는 온라인 저지 서비스입니다. 기업에서 선호하는 C, C++, 파이썬(Python), 자바(Java), 자바스크립트(Javascript) 이 level.goorm.io -풀이- 꼬여있는관계를 없애기 위해 자원을 반납해야하는 최소한의 프로그램 개수를 구하는 문제이다. 이문제는 꼬여있는 최소한을 없애는것== 전체에서 가장 긴 증가하는 수열의 개수를 빼주는것과 같다. 따라서 가장 긴 증가하는 수열의 개수를 구해준 뒤, 전체 개수에서 빼주면 된다. -시간 복잡도- 전체적으로 N번을 돌며, lower_bound를 실행하기 때문에 O(NlogN)이 된다. ..

2021. 3. 19.

문제풀이/백준oj

www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net -풀이- 출발지점에서 w만큼의 무게를 들고 시작점->도착점까지 도달할 수 있는지 없는지에 대한 bfs를 세워둔뒤, w에 대한 이분탐색을 실시한다. 만약 w만큼의 무게를 시작지점->도착지점까지 도달이 가능하다면, 무게를 올려도 되므로 left를 갱신시키고, 도달할 수 없으면 무게를 줄여야하므로 right를 갱신시키며 탐색을 하면, 물품들의 중량의 최댓값을 구할 수 ..

2021. 3. 17.

문제풀이/백준oj

www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 풀이) BFS로 풀 수 있다. BFS의 기본 상하좌우에서 말의 이동방향으로 배열을 선언해둔뒤, 일반적인 BFS를 수행시켜주면된다. 시간복잡도) 인접행렬BFS를 수행했으므로, O(l*l)이 된다. 코드) #include #include #include #include #include #define MAX 987654321 using namespace std; int mv[8][2]={{-1,-2},{-1,2},{1..

2021. 3. 11.

문제풀이/백준oj

www.acmicpc.net/problem/18427 18427번: 함께 블록 쌓기 첫째 줄에 자연수 N, M, H가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 10, 1 ≤ H ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 각 학생이 가진 블록들의 높이가 공백을 기준으로 구 www.acmicpc.net 풀이) dp문제+배낭문제이다. dp[i][j]=k 를 i명이 h높이를 만들 수 있는 경우의 수를 k라고 하자. i명의 사람이 j높이 만큼 쌓을 수 있는 경우의 수는, i-1명이 j-(i번째 사람이 들고있는 현재블록의 높이) 만큼 쌓을 수 있는 경우의 수와 동일하다. 예를들어 4번째 사람이 들고있는 블록의 높이가 2,4라고 했을 때, 4명의 사람이 10만큼의 높이를 쌓는 경..

2021. 3. 11.

문제풀이/백준oj

www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 풀이) 1. 입력받은 패키지와 단품중, 최소값만 구한다. 2. {패키지,단품} 의 개수를 {0,N-6},{1,N-12},{2,N-18} , ... , {(N/6)+1,N-6*((N/6)+1)} 의 순서쌍을 탐색하며, 각 경우중 최소비용을 구하면된다. 3. (N/6)+1은 패키지를 사고, 단품이 남았을떄 패키지 가격 > 싱글*남은 단품개수 일 수 있으므로 고려해줬고, 단품의 개수는 앞의 경우와 같으면 음수가 ..

2021. 3. 7.

문제풀이/백준oj

www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 풀이) c++에서 제공해주는 STL의 sort()를 이용하여 풀었다. 다만 정렬 기준을 다시 정의해주어서 풀었다. compare 함수를 정의하여 문제에 정의된 1.국어점수가 감소하는 순서로 2.국어 점수가 같으면 영어 점수가 증가하는 순서로 3.국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로 4.모든 점수가 같으면 이름이 사전순으로 증가하는 순서로 이 조건들을 추가시켜서 정렬을..

2021. 3. 7.