ps (12) 썸네일형 리스트형 [백준] B1395 스위치 - 느리게 갱신되는 세그먼트 트리 들어가면서 세그먼트 트리를 연습하면서 문제를 도전했다. 아직 완벽히 내 것으로 만든 알고리즘이 아니라서 사소한 실수를 많이 했다. 문제를 풀면서 내가 한 실수들을 설명하고자 한다. 세그먼트 트리 서그먼트 트리는 데이터의 집합에서 특정 구간의 연산된 결과를 빠르게 구하기 위해서 사용하는 알고리즘 중에 하나이다. 비슷하게 사용되는 알고리즘으로는 누적합 알고리즘이 있다. 두 알고리즘은 목적이 같지만 상황에 따라서 더 효과적인 알고리즘이 있기 때문에 특성을 이해하고 사용하는 것이 좋다. 세그먼트 트리는 연산된 결과를 트리 형태로 미리 저장하는 알고리즘이다. 부모 노드의 값은 자식 노드들의 연산 결과로 구성되어 있다. 보통 이진트리 구조로 세그먼트 트리를 만들어 사용하는 것으로 보인다. 다음은 특정 범위의 값을 .. [알고리즘] 스패닝 트리 Spanning tree란? 신장 트리, 스패닝 트리 생성 나무 라고 번역되어 쓰이며 노드 간 경로가 오직 하나인 토폴로지이다. 특징 모든 정점들의 연결에 끊임이 없어야 한다. 간선의 수 + 1 = 정점의 수 단절점, 단절선 구하기 문제 적용 스패팅 트리에서 특정 간선이나 특정 정점을 제거하면 그래프가 2개 이상으로 나뉘어지는 것을 활용하여 단절선과 단절점을 구한다. 11266번: 단절점 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B www.acmicpc.net 11400번: 단절선 첫째 줄에 두 정수 V(1≤V≤100,000),.. 최대공약수 구하기 https://school.programmers.co.kr/learn/courses/30/lessons/12940 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 최대공약수를 구하는 문제를 푸는데 O(n)의 시간 복잡도로 해결을 했다. 좀 더 효율적인 알고리즘이 있는데 활용을 하지 못하는 것 같아서 구글링을 해서 더 직관적이고 효율적인 알고리즘을 공부해서 소개하고자 한다. 유클리드 호제법 - 증명 A = B * c + r 일 때, A, B의 최대 공약수는 B, r의 최대 공약수와 같다. 라는 것이다. 전제 1. A와 B의 최대 공약수는 G이다. 2. A =.. [프로그래머스] 고고학 최고의 발견 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제를 분할하는 방법은 문제 해결 방법의 절차를 쪼개는 방법과 문제의 범위를 쪼개는 방법이 있다는 것을 생각하게 해주는 문제였다. 여기에서는 문제의 범위를 쪼개서 생각하는 것이 중요한데 절차적으로 어떻게 해결하면 좋을지만 생각하니 문제 해결의 실마리를 놓치고 삽질을 하게된 원인인 것 같다고 생각한다. 해결 과정 완전 탐색으로 문제를 푼다고 가정하면 각 시계가 90도, 180도 270도 0도 회전하는 경우를 생각하고 그것이 연속적으로 n제곱 만큼 있다. 그래서 완전탐색으로 모든 경우를 탐색하게 되면 4의 n제곱.. [프로그래머스] 등대 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 처음 풀때는 너무 복잡하게 생각해서 접근도 힘들었던 문제였다. 구글링을 해도 이해하기 쉬운 코드나 블로그가 보이지가 않았고 내 풀이가 조금 특이한 방법이라고 생각해서 공유하면 좋겠다는 생각에 포스팅을 해보았다. import java.util.*; import java.util.stream.Collectors; class Solution { Map map = new HashMap(); public void initMap(int[][] lighthouse) { for (int[] house : lighthouse.. [프로그래머스] 퍼즐 조각 채우기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제의 조건에 따라 정확하게 구현하는가를 판단하는 문제로 로직은 그렇게 복잡하지는 않았다. 하지만 도형을 회전시켜 같은 도형인지를 판단하는 부분에서 애를 먹었다. 내가 접근한 방식은 두가지 방식이다. 1. 무식하게 회전시키는 방법 사실 코딩테스트에서 문제를 풀때는 깔끔한 코드는 필요없어서 이런 간단한 방법이 더 좋은 선택지일 수 있다고 생각한다. 아래의 코드는 data에 저장된 모양을 90, 180, 270, 360 회전한 결과를 따라 입력 각도에 따라 출력하는 함수이다. 순서는 각도와 상관없다. privat.. [백준] 10775 공항 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 유니온 파인드를 이용해서 해결하는 문제이다. 유니온 파인드를 모른다면 검색해서 공부하고 글을 읽는 것을 추천한다. 원리는 다음 블로그를 참고하거나 "union find 최적화"로 검색하면 자료가 많이 나온다. [자료구조]Union-Find: Disjoint Set의 표현 Union-Find 란? Union-Find 란? Union-Find 의 구현 배열로 표현하기 트리로 표현하기 트리로 표현하기 : 실제 소스코드 최.. [백준] 1890 점프 JAVA 정답 코드 import java.io.*; public class Main { static int[][] board; static int size; static boolean[][] isConcluded; static long[][] dp; static int[] mRow = {0, -1}; static int[] mCol = {-1, 0}; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); s.. 이전 1 2 다음
