Baekjoon Online Judge

[BOJ] 9251 : LCS (Java)

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 걸린 시간 : 1시간 13분 난이도 좀 더 쳐줘요.. LCS를 알면 제일 기초여서 난이도가 낮게 책정된 듯. 처음에 무슨 생각이었는지 N 이 1000인데도 불구하고 시간제한이 걸려있어서 O(N^2) 이 불가능하다고 생각했다. 그러다 O(N^2)이 가능한 것을 알고 표를 무작정 그려봤는데,,, 감은 왔지만 정확한 점화식을 생각해내지 못했다. 결국, 답을 ..

[BOJ] 1987 : 알파벳 (Java)

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 걸린 시간 : 23분 22초 전형적인 백트래킹 문제이다. 단, 재귀함수 호출 시 알파벳을 지나갔는지에 대한 검사도 해야 한다. 이 검사에는 HashSet 자료구조를 썼다. 정답 코드 import java.io.*; import java.util.*; public class BOJ1987 { static int R, C; static String[] board = new String[21];..

[BOJ] 1744 : 수 묶기 (Java)

https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 걸린 시간 : 25분 2초 알고리즘 두 수를 묶는다는 것은 곱한다는 것이다. 따라서 음수끼리 혹은 양수끼리 곱해야 한다. 즉, 음수가 짝수라면 작은 음수부터 차례대로 묶어가면 끝이다. 양수도 마찬가지로 짝수라면 큰 수부터 차례대로 묶어가면 된다. 만약 양수가 홀수라면 가장 작은 양수를 묶지 않고 즉시 더해주면 된다. 만약 음수가 홀수라면 가장 큰 음수를 즉시 더해주면 된다. 단, 만약 수열에 0..

[BOJ] 21608 : 상어 초등학교 (Java) with 정렬

https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 걸린 시간 : 1시간 4분 복잡한 문제같지만 자리를 주어진 조건에 맞게 정렬해서 한 명 한 명 자리에 앉히면 된다. 정렬 Java에서 복잡한 정렬을 하는 방법은 여러가지가 있다. Comparator 인터페이스의 compare 함수를 직접 구현하기 람다식을 활용해 익명 객체 사용해 구현하기 메서드 참조와 유틸리티 메서드 사용하기 나는 2번을 이용해 문제를 풀었다. 아래는 int 형 변수 ..

[BOJ] 1941: 영역 구하기 (Java)

https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 걸린 시간 : 47분 8초 (자바 미숙) 자바로 코테가 미숙해서 열심히 푸는 중...!! 자바 언어에 익숙해지고자 풀어봤다. 문제에서 입력할 때 M, N 순서로 주기도 하고 N, M 순서로 주기도 해서 주의해야 한다. 알고리즘 영역이 100 X 100 이하이므로 이 크기의 2차원 배열을 만들어 입력 받을 때 칠해진 곳을 체크한다. 그 후 DFS로 방문체크를 하며 연결요소의 수를..

[BOJ] 1941: 소문난 칠공주 (Java) with 조합

https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 이전에 C++로 푼 문제이다. https://morenow.tistory.com/21 [BOJ] 1941: 소문난 칠공주 (C++) with 조합 https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생 morenow.tist..

[BOJ] 1520 : 내리막 길 (C++) with Top Down DP

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 걸린 시간 : 32분 21초 알고리즘 처음엔 간단한 DFS로 접근했다가 시간초과가 났다. 그제서야 시간복잡도를 체크해보니 최대 4^(500*500) 번의 실행이 일어날 수 있었다. 따라서 다른 방법을 찾아야 했다. 바로 떠올린 것이 DP였다. 예제를 다시 따라해보니 같은 실행을 너무 과도하게 반복한다는 생각이 들었다. DP에서 제일 중요한 것은 일반항이다. 잘 적용할 수 있는 일반항을 생각해보았다. p..

[BOJ] 11404 : 플로이드 (C++) with 플로이드

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 걸린 시간 : 12분 50초 (이에 해당하는 강의를 본 직후 풀어서 시간은 의미 없음) 플로이드 와샬 알고리즘의 가장 기본이 되는 문제이다. 플로이드 알고리즘은 임의의 점부터 임의의 점까지의 모든 최단거리를 알고 싶을 때 사용하는 O(N^3) 알고리즘이다. N이 몇백 수준일 때 사용하면 된다. 1000이 넘어가는 시점부터는 다익스트라 등 다른 알고리즘을 사용할 수 있는지 확인하자. 알고리즘 플로이..

[BOJ] 14501 : 퇴사 (C++) with DP

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 걸린 시간 : 21분 33초 알고리즘 다이나믹 프로그래밍이다. 예시로 나온 걸 차례대로 다 해보고, 거기서 일반항을 도출하면 끝이다. 모든 요소들을 돌면서 cost라는 dp 배열에 다음과 같이 실행한다. cost의 초기 상태는 모두 0이다. i번째 요소는 현재 그 값이거나, 아니면 이전에 현재 값보다 더 큰 값이 올 수 있었다면 그 값이다. 따라서 최댓값을 하나 변수에 저장해두고 탐색할 때마다 i번째 요소를 최신화한다. 만약 이 상담을 진행하면 N+1 째날에 퇴사할 수 없을 경우, 즉 인덱스를 벗어날 경우 고려하지 않는다. 이번 상담..

[BOJ] 20056: 마법사 상어와 파이어볼 (C++)

https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 걸린 시간 : 1시간 46분 45초 너무너무... 오래 걸려서 자신감을 떨어트린 문제.... 파이어볼을 저장하는 자료구조를 처음에 multimap으로 접근했다가 말도 안되는 생각이란 걸 알았다. 그 후, 3차원 배열과 벡터를 번갈아가며 쓰는 것으로 결정했고, 다들 그렇게 많이 한 것 같다. 두 번째는, 좌표가 0~(N-1)이 아니라 1~N 이기 때문에, 좌표..