분류 전체보기

정렬 알고리즘 (NlogN)

시간 복잡도가 O(NlogN) 인 대표적인 3개의 알고리즘 (Quick / Merge / Heap) 을 알아보고, 정렬 알고리즘의 O(NlogN) 이라는 시간복잡도와 각 언어에서 어떤 정렬 알고리즘이 쓰이는 지 알아보자. Quick Sort (퀵 정렬) 퀵 정렬은 다음과 같은 단계로 진행된다. pivot을 정한다. pivot 기준 왼쪽에는 모두 pivot 값보다 작은 값들을, pivot 기준 오른쪽에는 모두 pivot 값보다 큰 값들이 되게 한다. pivot 기준 왼쪽, 오른쪽 배열을 각각 다시 퀵 정렬한다. 다음과 같은 배열이 있다고 가정하자. 여기서 빨간 색인 4를 pivot으로 정했다고 하자. 위의 2단계를 거치고 나면 다음과 같이 변한다. 이제 왼쪽, 오른쪽 배열에서 다시 pivot을 정하고 정렬..

WAS vs Web Server

우리가 만든 건 웹 서버가 아니다! 우리는 열심히 서버 개발을 해서 사용자가 원하는 서버를 만든다. 하지만 이건 Web Server 가 아니다! Web Server는 단순하게 "웹 페이지를 위한 서버"를 뜻하는 말로 복잡한 뭔가를 하지 않는다고 받아들이면 될 것 같다. 우리가 열심히 코딩해서 만든 서버는 WAS, Web Application Server 이다. 단순한 Web Server가 아니라 Application이 들어갔다. 그럼 Web Server는 도대체 뭘까..? Web Server Web Server는 Apache, NginX로 대표되며, static page를 다루는 서버이다. 경로에 따라서 항상 같은 페이지를 반환한다는 의미이다. 예를 들어서 밑의 사진과 같이 Apache를 설치하면 나오는..

[Programmers] 단어 변환 (Java)

https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 간단한 BFS 문제이다. 알고리즘 begin 문자열과 0을 같이 큐에 넣는다. 큐가 빌 때까지 아래의 실행을 한다. 큐에서 현재 문자열과 단계를 꺼낸다. 모든 진행 가능한 word 문자열에 대해 다음을 실행한다. 만약 해당 문자열에 이미 방문했다면 지나친다. 현재 문자열과 word 문자열의 다른 부분이 1개라면 방문 처리 하고 word를 단계 + 1 해서 큐에 삽입한다. 만약 삽입할 문자열이 ta..

[Programmers] 최고의 집합 (Java)

https://school.programmers.co.kr/learn/courses/30/lessons/12938 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 정말 놀랍게도... 일부러 찾은 문제가 아닌데도... 이전에 문제를 잘못 접근해서 엉뚱한 방식으로 풀었는데 그 방식으로 풀면 되는 문제였다. 알고리즘 그리디 알고리즘이다. 곱의 최대는 똑같이 배분하면 나온다. 즉, 10를 3개로 쪼개서 곱할 때 최대는 [3, 3, 4] 일 때이다. 증명 s = k + k + ... + k 이와 같이 균등하게 분배되어 있을 때, 이게 최선이 아니라고 가정해보자. 그..

[Programmers] 야근 지수 (Java)

https://school.programmers.co.kr/learn/courses/30/lessons/12927 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 숫자의 범위가 큰 수를 처리해야 하므로 일일이 처리하는 게 아니라 그리디라고 착각했다. 쉽게 구할 수 있는 수식이 있을 거라고 생각해 잘못된 생각을 했다. 남은 작업량을 모두 더해 일을 최대한 한 뒤 남은 일에 고르게 분배했다. 하지만 이러면 일이 한 쪽에 치우쳐져 있을 경우를 생각하지 못한다. 그래서 일일이 처리할 수 밖에 없다는 생각이 들었다. 알고리즘 아주 간단하게 생각했을 때 O(N^2)은..

[BOJ] 9019 : DSLR (Java)

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 걸린 시간 : 1시간 4분 C++에서 Java로 옮기려고 하니까 쉬운 코드여도 실수가 엄청 잦고 코드도 깔끔하게 안 써진다... 처음엔 DP로 생각하고 풀려다가,, 그냥 BFS로 밀어버려도 되겠다고 생각해서 중간에 싹 바꿨다. 자료구조 memo배열 : 해당 인덱스까지 오려면 어떤 연산을 거쳐야 하는지에 대한 String형 배열이다. vis배열 : 해당 인덱스에 방문했다면 더 이상 방문..

[BOJ] 14940 : 쉬운 최단거리 (Java)

https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 걸린 시간 : 34분 33초 알고리즘 최단 거리 알고리즘 중 어떤 알고리즘? 최단 거리를 구할 수 있는 알고리즘 중 4가지를 살펴보자. 어떤 한 시작점에서 출발할 경우 모든 시작점을 다 고려할 경우 가중치가 없는 경우 BFS 알고리즘 BFS or 플로이드 알고리즘 가중치가 있는 경우 다익스트라 알고리즘 플로이드 알고리즘 이렇게 4가지를 생각하면 어떤 문..

[BOJ] 2630 : 색종이 만들기 (Java) with 분할 정복

https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 걸린 시간 : 19분 26초 기초적인 분할 정복 문제이다. 분할 정복은 재귀의 한 갈래이다. 재귀를 알 때 제일 중요한 것은 점화식이다. 점화식만 잘 파악하면 끝나는 문제. 알고리즘 색종이를 자를 cut() 메소드를 재귀호출한다. 재귀호출에 필요한 파라미터를 생각해보자. 파라미터의 조합으로 색종이를 자른 한 부분을 특정할 수 있으면 된다! 즉, 시작점이 필요하고, 색종이..

[BOJ] 1927 : 최소 힙 (Java)

https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 걸린 시간 : 5분 18초 정답 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue; public class BOJ1927 { static PriorityQueue pq = new PriorityQueue..

[BOJ] 11444 : 피보나치 수 6 (Java)

https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 걸린 시간 : 36분 32초 재밌을 것 같아서 도전! 했는데,, 숫자가 너무 크다. 이러면 무조건 O(logN) 알고리즘을 써야 하고, 그렇단 말은 F(2n) 과 F(n) 과의 관계를 알아내면 끝이다. ... ... 도대체 무슨 관계가 있는지 전혀 감도 안 오고 배운 적도 없는 것 같다.. 이런 너무 수학적인 주제를 공부할 시간에 코딩 공부를 좀 더 하자는 핑계 생각에 잠깐 검색을 해보았더니 이런 식이 나온다. 이걸 제가 어떻게 알아요 이 식의 m에 n, n+1 을 대입해 ..