Tech Log 🛠️

문제 분석 사실 이 문제를 굉장히 단순 무식하게 풀었다. 대략 문제의 조건을 요약하면 1. 중간에 파티션(X)이 존재한다면 거리 두기를 지킨 것이다. 2. 파티션을 사이에 두고 앉은 경우도 거리 두기를 지킨것이다. (옆에 빈 테이블이 있으면 안됨) 으로 요약 가능하다. 생각해보면, 1번 조건은 파티션이 나오면 해당 라인은 더 이상 탐색할 필요가 없는 것이다. 2번 조건에서는 P(참가자) 옆에 공석(O)이 있으면 안된다. 라고 해석할 수 있다. 이제 알고리즘을 짜보자 탐색을 할 때는 세가지 경우가 있다. 1. 파티션(X)이 나오는 경우 - 더 이상 볼 필요 없음 skip 2. 참가자(P)가 나오는 경우 - 무조건 안됨 3. 공석(O)이 나오는 경우 - 이건 좀 더 탐색할 필요가 있다. 주변에 참가자(P) ..

투포인터 알고리즘 - 리스트에 순차적으로 접근해야 할 때 두 개의 점(시작점 , 끝점)의 위치를 기록하면서 처리하는 알고리즘이다. - 시작점과 끝점으로 접근할 데이터의 범위를 표현할 수 있다. 예를 들어, 해당 수열에서 합이 5인 부분 수열의 개수를 찾는다고 생각해보자 1 2 3 2 5 완전 탐색으로 문제를 해결할 수도 있지만 너무 많은 시간이 걸린다는 단점이 있다. 따라서 이때 투포인터 알고리즘을 이용하여 문제를 해결할 수 있다. 투포인터 알고리즘의 방식은 다음과 같다. 1. 처음에는 시작점과 끝점 모두 0에서 시작한다. 1(start,end) 2 3 2 5 2. 합이 목표값과 같으면 카운트한다. 3. 만약 목표값보다 부분수열의 합이 작다면 end 인덱스를 1 증가시킨다. 1(start) 2(end) ..

"이것이 취업을 위한 코딩 테스트다 with 파이썬" 내용을 기반으로 제작하였습니다. (https://www.youtube.com/watch?v=KGyK-pNvWos&t=2349s) 정렬이란? - 데이터를 특정한 기준에 따라 순서대로 나열하는 것이다. - 문제에 따라 적절한 정렬 알고리즘이 사용된다. 위와 같이 정렬되지 않은 수열을 정렬하려면 어떻게 해야될까 ? 정렬 알고리즘에는 크게 4가지가 있다. 1. 선택 정렬 - 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다. 7 5 9 0 3 1 6 2 4 8 첫번째 단계에서는 0이 제일 작으므로 0과 7을 교환한다. 0 5 9 7 3 1 6 2 4 8 두번째 단계에서는 1이 제일 작으므로 5와 교환한다. 0..

분석 해당 문제는 백트래킹 , 비트마스킹 두 가지 방법으로 풀 수 있습니다. 1. 비트마스킹 비트 마스킹이란? 불리언 배열의 역할을 하는 하나의 숫자를 만들어서 비트 연산자를 통해 탐색 , 수정 등의 작업을 하는 것을 말합니다 - 큰돌의 터전 유튜브 더 자세한 사항은 이전에 블로그에 정리해 놓은 내용을 참고해주세요 https://cb036133.tistory.com/91 [백준] 11723 집합 JAVA 분석 비트마스킹을 이용하여 푸는 문제이다. 비트마스킹이란? - 컴퓨터는 모든 자료를 이진수로 표현하는데, 이를 이용하여 자료구조로 쓰는 기법이다. 비트마스킹을 통해 스위치,방문 처리 등 cb036133.tistory.com static void dfs() { for (int i = 0; i < (1

분석 이 문제를 풀려면 트리 자료구조와 트리의 순환에 대해 알아야한다. 트리란? 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조이다. 루트노드 : 부모가 없는 최상위 노드 (F)단말노드 : 자식이 없는 노드 (A,C,E,H)크기 : 트리에 포함 된 노드의 개수 (8)깊이 : 깊이 루트 노드부터의 거리높이 : 깊이 중 최댓값 (3)차수 : 각 노드의 간선 개수 * 트리의 크기가 N 일때, 전체 간선의 개수는 N-1 이다. 트리의 순회 트리 자료구조에 포함 된 노드를 특정한 방법으로 한번씩 방문하는 방법이다. 대표적인 순회의 방법은 3가지가 있다. 1. 전위 순회 : 루트노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드 순으로 방문한다. F B A D C E G I H 2. 중위 순회 : ..

분석 비트마스킹을 이용하여 푸는 문제이다. 비트마스킹이란? - 컴퓨터는 모든 자료를 이진수로 표현하는데, 이를 이용하여 자료구조로 쓰는 기법이다. 비트마스킹을 통해 스위치,방문 처리 등 다양한 문제를 해결할 수 있다. 비트연산자의 종류 - 비트마스크의 상태를 변경시키기 위해 다양한 비트 연산자를 활용할 수 있다. 1. a | b - a의 모든 비트와 b의 모든 비트를 OR 연산을 수행한다. ex) a=1 , b=1 일때 a | b = 1 a=1 , b=0 일때 a | b = 1 a=0 , b=0 일때 a | b = 0 2. a & b - a의 모든 비트와 b의 모든 비트를 AND 연산을 수행한다. ex) a=1 , b=1 일때 a & b = 1 a=1 , b=0 일때 a & b = 0 a=0 , b=0 ..

