알고리즘 문제풀이
1.백준 1712번 자바 : 손익분기점
A/(C-B)가 소수점으로 떨어질 수 있는거 아닌가????했지만... int 나누기 int = int이래서 자바 기초가 중요합니다 ㅎㅎ
2.백준 2869번 자바 : 달팽이는 올라가고 싶다
올라가는 날을 x라고 가정하고,(x-1)일 동안은 무조건 a-b 만큼 올라감마지막날 올라가는게 최대 a(a-b)(x-1) + a >= vx >= (v-a)/(a-b) + 1
3.백준 10250번 자바 : ACM 호텔
n%h 이 0일 때를 고려해야 함!!
4.백준 2775번 자바 : 부녀회장이 될테야
2차원 배열을 활용한다
5.백준 2839번 자바 : 설탕 배달
5키로 봉지의 우선순위가 더 높으므로 5로 나눈 몫을 먼저 따진 다음 나머지를 3으로 나누어 계산한다.끝까지 계산이 안된다면 초기값인 -1로 출력한다.
6.백준 10757번 자바 : 큰 수 A+B
java.math.BigInteger 사용더하고자 하는 자릿수만큼의 배열 생성하여 올림하면서 계산
7.백준 1978번 자바 : 소수 찾기
에라토스테네스의 체한편, 에라토스테네스의 체를 이용해 1~n까지의 소수를 알고 싶다면, n까지 모든 수의 배수를 다 나눠 볼 필요는 없다. 만약 n보다 작은 어떤 수 m이 m=abm=ab라면 aa와 bb 중 적어도 하나는 루트n 이하이다. 즉 n보다 작은 합성수 m은
8.백준 2581번 자바 : 소수
import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main { public static void main(String[] args) {
9.백준 1929번 자바 : 소수 구하기
처음에는 이렇게 풀었는데 시간이... 너무 오래 걸려서 다시!!
10.에라토스테네스의 체
가장 대표적인 소수(Prime Number) 판별 알고리즘이다. 소수란 '양의 약수를 두 개만 가지는 자연수'를 의미한다. 시간복잡도는 O(N)이다. 모든 경우의 수를 다 돌며 약수 여부를 확인한다는 점에서 비효율적이다. n까지의 자연수 중에서 소수인 수를 구한
11.백준 4948번 자바 : 베르트랑 공준
`
12.백준 9020번 자바 : 골드바흐의 추측
13.백준 1085번 자바 : 직사각형에서 탈출
14.백준 3009번 자바 : 네 번째 점
15.백준 4153번 자바 : 직각삼각형
16.백준 10872번 자바 : 팩토리얼
17.백준 10870번 자바 : 피보나치 수 5
18.[프로그래머스] 해시 - 완주하지 못한 선수(자바)
19.[프로그래머스] 해시 - 전화번호 목록(자바)
20.[프로그래머스] 해시 - 위장(자바)
21.[프로그래머스] 해시 : 베스트앨범(자바)
22.[프로그래머스] 스택/큐 - 기능개발(자바)
23.[프로그래머스] 스택/큐 - 프린터(자바)
24.[프로그래머스] 스택/큐 - 다리를 지나는 트럭(자바)
25.[프로그래머스] 주식 가격(자바)
26.[프로그래머스] 힙 - 더 맵게(자바)
27.[프로그래머스] 정렬 - K번째수 (자바)
28.[프로그래머스] 완전탐색 - 모의고사 자바
29.백준 15649 c++ : N과 M(1) - 백트래킹 기본
30.백준 9663번 c++ : N-Queen
한 줄에 하나만 놓을 수 있다.1\. y축 중복 확인2\. 왼쪽 아래 -> 오른쪽 위 대각선 방향 확인3\. 왼쪽 위 -> 오른쪽 아래 대각선 방향 확인
31.백준 6593번 c++ : 상범 빌딩
평범한 BFS문제인데 3차원 배열이 필요해서 pair대신 tuple을 사용하여야 한다.
32.백준 15683번 c++ : 감시
진수법으로 모든 경우의 수를 구할 수 있다. cctv가 한 대도 없는 경우 고려 필요 dir로 취할 수 있는 값은 0,1,2,3인데 +1,+2,+3,+4해버리면 4,5,6,7로 넘어올 수 있으므로 dir %= 4를 해주어야 함.
33.백준 18808번 c++ : 스티커 붙이기
스티커를 붙일 수 있는 노트의 범위 고려(경계값 주의)90도 회전, i,j의 규칙 찾기
34.백준 15686번 c++ : 치킨배달
brute라는 백터에 m개 치킨집을 1로 설정하고 나머지는 0으로 설정한 후 next_permutaion을 사용하면 중복되지 않는 치킨집 조합을 만들어 낼 수 있다.
35.백준 14503번 c++ : 로봇 청소기
36.백준 14891번 c++ : 톱니바퀴
37.백준 13335번 c++ : 트럭
38.백준 5427번 자바 : 불
BFS
39.백준 1003번 자바 : 피보나치 함수
다이나믹 프로그래밍
40.백준 14501번 자바 : 퇴사
백트래킹 or DP
41.백준 15988번 자바 : 1,2,3 더하기 3
다이나믹 프로그래밍 - int 오버플로우에 유의
42.백준 2302번 자바 : 극장 좌석
다이나믹 프로그래밍 : dp 배열의 크기, ArrayIndexOutOfBounds 유의!
43.백준 2293번 자바 : 동전1
다이나믹 프로그래밍/ 동전의 합 경우의 수 구하기 (북마크)
44.백준 4883번 자바 : 삼각 그래프
다이나믹 프로그래밍
45.백준 11053번 자바 : 가장 긴 증가하는 부분 수열
x번째 값이 가지는 가장 긴 증가하는 부분수열의 길이를 구하고 싶다면 , 1 ~ x - 1번째 값들 중, x번째 값 보다 더 작은 숫자들이 갖는 부분수열의 길이 중, 가장 길이가 긴 부분수열의 길이에 + 1을 한 값이, x번째 값이 가지는 가장 긴 증가하는 부분 수열의