본문 바로가기

알고리즘56

[백준 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.
[프로그래머스] 네트워크 - 자바 https://programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 코드 DFS나 BFS를 통해서 노드간의 연결을 탐색하는 문제이다. 연결 요소의 개수를 찾는 것과 똑같다. 각 노드마다 DFS를 돌려서 연결 요소의 개수를 카운팅 하면 되는 문제이다. 백준에서 11724 ( 연결요소의 개수 )와 비슷한 문제이다. 2. 코드 class Solution { static boolean[] visited; // 방문 체크용 static int answer = 0; public i.. 2020. 4. 4.
[프로그래머스] 타켓 넘버 - 자바 https://programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 풀이 DFS를 사용하는 문제인데요, 재귀를 사용하여 부분 집합의 알고리즘을 이용하면 쉽게 풀이가 됩니다. 배열(numbers)의 요소들을 하나의 노드라고 보고, 문제에서 +, -만을 사용할 수 있다고 하였기 때문에 트리 형태처럼 +와 -를 번갈아주면서 부분집합을 구한 후 합을 구하여 타켓과 같으면 카운트를 해주면 됩니다. 저도 처음엔 이해가 잘 안되서, 구글링을 통해서 해당 방법을 알게되었습니다. DFS.. 2020. 4. 4.
[백준 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.

티스토리툴바