백준에서 강의실 배정 문제를 풀다가 sort가 되는 원리를 잘 이해 못하고 있다보니 정렬이 잘되었는지 확인하기 위해 헛된 시간을 쏟고 있다는 것을 깨달았다. 깨달았으면? 공부를 해야지! 1. Arrays.sort() 배열을 이용할 때는 Arrays.sort()를 이용한다. Arrays.sort()는 정렬 방식이 DualPivotQuickSort이다. 2가지 포인터를 이용해 비교하는 퀵소트로 정렬한다. 이런 이유로 시간 복잡도는 평균 O(n log n)이지만 최악의 경우에는 O(n^2)까지 나올 수 있다. 그래서 정렬할 일이 생기면 기본 Collections.sort() 먼저 생각하기 나름이다. import java.util.*; import java.io.*; class Main { public stat..
하노이탑은 알고리즘 문제로 너무 유명하지만, 난 이번에 처음 풀어봤다. 단순 구현문제인 줄 알았는데, 재귀 문제로 유명한 것이었다. https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 1. 이동 갯수 공식 하노이탑은 이동할 때마다 신경써줘야 하는 것이 있다. 바로 쌓아 놓은 원판은 항상 위의 것이 아래 것보다 작아야 한다는 공식이다. 이걸 고려하여 이동 갯수를 1부터 세워주면 일정한 숫자로 증가하는 것을 확인할 수 있다. 원판 1개 (..
0. 인트로 나는 사실 LCS 문제를 처음 풀어본다. 그래서 혼자 풀어보려니 시간초과만 나고 답도 틀리고 잘 풀리지 않았다. 그래서 여러 LCS 설명을 찾아봤는데, 무슨 말인지 통 모르겠더란다... 그러던 찰나에 발견한 한 유튜브 강의가 내 이해를 도왔다. 영상 길이는 4분이라는 짧은 시간인데, 내 이해를 단번에 도왔다. https://www.youtube.com/watch?v=MeE-GSikiE4 1. LCS란? LCS는 최장 공통 부분 수열의 길이를 구하는 문제이다. 예를 들면 아래와 같은 문제이다. 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들..
오늘은 수들의 합2에서 맞닥뜨린 투포인터 알고리즘에 대해 기록해보고자 한다. 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 1. 투포인터는 어디에 쓰일까? 투포인터가 쓰이는 대표적인 예제로는 [특정한 합을 가지는 부분 연속 수열]을 찾을 때이다. 나는 슬라이딩 윈도우랑 쓰임새가 많이 헷갈렸다. 두 알고리즘의 차이는 투포인터는 구간의 너비가 조건에 따라 유동적으로 변하고, 슬라이딩 윈도우는 구간의 너비가 고정되어 있다는 것이다. 수들의 합2 문제는 고정된 구간의 너비를..
현대오토에버 코딩테스트를 보려고 하는데, C/C#으로 제한된 언어.. 문자열은 언어 가리지 않고 약하기 때문에 C strtok 개념을 정리해보려고 한다. split 기능은 문자열의 필수 기능인데, C는 직접 구현하거나 include strtok를 이용해야 한다. https://softeer.ai/practice/6254 Softeer - 현대자동차그룹 SW인재확보플랫폼 당신은 인사팀 직원으로, 각 직원의 근태를 확인하고자 한다. 당신의 회사는 자율출퇴근제를 실시하기 때문에 각 직원이 정확히 몇 시에 출근하는 것은 중요하지 않고, 총 근로 시간이 몇 분인 softeer.ai 가장 기본 연습 풀이 문제 "근무시간"으로 적용해보았다. #include #include #include #include //5일동안..
SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com DFS /** * DFS는 4방 탐색 후 갈 수 있는 곳으로 재귀를 불러 시스템 스택을 쌓는다. * */ public static void DFS(int startR, int startC) { //상 하 좌 우 int[][] drc = {{-1,0},{1,0},{0,-1},{0,1}}; for(int direc=0;direc
1. 부분집합 - power set 공집합일 때 부터 1,2,3의 조합이 모두 들어갈 때 까지 즉, 집합이 0개일 때부터 1개일 때 2개일 때... 전체 다 들어갔을 때를 따져 준다. package arr; import java.util.Scanner; /** * 부분집합 * * * */ public class PowerSet { static int[] arr = {1,2,3}; static int[] sel; static int N; public static void main(String[] args) { N = 3; sel=new int[N]; powerset(0); } static public void powerset(int depth) { if(depth==N) { for(int i=0;i=arr..
1. 이진검색 for package test; import java.util.Arrays; public class 이진검색 { static int[] arr; public static void main(String[] args) { arr = new int[] {5,3,1,2,4}; //이진검색은 반드시 정렬된 상태여야 한다. Arrays.sort(arr); //1 2 3 4 5 System.out.println(binarySearch(3)); } public static int binarySearch(int key) { int start = 0; int end = arr.length-1; System.out.println(Arrays.toString(arr)); while(start key) end=m..
