두부의 코딩일기

싱글톤 패턴은 생성자가 여러 번 호출 되더라도 실제로 생성되는 객체는 하나이며 최초로 생성된 이후에 호출된 생성자는 이미 생성한 객체를 반환시키도록 만드는 디자인 패턴이다. 간단하게 설명하자면 단 하나의 인스턴스만 생성하여 사용하는 디자인 패턴을 의미한다. ✅ 디자인 패턴 프로그램을 설계할 때 발생했던 문제점들을 객체 간의 상호 관계 등을 이용하여 해결할 수 있도록 하나의 규약 형태로 만들어 놓은 것을 의미함. 일종의 설계 기법으로 SW 재사용성, 호환성, 유지 보수성을 위함이다. ✅ 싱글톤을 사용하는 이유 객체는 생성할 때마다 메모리 영역을 할당받아야한다. 싱글톤을 사용하게 되면 한 번의 객체를 생성하기 때문에 메모리 낭비를 방지할 수 있다. 또한, 이미 생성된 인스턴스를 활용하기 때문에 속도 측면에서..

10431번: 줄세우기 (acmicpc.net) 10431번: 줄세우기 초등학교 선생님 강산이는 아이들을 데리고 단체로 어떤 일을 할 때 불편함이 없도록 새로 반에 배정받은 아이들에게 키 순서대로 번호를 부여한다. 번호를 부여할 땐 키가 가장 작은 아이가 1 www.acmicpc.net 풀이 "줄서기가 끝났을 때 학생들이 총 몇 번 뒤로 물러서게 될까?" 줄 서는 조건이 거창하지만 엄청 쉬운 문제였다. 반복문으로 앞에 키 큰 사람이 몇 명인지 세주면 간단하게 해결할 수 있다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedRea..

안녕하세요. N년차 웹 개발자입니다. 저는 웹 개발을 하면서 이 페이지가 어떻게 동작하는지에 대해서 알아야 된다고 생각합니다. 그렇다면 사용자가 주소창에 www.google.com 혹은 www.naver.com 을 입력하면 무슨 일이 발생할까요? 우리가 사는 집 주소가 존재하듯이 웹 브라우저도 주소가 있다. 모든 사람에게 '수원역 1번 출구'로 오세요. 라고 한다면 한 명도 빠짐없이 수원역 1번 출구로 올 것이다. 웹 브라우저도 google.com 혹은 naver.com 처럼 고유 주소가 존재하고 이것을 URL이라고 부른다. 웹 브라우저 동작 방식 1. 사용자가 google.com 을 검색 2. 웹브라우저는 캐싱된 DNS 기록들을 해당 도메인 주소와 대응하는 IP 주소를 확인 DNS는 웹사이트 이름과 I..

카운팅 정렬 Counting Sort 카운팅 정렬은 시간 복잡도 O(n) 을 가지고 있기 때문에 많은 정렬 알고리즘 중에서 좋은 성능을 갖고 있다. 빠른 정렬 알고리즘에 속하는 퀵 정렬 (Quick Sort), 힙 정렬 (Heap Sort), 합병 정렬 (Merge Sort) 등의 평균 시간 복잡도가O(nlogn) 인 것을 보면 엄청난 속도를 가지고 있다는 것을 알 수 있다. 이처럼 빠른 속도를 가졌음에도 정렬이 필요한 상황에서는 퀵 정렬을 주로 사용한다. 그 이유에 대해서 알아보자. 정렬 과정 카운팅 정렬은 데이터 값이 몇 번 나왔는지 세주는 것이다. 정렬의 이름처럼 수를 counting 해주는 것. 다음과 같은 배열이 있다고 가정해보자. 1. 배열을 쭉 돌면서 해당 값을 index로 하는 새로운 배열..

2075번: N번째 큰 수 (acmicpc.net) 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 풀이 N*N 크기의 2차원 배열에서 N번째 큰 수를 찾으면 된다. 우선순위 큐를 사용하면 쉽게 해결할 수 있다. 기본적으로 오름차순으로 정렬되기 때문에 N번째 큰 수를 찾기 위해서는 정렬을 재정의해주어야 한다. 단순 integer형 큐이기 때문에 Collections.reverseOrder() 를 사용해서 역순으로 정렬해 주었다. 이후에 N-1번째까지 pq.poll()을 해주고, pq.poll()을 한 번 더 사용해서..