비트마스킹 문제를 마지막으로 골드를 달성하였다 ! 비록 중간에 다른 사람꺼 참고한 코드도 있고 쉬운 문제들도 많이 풀었지만 어찌됐건 골드까지 오게되었다 이제 플레티넘을 목표로 더 열심히 풀어야겠다 ㅎㅎ

분석 이 문제를 풀려면 bfs와 dfs에 대해서 먼저 알아야한다. dfs, bfs는 그래프를 탐색할 때 사용하는 알고리즘인데, 구현 방식이 다르므로 목적에 따라 다른 알고리즘이 사용된다. (*그래프 : 노드와 간선으로 이루어진 자료구조의 일종) 깊이 우선 탐색(bfs) - 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완전하게 탐색하는 방식을 말한다. 스택 , 재귀함수로 구현이 가능하지만 재귀함수로 구현하면 좀 더 간략한 코드가 나온다. 모든 노드를 방문해야하거나 , 그래프가 큰 경우 사용 너비 우선 탐색(bfs) - 인접한 노드를 먼저 탐색하는 방식을 말한다. 가까운 노드를 먼저 방문하고 멀리있는 노드를 나중에 방문한다. 큐로 구현할 수 있다. 최단 경로를 구할 경우 사용 코드 impo..

분석 완전탐색 문제이다. 처음부터 끝까지 비교해가면서 무식하게 답을 찾는 수 밖에는 없다.. 인접한 사탕의 색이 다를 경우 위치를 변경한다고 하였지만 그 코드를 짜는 거 자체가 더 비효율적이기 때문에 모든 사탕의 위치를 바꾸면서 비교해가는 방식으로 해결하였다. 그리고 사탕을 바꾸는 경우의 수는 1. 옆자리끼리 바꾸기 2. 위아래로 바꾸기 이렇게 두가지 경우가 있어서 두 경우 모두 비교를 해주었다. 사탕의 길이를 구하는 경우 또한 두가지가 있는데 1. 가로줄로 사탕으로 먹는 경우 2. 세로 줄로 사탕을 먹는 경우 이 두 가지 경우를 사탕의 자리를 바꿀 때마다 각각 비교해주면 된다 ! 코드 import java.util.Arrays; import java.util.Scanner; public class Ma..

분석 일단 포도주를 3개라고 가정해보자 포도주를 제일 많이 마시는 경우의 수는 1. 첫 번째 , 두 번째 포도주를 마시는 경우 2. 세 번째 , 첫 번째 포도주를 마시는 경우 3. 세 번째 , 두 번째 포도주를 마시는 경우 크게 3가지가 나올 수 있다. 이렇게 생각하면 다음과 같은 점화식을 세울 수 있다. dp[num] = max(max(dp[num - 3] + value[num - 1] + value[num], dp[num - 2] + value[num]),dp[num-1]); 3가지 경우의 수를 비교해주면 된다 ! 코드 import java.util.Arrays; import java.util.Scanner; import static java.lang.Math.max; public class Main..