백준

[BOJ 11053] 가장 긴 증가하는 부분 수열(javascript): DP LIS

문제 설명 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. let n = 8; let arr = [5, 3, 7, 8, 6, 2, 9, 4]; console.log(solution(n, arr)); function solution(n, arr){ if (n === 1) return 1; let dp = Array.from({length: n}, () => 0); let answer = 0; dp[0]=1; for (let i=1; i=0; j--){ if (arr[i] > arr[j]..

[BOJ/1987번] 알파벳

문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다. 입력값 첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다. I..

[BOJ/4963번]섬의개수(java) : DFS

문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다. 입력값 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다. 입력의 마지막 줄에는 0이 두 개 주어진다. Input 1 1 0 2 2 0 1 1 0 3 2 1..

PriorityQueue : 우선순위 큐(Java)

우선순위 큐(Priority Queue) BOJ 11656 기본문제를 보다가 우선순위 큐를 적용해서 풀어보았다. 쉽게도 풀 수 있지만, 요즘에는 최대한 시간복잡도를 줄이면서 풀도록 노력하고 있다. N의 최댓값이 1000이고 O(N2)이라 시간초과가 나지 않을거 같긴한데 PriorityQueue로 O(N)으로 순서를 직접적으로 정렬하면서 진행한다면 훨씬 수월할 거라 판단. 구현을 시작했다. 접미사 배열은 문자열 S의 모든 접미사를 사전순으로 정렬해 놓은 배열이다. baekjoon의 접미사는 baekjoon, aekjoon, ekjoon, kjoon, joon, oon, on, n 으로 총 8가지가 있고, 이를 사전순으로 정렬하면, aekjoon, baekjoon, ekjoon, joon, kjoon, n,..

[그래프 위상정렬] Topological Sort : Java

그래프 위상정렬: Topological Sort BFS&DFS를 계속 공부하다가 위상정렬도 요즘 핫(?)하다길래 따로 공부하는 중이다. 위상정렬은 그래프 정렬의 일종인데 이것이 가능하기 위해선 순환성을 가져서는 안된다. 즉 순환없는 방향성을 가진 계층적 정렬이 가능해야 위상정렬이 가능하다. 조건식으로 나타내면 다음과 같다. 1. 1 -> 2 -> 3 -> 4 와 같은 관계가 성립되어야 한다. 2. A -> B | B

[백준/2959번] 거북이(COCI 2008/2009) [Java]

문제 거북이는 이제 어떤 것에도 흥미를 느끼지 않는다. 그 이유는 거북이가 300년동안 살았고, 그 동안 모든 것들을 다 해보았기 때문이다. 거북이는 시간을 떼우는 무엇인가를 하려고 한다. 이번 주말에 거북이는 거북이 세계에서 매우 유명한 게임인 "가장 큰 직사각형 만들기"를 해보려고 한다. 이 게임을 시작하기 전에 거북이는 양의 정수 네 개를 머릿 속에 생각해야 한다. 한 방향으로 움직이기 시작하고 90도 회전한 뒤에 새로운 방향으로 움직인다. 이런 식으로 세 번 90도 회전을 하고, 네 번 앞으로 움직여서 선 분 네 개를 만들어야 한다. 거북이가 선분을 그릴 때 움직여야 하는 걸음의 수는 생각해 놓은 네 정수중 하나이다. 이때, 한 정수를 각각 한 번씩 사용해야 한다. 거북이가 정수를 사용하는 순서에..

[백준/1181번] 단어 정렬[Java]

문제 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오. 길이가 짧은 것부터 길이가 같으면 사전 순으로 입력 첫째 줄에 단어의 개수 N이 주어진다. (1≤N≤20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. 출력 조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다. 풀이 n개의 testcase를 int형으로 입력받고 arr배열에 String값들을 입력받아준다. 이후 Comparator를 통해서 길이를 우선적으로 오름차순정렬해주고 만약에 길이가 같다면 o1과 o2를 사전순으로 정렬해준다. 여기서 같은 값..

[백준/10814번] 나이순정렬 [Java]

문제 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다. 출력 첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다. 풀이..

[백준/1735번] 분수 합 (유클리드 호제법 응용)[Java]

문제 분수 A/B는 분자가 A, 분모가 B인 분수를 의미한다. A와 B는 모두 자연수라고 하자. 두 분수의 합 또한 분수로 표현할 수 있다. 두 분수가 주어졌을 때, 그 합을 기약분수의 형태로 구하는 프로그램을 작성하시오. 기약분수란 더 이상 약분되지 않는 분수를 의미한다. 입력 첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. 출력 첫째 줄에 구하고자 하는 기약분수의 분자와 분모를 뜻하는 두 개의 자연수를 빈 칸을 사이에 두고 순서대로 출력한다. 풀이 분수 1과 2를 입력받고 분모의 최소 공배수를 찾는다(유클리드 호제법(a*b/a와b의 최대공약수)). 그리고 분자에 분자*(분모/최대공약수)를 통해서 만약 2/7..

[백준/3036번] 링 (COCI 2006/2007)[Java]

문제 상근이는 창고에서 링 N개를 발견했다. 상근이는 각각의 링이 앞에 있는 링과 뒤에 있는 링과 접하도록 바닥에 내려놓았다. 상근이는 첫 번째 링을 돌리기 시작했고, 나머지 링도 같이 돌아간다는 사실을 발견했다. 나머지 링은 첫 번째 링 보다 빠르게 돌아가기도 했고, 느리게 돌아가기도 했다. 이렇게 링을 돌리다 보니 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 도는지 궁금해졌다. 링의 반지름이 주어진다. 이때, 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 돌아가는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 링의 개수 N이 주어진다. (3 ≤ N ≤ 100) 다음 줄에는 링의 반지름이 상근이가 바닥에 놓은 순서대로 주어진다. 반지름은 1과 1000를 포함하는 사이의 자연수이다. 출..

[백준/4948번] 베르트랑 공준(2011 Japan Domestic Contest ) [Java]

문제 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다. 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23) n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하며, 한 줄로 이루어져 있다. (n ≤ 123456) 입력의 마지막에는 0이 주어진다. 출력 각 테스트 케이스에 대..

[백준/15820번] 맞았는데 왜 틀리죠?(2018 Ajou Porgramming Contest)[Java]

문제 '테스트케이스(TestCase)'란 사용자가 제출한 코드가 옳은 답을 출력하는지 판단하기 위한 데이터다. 한 문제는 여러 개의 테스트케이스를 가지며, 문제를 '맞았다'는 것은 해당 문제의 모든 테스트케이스를 통과했다는 것을 의미한다. 즉, 하나의 테스트케이스라도 틀린다면 해당 문제는 틀린 것이 된다. 그림1. 실제 대회 시스템의 채점 방식을 나타내는 그림 테스트케이스 중 일부는 유저에게 공개되며, 일부는 공개되지 않는다. '샘플 테스트케이스'란 문제의 이해를 돕기 위해 유저에게 제공된 데이터다. 시스템이 코드를 채점할 때에는 이 외에도 공개되지 않은 '시스템 테스트케이스'를 통해 추가로 답을 검증한다. 따라서 유저는 코드를 작성할 때 제한 내의 모든 데이터를 고려해야 한다. 만영이는 샘플 테스트케이..

[백준/2108번] 통계학 [Java]

문제 수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자. 산술평균 : N개의 수들의 합을 N으로 나눈 값 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값 최빈값 : N개의 수들 중 가장 많이 나타나는 값 범위 : N개의 수들 중 최댓값과 최솟값의 차이 N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. 출력 첫째 줄에는 산술평균을 출력한다. 소수점 이하 첫째 자리에서 반올림한..

[백준/17248번] 물리 공부 [2019 전북대학교 프로그래밍 경진대회]

문제 전북대학교 컴퓨터공학부 신입생인 시현이는 공대 필수 교양인 기초물리를 수강중이다. 공부를 열심히 하는 시현이는 물리 문제집를 풀다가 다음과 같은 문제를 만났다. 평소 물리를 좋아하던 시현이는 ㄱ, ㄴ번은 단숨에 알았지만, ㄷ번을 풀 수 없어 절망에 빠져 있다. 절망에 빠져있는 시현이를 도와주도록 하자. 입력 첫째 줄에 테스트케이스 T를 입력한다. (1 ≤ T ≤ 100) 다음 줄부터 각 테스트케이스마다 자동차 A와 자동차 B의 속력 X, Y, 그리고 자동차 A의 가속도 Z가 주어진다. (각각의 입력은 띄어쓰기로 구분한다.) 단, 0 ≤ X < Y ≤ 10,000이고, 0

[백준/10219번] Meats On The Grill (Coder's High 2014)[Java]

문제 Coders High 2014가 끝났다. 저녁 회식은 취소되었기 때문에 참가자들은 뿔뿔이 흩어져 저녁식사를 하기 위해 떠났다. 사람들이 모여서 먹는 저녁식사 중에서도 가장 대중적인 것은 고기! Coders High의 출제진들도 고깃집에 와서 고기를 시켰다. 명우는 고기를 구워야 하는 중책을 맡게 되었으므로 불판 위에 고기들을 얹었다. 뛰어난 문제 해결 능력을 가진 명우는 불판 위의 고기를 다음과 같이 모델링하기로 했다. 편의상 불판을 H × W개의 칸으로 이루어진 격자로 나타내기로 하고, 고기는 격자의 여러 칸 위에 걸쳐 있는 것으로 표현한다. 또한 고기가 격자 위에 올라와 있으면, 격자를 가득 채우게 된다고 생각한다. 시간이 지나 현재 아래쪽 면은 적당히 구워졌기 때문에 고기를 뒤집을 시간이 되었..

[백준/2566번] 최댓값 [Java]

문제 과 같이 9×9 격자판에 쓰여진 81개의 자연수가 주어질 때, 이들 중 최댓값을 찾고 그 최댓값이 몇 행 몇 열에 위치한 수인지 구하는 프로그램을 작성하시오. 예를 들어, 다음과 같이 81개의 수가 주어지면 이들 중 최댓값은 90이고, 이 값은 5행 7열에 위치한다. 입력 첫째 줄부터 아홉 번째 줄까지 한 줄에 아홉 개씩 자연수가 주어진다. 주어지는 자연수는 100보다 작다. 출력 첫째 줄에 최댓값을 출력하고, 둘째 줄에 최댓값이 위치한 행 번호와 열 번호를 빈칸을 사이에 두고 차례로 출력한다. 최댓값이 두 개 이상인 경우 그 중 한 곳의 위치를 출력한다. 풀이 다중배열을 이용해서 풀면 쉬운문제. 값을 입력받을 때 max와 그에 따른 i,j값을 저장해서 그대로 출력하였다.ㅇㅅㅇ 1 2 3 4 5 6..

[백준/7568번] 덩치(한국정보올림피아드 2013)[Java]

문제 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x,y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x,y), (p,q)라고 할 때 x>p 그리고 y>q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다. 예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56,177), (45,165) 라고 한다면 A의 덩치가 B보다 큰 셈이 된다. 그런데 서로 다른 덩치끼리 크기를 정할 수 없는 경우도 있다. 예를 들어 두 사람 C와 D의 덩치가 각각 (45, 181), (55,173)이라면 몸무게는 D가 C보다 더 무겁고, 키는 C가 더 크므로, "덩치"로만 볼 때 C와 D는 누..

[백준/5533번] 유니크(JOI 2013)[Java]

문제 상근이와 친구들은 MT에 가서 아래 설명과 같이 재미있는 게임을 할 것이다. 각 플레이어는 1이상 100 이하의 정수를 카드에 적어 제출한다. 각 플레이어는 자신과 같은 수를 쓴 사람이 없다면, 자신이 쓴 수와 같은 점수를 얻는다. 만약, 같은 수를 쓴 다른 사람이 있는 경우에는 점수를 얻을 수 없다. 상근이와 친구들은 이 게임을 3번 했다. 각 플레이어가 각각 쓴 수가 주어졌을 때, 3번 게임에서 얻은 총 점수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 참가자의 수 N이 주어진다. (2 ≤ N ≤ 200) 둘째 줄부터 N개 줄에는 각 플레이어가 1번째, 2번째, 3번째 게임에서 쓴 수가 공백으로 구분되어 주어진다. 출력 각 플레이어가 3번의 게임에서 얻은 총 점수를 입력으로 주어진 순서대로 ..

[백준/3034번] 앵그리 창영(COCI 2006/2007) [Java]

문제 창영이는 화가나서 성냥을 바닥에 던졌다. 상근이는 바닥이 더러워진 것을 보고 창영이를 매우 혼냈다. 강산이는 근처에서 박스를 발견했다. 상덕이는 강산이가 발견한 박스를 상근이에게 주었다. 상근이는 박스에 던진 성냥을 모두 담아오라고 시켰다. 하지만, 박스에 들어가지 않는 성냥도 있다. 이런 성냥은 박스에 담지 않고 희원이에게 줄 것이다. 성냥이 박스에 들어가려면, 박스의 밑면에 성냥이 모두 닿아야 한다. 박스의 크기와 성냥의 길이가 주어졌을 때, 성냥이 박스에 들어갈 수 있는지 없는지를 구하는 프로그램을 작성하시오. 창영이는 성냥을 하나씩 검사한다. 입력 첫째 줄에 던진 성냥의 개수 N과 박스의 가로 크기 W와 세로 크기 H가 주어진다. (1 ≤ N ≤ 50, 1 ≤ W, H ≤ 100) 다음 N개..

[백준/12354번] Ocean View(Small)(Code Jam for Veterans 2013)[Java]

Problem Ocean View is a small town on the edge of a small lake, populated by people with high self-esteem. There is only one street in this town, Awesome Boulevard, running away from the lake on the west towards the hill in the east. All of the houses in Ocean View are situated along one side of Awesome Boulevard and are numbered starting at #1 on the edge of the lake all the way up to #N at the..