본문 바로가기
반응형

코딩 테스트

[프로그래머스] 네트워크 (JAVA)
CodingTEST 2023. 10. 11. [프로그래머스] 네트워크 (JAVA) 프로그래머스 - [Level 3] 네트워크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 분석 네트워크란 컴퓨터 간에 정보를 교환할 수 있는 형태를 의미 (즉, 한개씩이라도 연결되있는 상태) 컴퓨터 개수와 연결정보를 가지고 네트워크가 몇 개인지 출력 해결 키 포인트 BFS 이용 코드 import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; class Solution { public static boolean [] visited; public static Array..
[프로그래머스] 게임 맵 최단거리 (JAVA)
CodingTEST 2023. 9. 19. [프로그래머스] 게임 맵 최단거리 (JAVA) 프로그래머스 - [Level 2] 게임 맵 최단거리 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 분석 게임 맵(NXM)이 주어졌을 때, 내가 상대팀 진영(n-1,m-1)에 도달할 때 가장 적게 지나가는 칸의 개수을 출력해라. (도착할 수 없을 때는 -1을 출력) map에 0은 갈 수 없는 길이다. 해결 키 포인트 BFS 이용 시간이 생각보다 여유롭지 않음 (시간초과 고려) count를 지역변수로 두고 큐에 있는 걸 다 빼고 인접 노드를 다 넣는 방법 → 문제 X 이웃셀 탐색하는 방법 → 문제 O, 제대로 구현해야함 + 추가적으로 queue에 넣기 ..
[백준 14675] 단절점과 단절선 (JAVA)
CodingTEST 2023. 9. 19. [백준 14675] 단절점과 단절선 (JAVA) 백준 14675번 문제 - 단절점과 단절선 14675번: 단절점과 단절선 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 트리의 정점 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 트리의 정점은 1번부터 n번까지 존재한다. 다음 줄부터 N-1개의 줄에 걸쳐 간선의 정 www.acmicpc.net 문제 분석 트리에서 해당 점이 단절점인지, 해당 선이 단절선인지 유무를 출력한다. 단절점(cut vertex) : 해당 정점을 제거하였을 때, 그 정점이 포함된 그래프가 2개 이상으로 나뉘는 경우 단절선(bridge) : 해당 간선을 제거하였을 때, 그 간선이 포함된 그래프가 2개 이상으로 나뉘는 경우 해결 키 포인트 각 정점에 연결된 정점 정보를 ArrayList로 제작한다. 질문에 대한 답을..
[백준 7662] 이중 우선순위 큐 (JAVA)
CodingTEST 2023. 9. 19. [백준 7662] 이중 우선순위 큐 (JAVA) 백준 7662번 문제 - 이중 우선순위 큐 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 문제 분석 이중 우선순위 큐가 있다고 가정하고 문제를 푼다. 입력 받을 테스트 개수를 입력받고, 각 케스트에서 연산 수를 입력 받는다. 그리고 연산을 실행하고 가장 큰 값, 가장 작은 값을 출력한다. (이중 우선순위 큐의 첫번째와 마지막 값을 출력) 만약 값이 없으면 EMPTY를 출력하라. 연산 풀이 1) D num : [ num == 1 ] 최댓값 삭제 | [ num == -1 ] 최솟값 삭제 2) I num : ..
[백준 4358] 생태학 (JAVA)
CodingTEST 2023. 9. 19. [백준 4358] 생태학 (JAVA) 백준 4358번 문제 - 생태학 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 문제 분석 나무들을 입력이 없을 때까지 입력받아, 각 나무별로 차지하는 비율(%)을 소수점 4째자리까지 출력해라 해결 키 포인트 입력받을 수 N을 입력받지 않고, 어떻게 사용자의 입력 종료를 기다릴지가 중요 끝 값(EOFf)를 알아내는 법 1) (Scanner 사용) scanner.hasNextLine()과 입력받은 문자열 s의 s.isEmpty() 확인 2) (BufferedReader 사용) 입력받은 문자열 s의 s..
[백준 1516] 게임 개발 (JAVA)
CodingTEST 2023. 8. 29. [백준 1516] 게임 개발 (JAVA) 백준 1516번 문제 - 게임 개발 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 문제 분석 건물을 짓기 위해 선행되어야하는 건물이 있다. 그럼 이 건물을 짓기 위해 필요한 최소 시간을 출력한다. 2, 3 둘 다 1번 건물이 필요할 때 : 1번 짓고 2번 1번 또 짓고 3번이 아니라, 1번 짓고 2, 3을 짓는 것으로 시간을 잰다. 해결 키 포인트 위상 정렬 개념 이해 위상 정렬할 때, inDegree 배열에 선행되어야 할 건물 개수가 아닌 자신이 선행되어야하는 건물의 개수로 한다. 현재 이미 건..
[백준 2252] 줄 세우기 (JAVA)
CodingTEST 2023. 8. 27. [백준 2252] 줄 세우기 (JAVA) 백준 2252번 문제 - 줄 세우기 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 문제 분석 N(학생 수), M(비교 횟수) 입력 M번의 비교 입력 : a b 입력 - a가 b의 앞에 와야한다 이를 토대로 학생들 나열 순서에 맞춰 출력해라 해결 키 포인트 위상 정렬 개념 이해 위상 정렬 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다. 위상 정렬에서는 항상 유일한 값으로 정렬되지 않는다. 또한 사이클이 존재하면 노드 간의 순서를 명확하게 정의할 수 없으..
[백준 1043] 거짓말 (JAVA)
CodingTEST 2023. 8. 27. [백준 1043] 거짓말 (JAVA) 백준 1043번 문제 - 거짓말 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 문제 분석 N,M 입력 : 지민이는 N명의 친구가 있으며, M개의 파티에 참여해야한다. 수 K와 K명의 진실을 아는 사람 입력 M개의 파티를 입력 - 수 K와 K명의 파티에 참여하는 사람 입력 (M개의 파티에 순서는 없다) 진실을 아는 사람이 있을 때에는 과장해서 이야기 할 수 없을 때, M개의 파티에서 과장해서 이야기할 수 있는 파티의 개수를 출력해라. + 진실을 아는 사람과 함께 파티를 보낸 사람 또한 진실을 아는 사람이 된다. 해결 키..
[백준 1976] 여행 가자 (JAVA)
CodingTEST 2023. 8. 26. [백준 1976] 여행 가자 (JAVA) 백준 1976번 문제 - 여행 가자 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 문제 분석 N(전체 도시 개수)하고 M(가고 싶은 도시 개수)을 입력받고, N(1 ≤ i ≤ N)번 N(1 ≤ j ≤ N)개씩 수가 주어진다. 이 수는 i번 나라와 j번 나라의 연결 정보 입력 정보로 1이면 i와 j 나라가 연결되있음을 의미 가고 싶은 도시 M개를 입력 받는다. 가고 싶은 도시들이 다 연결되어 있어 모두 갈 수 있을 경우 YES, 아닐 경우 NO 출력 해결 키 포인트 유니온 파인드(union-find) 개념 사..
[백준 1717] 집합의 표현 (JAVA)
CodingTEST 2023. 8. 26. [백준 1717] 집합의 표현 (JAVA) 백준 1717번 문제 - 집합의 표현 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 문제 분석 N개의 수가 주어지면 N개는 각각 다른 집합으로 구성된다. M개의 수식이 주어지며, 수식은 다음 2가지 종류가 있다. 0 a b : b 집합을 a 집합에 포함 시킨다. 1 a b : a와 b가 동일한 집합이면 YES, 아니면 NO 출력 해결 키 포인트 유니온 파인드(union-find) 개념 사용 0도 포함되므로 배열 구현할 때, N개 배열 생성하고 a,b에서 -1을 하면 안된..
[백준 2251] 물통 (JAVA)
CodingTEST 2023. 8. 25. [백준 2251] 물통 (JAVA) 백준 2251번 문제 - 물통 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 문제 분석 물은 C에만 가득찬 상태로 시작 물을 옮길 때 물을 받는 쪽이 가득차거나, 물을 주는 쪽이 비는 경우만 가능 이 과정을 실행해서 A가 비어있을 때 C의 담긴 물의 양의 경우의 수를 모두 출력 ex) 0 | 0 | 10 , 0 | 1 | 9 , 0 | 2 | 8 , 0 | 8 | 2 , 0 | 9 | 1 ➡️ C의 경우의 수(오름차순) : 1, 2, 8, 9, 10 해결 키 포인트 BFS(너비 우선 탐색..
[백준 1707] 이분 그래프 (JAVA)
CodingTEST 2023. 8. 24. [백준 1707] 이분 그래프 (JAVA) 백준 1707번 문제 - 이분 그래프 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 문제 분석 몇 번 동작할지(K) 입력 → 정점(V), 간선(E) 입력 → 간선 입력 → 이분 그래프가 가능하면 YES, 아니면 NO 출력 해결 키 포인트 BFS(너비 우선 탐색) 개념 파악 이분 그래프 개념 파악 해당 정점과 연결된 정점은 다른 그룹, 인접 리스트 중에 값은 그룹이 존재 하지 않는 그래프 (사이클이 존재할 때 홀수 사이클이면 이분 그래프 아님) 너비 우선 탐색(BFS) 그래프 완전 탐색 기번 중 하나로, 그래..
반응형

티스토리툴바