본문 바로가기

알고리즘/백준48

[백준 1697] 숨바꼭질 - 자바 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 www.acmicpc.net 1. 풀이 처음엔 헤맸지만, 풀고나니 BFS에 대해서 더 깊은 이해를 하게 되는 좋은 문제인 듯 싶다. 수빈이는 +1 , -1 , *2로 .. 2020. 4. 5.
[백준 1260] DFS와 BFS - 자바 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. www.acmicpc.net 1. 풀이 이 문제는 DFS와 BFS의 구현을 하는 문제입니다. 그래프를 구성하는 방법은 인접 리스트와 인접 행렬이 있습니다. 둘 중 아무거나 선택해서 구현을 하면 되지만, 저는 인접 행렬을 통해서 구현했습니다. 주의할 점은 DFS에서 스택을 통한 구현과, 재귀를 통한 구현이 있는데요... 2020. 4. 4.
[백준 1946] 신입 사원 https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어진다. 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다. www.acmicpc.net 1. 풀이 문제의 조건은 A라는 사람의 서류 및 면접 시험의 성적이 B라는 사람 보다 둘 다 열세라면 채용을 하지 않는다는 것이엇습니다. 따라서 그리디를 사용하였고, 아래와 같이 풀이를 하였습니다. 1. 서류심사의 성적을 기준으로 오름차순 정.. 2020. 4. 3.
[백준 1120] 문자열 - 자바 https://www.acmicpc.net/problem/1120 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 길이는 B의 길이보다 작거나 같다. 이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다. A의 앞에 아무 알파벳이나 추가한다. A의 뒤에 아무 알파벳이나 추가한다. 이때, A와 B의 길이가 같으 www.acmicpc.net 1. 풀이 알파벳 추가까지는 굳이 안해도 되고, 앞으로 넣나, 뒤로 넣나 어차피 정답만을 넣을 것이기 때문에, 뒤로는 신경 안쓰고, 앞으로.. 2020. 4. 3.
[백준 1541] 잃어버린 괄호 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. www.acmicpc.net 1. 풀이 문제에서 적절히 괄호를 넣으라고 하였으므로, 괄호가 있어도 되고 없어도 된다는 뜻입니다. 따라서 마이너스(-)가 나온 뒤 나오는 숫자들을 모두 더하고, 다음 마이너스(-)가 나오기 전 숫자에서 빼주면 됩니다. 입력값을 문자열로 받은 후, 마이너스를 기준으로 문자열을 잘라줍니다. 자른 문자열을 모두 더해줍니다. 마지막으로 전.. 2020. 4. 3.
[백준 2875] 대회 or 인턴 https://www.acmicpc.net/problem/2875 2875번: 대회 or 인턴 문제 백준대학교에서는 대회에 나갈 때 2명의 여학생과 1명의 남학생이 팀을 결성해서 나가는 것이 원칙이다. (왜인지는 총장님께 여쭈어보는 것이 좋겠다.) 백준대학교는 뛰어난 인재들이 많아 올해에도 N명의 여학생과 M명의 남학생이 팀원을 찾고 있다. 대회에 참여하려는 학생들 중 K명은 반드시 인턴쉽 프로그램에 참여해야 한다. 인턴쉽에 참여하는 학생은 대회에 참여하지 못한다. 백준대학교에서는 뛰어난 인재들이 많기 때문에, 많은 팀을 만드는 것이 최선이다. 여 www.acmicpc.net 1. 풀이 문제의 조건에 따른 카운트해도 되는 규칙은 아래와 같습니다. 1. 여학생 2명, 남학생 1 명을 각각 빼줬을 때 총 남.. 2020. 4. 3.

티스토리툴바