본문 바로가기

전체 글

 (119)
[Softeer] [21년 재직자 대회 본선] 거리 합 구하기 / problemid 635 [JAVA] 문제링크 : https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=635&sw_prbl_sbms_sn=39796 Softeer Problem을 담을 Box를 선택해 주세요. 취소 확인 softeer.ai 모든 노드간 연결돼 있고 간선이 N-1개인 그래프는 트리다 모든 노드마다 다른 모든 노드와 거리의 합을 구한다면 N이 최대 2*10^5 이므로 단순하게는 불가능 해보인다 1번 노드를 루트로 하고 노드간 거리의 합을 먼저 구해보자 1번 노드를 루트로 하는 트리 1번에서 3번,5번,6번 노드로 가기 위해서는 빨간 간선을 지나가야 한다. 그러므로 빨간 간선은 2*3인 6을 정답값에 더해주는 간선이다. 마찬가지로 가중치가 5인 간선은 노드 2만을 위해 지나는 ..
[Softeer] [21년 재직자 대회 본선] 코딩테스트 세트 / ProblemId 630 [JAVA] 문제링크 : https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=630 Softeer Problem을 담을 Box를 선택해 주세요. 취소 확인 softeer.ai 짝수번 째 있는 난이도를 적절히 홀수번 째 있는 난이도에 할당하면 된다. 그렇게 해서 홀수번 째에 있는 난이도 중에 가장 작은 값을 가장 크게 만드는 방법을 찾아 그 값을 정답으로 한다. 예를들면 아래와 같다 N=3 이며 난이도의 정보는 아래와 같다고 하자(입력예제1-1) (1) 2 2 1 1 3 1) 2번째 값인 2를 왼쪽에 1, 오른쪽에 1씩 할당해준 후 난이도 결과 3 0 2 1 3 2) 4번째 값인 1을 왼쪽에 1 할당해준 후 난이도 결과 3 0 3 0 3 홀수번 째의 값은 3,3,3..
[Softeer] [21년 재직자 대회 본선] 비밀메뉴2 / ProblemId 633 [JAVA] 문제 링크 : https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=633 Softeer Problem을 담을 Box를 선택해 주세요. 취소 확인 softeer.ai 재직자 본선 문제 1번 A수열과 B 수열의 가장 긴 '연속된' 공통 부분 수열의 길이를 찾는 문제이다 방법 1. 길이를 1~3000까지 시도해보는 것이다. -> 3000(N) * 3000(M) * 2999 * 3000 / 2 (1~3000까지의 합) -> 1~3000까지 시도해볼 필요가 없다 (1500을 시도했을 때 실패했다면 0~1499중에 정답이 있다) -> 이분탐색으로 3000(N) * 3000(M) * 12이 가능하다. -> 그래도 시간 내에 해결하기 불가능해 보인다. 2. 연속된 ..
[백준] 21610 마법사 상어와 비바라기 JAVA 문제 링크 : https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 문제에서 하라는 대로 구현하면 된다. import java.io.*; import java.util.*; public class baekjoon_21610{ public static int N,M; public static int board[][]; public static int dir[][] = {{0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{..
[프로그래머스] 2021 카카오인턴십 - 미로탈출 [JAVA] 문제링크 : https://programmers.co.kr/learn/courses/30/lessons/81304 코딩테스트 연습 - 미로 탈출 4 1 4 [[1, 2, 1], [3, 2, 1], [2, 4, 1]] [2, 3] 4 programmers.co.kr 오랜만에 알고리즘을 풀었다. 다익스트라 + 비트마스킹 주석 참조 public static final int INF = Integer.MAX_VALUE; public static int maxBit; public static Map hm; //좌표압축 public static int dist[][]; public static class Node implements Comparable{ int nodeNum; int cost; int bitmask..
[카카오 2021 인턴십] 표 편집 / 다양한 풀이 [JAVA] 문제링크 : https://programmers.co.kr/learn/courses/30/lessons/81303 코딩테스트 연습 - 표 편집 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] "OOOOXOOO" 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"] "OOXOXOOO" programmers.co.kr 1. 이중연결리스트 2. 인덱스트리 3. 펜윅트리 문제를 가장 단순히 생각해보면, 표의 k번 위치에서 U나 D 입력이 들어왔을 때 U번 이동하면서 제거된 행은 횟수로 포함하지 않고 이동하면 될 것 같다. 또 C 입력에 대해서는 k번 위치의 행을 지우고 맨 아래가 아니면 제거되지 않은 아래행을 가리키도..
[백준] 13911 집 구하기 [JAVA] 문제링크 : https://www.acmicpc.net/problem/13911 13911번: 집 구하기 첫줄에는 정점의 개수 V(3 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 300,000)가 주어진다. 그 다음 E줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u,v,w)가 순서대로 주어진다. 이는 u와 v(1 ≤ u,v ≤ V)사 www.acmicpc.net 코드가 더럽다. 아이디어는 아래와 같다. 스타벅스거리 + 맥도날드 거리의 합이 최소인 집의 거리를 출력한다. 스타벅스거리와 맥도날드 거리를 따로 구해서 모든 집마다 스타벅스거리 + 맥도날드 거리의 합을 비교하는 것이다. 스타벅스거리를 구하는 방법은, 아무 스타벅스에서 다익스트라를 수행한다. 다음 노드가 집이면 스타벅스 거리가 늘어나..
[백준] 2479 경로 찾기 [JAVA] 문제링크 : https://www.acmicpc.net/problem/2479 2479번: 경로 찾기 길이가 같은 두 개의 이진수 코드 A와 B가 있다고 하자. 이 두 코드 사이의 해밍 거리는 A와 B의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 수이다. 예를 들 www.acmicpc.net 이진 수 코드 간 해밍 거리가 1인 이진 수 끼리는 연결돼 있다고 표현한다. 시작 점에서 연결된 이진 수 코드는 거리가 1이고, 연결된 이진 수 코드에서 다시 연결된 이진 수 코드간 거리는 1이므로, 이를 X번 반복해서 목적지 이진 수 코드를 찾을 수 있으면 해밍 거리가 X인 것이다. 이것은 BFS다. import java.io.*; import java.util.*; public..

티스토리툴바