전체 글

[프로그래머스][Javascript] 완주하지 못한 선수

문제 프로그래머스 해시 문제 - 완주하지 못한 선수 문제 설명 참가한 선수 : n+1명 완주한 선수 : n명 1. 정렬하기 너무 어렵게 생각해서 휘황찬란한 코드가 되어버린 문제. 하지만 단순 for문이나 foreach문을 쓰게 된다면 시간초과로 효율성 검사를 실패하게 된다. 그래서 생각을 하다가 정렬을 해서 값이 다르면 완주하지 못한 선수가 나오겠다는 생각을 했다. 그런데 시간복잡도 생각을 너무 많이 했더니 정렬을 퀵소트로 했다. 퀵소트 평균 Big o가 O(nlogn) 정도이니 빨라질거라 생각을 했는데, 생각해보니 반복하며 배열 값을 비교할 때는 최악의 경우 O(n)의 복잡도가 나오게 된다. 퀵소트를 쓰나 그냥 소트를 쓰나 최종 복잡도 차이는 없었던 것이다. 참고로 퀵소트는 하나의 리스트를 피벗(piv..

[BOJ][Java] 1932번 - 정수 삼각형

문제 백준 1932번 문제: 정수 삼각형 문제 설명 각 층의 모든 칸마다 최댓값을 저장하면서 동적 계획법으로 푸는 문제 최대값을 찾기 위해서는 이전 열에서 최대값을 더해 나가야 한다. 문제의 예제로 이해를 해보자 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5맨 위의 수인 7은 제일 상단에 위치해 3과 8에 각각 7을 더해주면 된다. 그럼 10과 15가 되어 밑의 수들에게 선택을 받게 된다. 하지만 셋째줄의 맨 처음에 있는 8과 0은 선택의 여지가 없이 위의 수를 더해야 한다. 1은 10과 15 중 큰 수인 15를 선택할 수 있다. 이를 이용하여 큰 수를 축적해 나갈 수 있다. 아래 축적된 수를 보자. 7 10 15 18 16 15 20 25 20 19 24 30 27 26 24가장 밑에 줄에 가장..

[BOJ][Java] 1149번 - RGB거리

문제 백준 1149번 문제: RGB거리 문제 설명 i번째 집을 각각의 색으로 칠할 때, 1~i번째 집을 모두 칠하는 최소 비용으로 부분문제를 정의해봅시다. 설명 추가 예정 성공 코드 import java.util.Scanner; public class Main{ public static void main(String[] args){ Scanner s = new Scanner(System.in); int n = s.nextInt(); int[][] rgb = new int[3][n+1]; for (int i = 0; i < n; i++){ rgb[0][i] = s.nextInt(); rgb[1][i] = s.nextInt(); rgb[2][i] = s.nextInt(); } for (int i = 1; i..

[BOJ][Java] 9461번 - 파도반 수열

문제 백준 9461번 문제 : 파도반 수열 문제 설명 피보나치 수와 비슷한 규칙을 찾아 동적 계획법으로 푸는 문제 파도반 수열은 n에서 두번째 수와 세번째 수를 더하면 n의 값이 나오는 문제이다. 재귀로 풀면 시간 초과로 틀린다. 배열에 차곡차곡 담는 식으로 풀어야 한다. 초기값은 처음 3개의 값인 1로 두면 된다. 성공 코드 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); for (int i = 0; i < t; i++) { int n = sc.nextInt(); System.out.print..

[Markdown] table 쉽게 만들기

마크다운 문법으로 테이블 쉽게 만들기 Tables Generator 사이트를 통해 보기 쉽게 틀을 만들 수 있다. 작은 테이블을 만들 때는 그냥 만들어도 상관이 없으나 내용이 많은 테이블은 사이트로 만드는 게 더 편하다. Tables Generator 사용방법 표에 입력할 내용을 차례대로 입력한다. 필요없는 행이나 열은 해당 위치에서 삭제할 수 있다. 추가도 가능하다. Generate 버튼으로 표를 생성한다. copy to clipboard로 복사해 필요한 곳에 넣으면 된다. 깃허브에 출력되는 표

2020년 새해 목표

글 양식은 추후 수정예정

Visual Studio Code 자동 들여쓰기 단축키

Ctrl + K, F 외워지거라..

[BOJ][Java] 1904번 - 01타일

문제 백준 1904번 문제: 01타일 문제 설명 n의 증가로 타일 개수를 세어 봤을 때의 표이다. * n = 11* n = 22* n = 33* n = 45* n = 58* n = 613* n = 721* n = 834* n = 955* n = 1089* n = 11144* n = 12233* n = 13377* n = 14610 n = n-1 + n-2 구조를 띠고 있다. 앞에서 풀었던 피보나치 수와 비슷하게 풀면 된다. 단, 주의할 것은 15746을 나눈 나머지 값으로 저장하면서 for문을 돌아야 한다는 것이다. 성공 코드 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = ..

[BOJ][Java] 1003번 - 피보나치 함수

문제 백준 1003번 문제: 피보나치 함수 문제 설명 단순 재귀로 피보나치 수를 구하면 왜 느릴까요? 함수 호출의 개수가 기하급수적으로 늘어나기 때문입니다. N번째 피보나치 수에서 0이 출력되는 횟수와 1이 출력되는 횟수를 구하는 문제 아래는 각 n마다 0과 1의 출력 횟수를 작성한 것이다. fibo(0) --- 0이 1번 1이 0번 fibo(1) --- 0이 0번 1이 1번 fibo(2) --- 0이 1번 1이 1번 fibo(3) --- 0이 1번 1이 2번 fibo(4) --- 0이 2번 1이 3번 fibo(5) --- 0이 3번 1이 5번 fibo(6) --- 0이 5번 1이 8번 fibo(7) --- 0이 8번 1번 13번 fibo(8) --- 0이 13번 1이 21번 fibo(n)의 1의 횟수 ..

[BOJ][Java] 2748번 - 피보나치 수 2

문제 [백준 2748번 문제: 피보나치 수 2](https://www.acmicpc.net/problem/2748) 피보나치 수 시리즈 문제 풀이 2747번. 피보나치 수 1 2748번. 피보나치 수 2 2749번. 피보나치 수 3 10826번. 피보나치 수 4 10870번. 피보나치 수 5 문제 설명 피보나치 수를 동적 계획법으로 구하는 문제 피보나치 수 1번 문제와 동일한 문제이다. 다른 점은 n이 45에서 90으로 증가했다는 점이다. 이 때문에 수를 저장하는 배열이 long 형태여야 한다. 성공 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputSt..

[BOJ][Java] 2747번 - 피보나치 수

문제 백준 2747번 문제: 피보나치 수 피보나치 수 시리즈 문제 풀이 2747번. 피보나치 수 1 2748번. 피보나치 수 2 2749번. 피보나치 수 3 10826번. 피보나치 수 4 10870번. 피보나치 수 5 문제 설명 동적 계획법으로 피보나치 수를 계산하는 문제 n이 45까지 주어진다. 최대 45까지이므로 배열을 만들 때 int형으로 만들어도 숫자 저장이 가능하다. 1번째와 2번째 값, 즉 n의 값이 0이나 1일 때는 초기값인 0과 1을 반환해야 한다. n이 2 이상일 경우에는 피보나치의 식Fn = Fn-1 + Fn-2을 따라 배열에 저장해 주면 된다. 처음에는 재귀함수로 풀려고 시도했지만 시간 초과가 떠서 재귀로는 풀지 못했다. 성공 코드 import java.io.BufferedReader..

[BOJ][Java] 9663번 - N-Queen

문제 백준 9663번 문제: N-Queen 문제 설명 한줄에 하나의 Queen만 존재 가능하므로 1차원 배열 선언 N+1크기의 배열을 선언한 후 재귀로 경우의 수를 구한다. int array는 선언 시 0으로 초기화되므로 배열 요소가 1부터 시작하도록 한다. array를 0부터 채웠을 때 문제점은 아래의 표를 보면 알 수 있다. 0으로 시작했을 때 디버깅한 것을 보면 값이 중복되어 들어간다. arr[i] == arr[row] 조건에 걸려 false가 리턴되었기 때문이다. 조건 1. 같은 열에 있거나 조건 2. 대각선에 위치할 경우를 제외하고 찾는다. 대각선에 위치하기 위한 조건 (기준 x좌표 값 - 대각선 x좌표값)의 절대값 == (기준 y좌표 값 - 대각선 y좌표값)의 절대값 x의 좌표값끼리의 절대값과..

[Git] 수정, 추가 파일 Commit, push하는 명령어

[Git] 수정, 추가 파일 Commit, push하는 명령어 git init git status git add . git add [filename] git commit -m "message" git log git remote add origin [git repository address] git push origin mastergit commit으로 에디터로 들어갔다면 i // 현재 커서에 입력 "commit message" // 커밋 메시지 입력 ESC // 명령 모드로 전환 !wq // 저장 후 종료깃허브에서 repository 생성 시 readme.md 파일을 생성하도록 만들거나, 올리던 도중에 깃허브에 연결하려고 할 때 git pull origin master --allow-unrelated-h..

[BOJ][Java] 15652번 - N과 M (4)

문제 백준 15652번 문제: N과 M (4) N과 M 시리즈 문제 해설 보러가기 [BOJ][Java] 15649번 - N과 M (1) [BOJ][Java] 15650번 - N과 M (2) [BOJ][Java] 15651번 - N과 M (3) [BOJ][Java] 15652번 - N과 M (4) 문제 설명 15651번 문제에서 비내림차순 조건이 추가된 문제이다. 비내림차순이므로

[BOJ][Java] 15651번 - N과 M (3)

문제 백준 15651번 문제: N과 M (3) N과 M 시리즈 문제 해설 보러가기 [BOJ][Java] 15649번 - N과 M (1) [BOJ][Java] 15650번 - N과 M (2) [BOJ][Java] 15651번 - N과 M (3) [BOJ][Java] 15652번 - N과 M (4) 문제 설명 1부터 n까지 중복 관계 없이 m개를 고르는 문제 15649번 문제에서 중복을 체크할 필요가 없어졌다. 그래서 앞의 문제들과는 다르게 방문 여부를 체크하는 visited 배열을 쓰지 않아도 됐다. 그리고 Scanner를 사용하면 시간 초과로 실패가 나와서 BufferedReader, BufferedWriter를 사용했다. 성공 코드 import java.io.BufferedReader; import j..