1244번: 스위치 켜고 끄기 (acmicpc.net) 1244번: 스위치 켜고 끄기 첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 켜져 있으면 1, 꺼져있으면 0이라고 표시하고 사이에 빈칸이 하나씩 www.acmicpc.net 풀이 딱히 풀이라고 할 게 없는 문제다. 그냥 문제에서 시키는대로 해주면 된다. 번호가 주어졌을 때 남학생일 경우 번호의 배수에 해당하는 스위치 상태를 변경해주면 된다. 예를 들어 3이 주어졌다면 3, 6, 9, ··· 를 변경해준다. 여학생일 경우 번호의 양 옆 스위치 상태를 확인하고 서로 다를 때까지 비교해준다. 두 개의 스위치 값이 같다면 변경해주고, 다르면 탐색을 중단한다. 예를 들어 3이 주어..

https://www.acmicpc.net/problem/20926 20926번: 얼음 미로 탐험가 테라는 얼음 미로에 갇혔다. 얼음 미로의 바닥은 빙판으로 되어 있어 발을 내디디면 바위에 부딪힐 때까지 미끄러진다. 예를 들어, 위 그림에서 테라가 왼쪽 방향으로 이동한다면 중간에 www.acmicpc.net 풀이 포켓몬 얼음동굴이 생각나는 다익스트라 문제. 테라, 바위, 구멍, 출구가 char형이라서 int형으로 임의의 값을 줘서 int형 배열로 선언했다. static int Rock = 100, Hole = -1, Escape = 200, W, H; for (int i=0; i= W) break; if (map[nx][ny] == Hole) break; if (map[nx][ny] == Rock) { ..

https://www.acmicpc.net/problem/1106 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net 풀이 "호텔의 고객을 적어도 C명 늘리기 위해 형택이가 투자해야하는 돈의 최솟값을 구하시오." 문제 요구사항에서 주목해야할 건 "적어도 C명"이다. 만약 목표치가 10명인데 11명, 12명을 모집했을 때가 더 비용이 적게 든다면 그 비용을 출력해야한다. 예제 2번을 보면 쉽게 이해할 수 있다. 3명 모집 -> 1원 6명 모집 -> 2원 9명 모집 -> 3원 10명 모집 -> 6원 11명 모집 ..

엑셀에서 어떤 값을 찾거나 바꾸고 싶을 경우에 '찾기 및 바꾸기' 기능을 활용한다. 하지만 다른 값에 포함된 임의의 값만 바꾸고 싶을 때 문제가 어떻게 해야될지 몰라서 고민한 적이 있을 것이다. 위 예시 데이터를 보겠다. 예를 들어 '0'인 값만 삭제하고 싶을 경우 '찾기 및 바꾸기' 기능을 사용하면 아래와 같은 경우가 생긴다. '0'인 값만 삭제하고 싶은데 모든 '0'이 다 검색되서 총 53개의 항목이 바뀌는 것을 볼 수 있다. 그렇다면 어떻게 해야 '0'인 값만 삭제할 수 있을까? 1. 바꾸고자하는 내용을 드래그 후에 Ctrl + H 를 눌러서 찾기 및 바꾸기 창을 연다. 2. [모두 찾기] 버튼을 누른다. 3. 값을 더블 클릭해서 아래와 같이 만든다. 4. 첫번째 줄을 클릭 후에 '0' 값만 가진 ..

https://www.acmicpc.net/problem/11067 11067번: 모노톤길 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 개수 T가 정수로 주어진다. 각 테스트 데이터의 첫 번째 줄에는 카페의 수 www.acmicpc.net 풀이 제한 시간이 5초로 엄청 길고, n의 범위가 최대 100,000 이므로 T의 값에 따라서 완전 탐색도 충분히 가능하다고 본다. 문제 조건에는 "x축의 값이 작아지는 경우는 없어도 출구까지 도달할 수 있다." 이다. 따라서 카페 방문 순서는 아래와 같다. 1. 현재 위치와 같은 x축에 있는 카페들 중 가까운 카페부터 방문한다. 2. 현재 위치와 같은 x축의 카페를 모두 방문했다면 y축이 동일한 ..