일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 이분탐색
- 디베이스앤 인턴 후기
- DBASE&
- 그리디
- IT 면접 준비
- CJ DBASE&
- 면접 필수 질문
- 이중우선순위큐 java
- 백트래킹
- 프로그래머스 이중우선순위큐 java
- 이중우선순위큐 자바
- oracle ansi sql
- 백준
- ansi sql 단점
- 프로그래머스
- BFS
- Spring Boot
- Java
- 프로그래머스 이중우선순위큐 자바
- JPA
- 위상정렬
- 개발자 면접 준비
- 프로그래머스 이중우선순위큐
- ansi sql 장점
- DP
- SQL
- 디베이스앤
- DFS
- oracle ansi
- Gradle
- Today
- Total
목록알고리즘 (76)
쉬운 프로그래밍
www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 아이디어를 생각 해내면 그렇게 어렵지는 않은 문제같다... 물론.. 생각해내면.. 입력으로 지도의 2차원 배열 정보가 주어진다. BFS를 통해서 한 섬에서 다른 섬을 이어주는 최소비용을 구해야한다. 이 문제를 풀기 위해서는 섬과 바다가 맞닿아있는 지점을 반복문을 통해 BFS를 돌려 최소의 거리를 찾아야한다. 여기까지는 어렵지 않게 생각을 했긴 하지만, 해당 지점이 섬과 맞닿아있는지 판별하는 것과 다른 섬에 도착하여 ..
www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 이전에 풀었던 문제와 마찬가지로 별 다른 응용 없이 위상정렬을 구현하는 문제이다. 다만 이 문제는 우선순위큐를 사용해야 한다. 문제에서 주어진 입력의 그래프를 그리면 아래와 같다. 일반 큐를 사용하여 위 그래프를 위상정렬 시키면 (물론 여러가지 경우가 있지만 반복문 돌아가는 순서대로 하면) 3 -> 4 -> 1 -> 2 위와 같은 순서로 정렬이 될텐데, 문제에서는 가능하다면 "작은..
www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net 위상정렬을 통한 문제 풀이라기 보다는 위상정렬 그 자체를 구현하는 문제라고 생각한다. 따로 설명은 필요 없을것 같다. 이해가 가지 않는다면 나동빈님 블로그(m.blog.naver.com/ndb796/221236874984)를 참고해서 공부해보자. 소스코드 import java.io.BufferedReader; import java.io.IOException; import java..
www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 이분 탐색 문제이다. right값을 통나무중에서 가장 긴 통나무로 초기화 해준 후 m에 가장 근접하는 값을 찾아주면 된다. 맞왜틀..이 계속 나왔는데 뭔지 보니까 통나무의 길이가 최대 10억까지 들어갈 수 있으므로 구하는 과정에서 int값을 넘어가기 때문이였다. 단위!!! 한번씩 꼭 확인하는 습관을 들여야겠다. 소스코드 import java.io.BufferedReader..
www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 이분 탐색의 기초적인? 문제인것 같다. 이분 탐색 알고리즘의 개념이 제대로 잡혀있지 않았던 상태여서 풀이를 하는데 오래걸렸다. 각 부서별로 예산이 주어지고, 예산이 부족한 경우에 상한선을 정해서 상한선을 초과하는 예산을 요구하는 부서는 상한선 까지만 예산을 부여한다. 이 상한선을 찾기 위해 그냥 완탐을 돌려버리면 시간초과가 뜨기 때문에 이분 탐색이 필요하다. start를 0, end를 최대 예산으로 설정하..
www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 그리디 보다는 문자열 파싱하는게 주된 문제인 것 같다. 풀이과정을 요약하자면, 55-50+40 이라는 문자열에 임의로 괄호를 씌워 최소값을 만드는 문제이다. -> 55-(50+40) 최소값을 구하기 위해서는 '큰 숫자를 빼야한다' 즉 덧셈에 괄호를 씌워 먼저 계산하여 큰 수를 만들어 빼는 것이다. 이를 위해서 '-'로 토큰을 만든 다음 그 토큰 안에서 '+'를 통해 또 토큰을 나눈다. 소스코드 import..
www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제만 이해하면 크게 어려울 것 없는 문제다. 돈을 인출하는데 필요한 시간이 적은 사람부터 뽑아야 시간의 합의 최솟값을 구할 수 있다. 따라서 p 배열을 먼저 정렬한 후, 이전값을 통해 걸린 시간의 총합을 구한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import jav..
www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 희의 종료시간이 빠른 순으로 정렬하고 회의시간이 겹치지 않는 경우를 카운팅 하면 되는 문제다. 이해가 가지 않으면 st-lab.tistory.com/145의 그림을 참고하면 쉽게 풀 수 있을 것이다. 코드 설명은 주석으로 달았다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util...