java
-
BOJ) 에디터알고리즘/백준 2020. 7. 7. 20:09
에디터 1406번: 에디터 문제 한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다. 이 편집기에는 '커서'라는 것이 있는데, 커서는 www.acmicpc.net 풀이 총 3번을 제출했고, 마지막 한번만 맞았다. 처음에 푼 방법은, ArrayList에 char를 집어넣고 커서를 ArrayList의 size로 시작해서 LDBP를 구현했다. 풀면서 무조건 시간초과가 뜰거라고 생각했고, 9%에서 시간초과가 떴다. 그래서, 위의 방법과 커서는 똑같이 가져가고 ArrayList대신 StringBuffer로 문자열을 제거, 추가했다. 몰랐는데, StringBuffer에도 index에 값을 넣는 input 이라는 메소드가 존..
-
BOJ) 쉬운 계단 수알고리즘/백준 2020. 7. 6. 18:27
쉬운 계단 수 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 문제 제목은 쉬운 계단 수 인데, 어렵다.. ㅋㅋㅋㅋ DP 문제를 푼지 오래된 것 같아서 DP 문제를 선택해봤다. 우선 2차원 배열을 사이즈에 따라 생성하는 것 까지는 해놓고 생각을 했다. n자리 수 때, 0~9 숫자가 몇 번 쓰이는지 저장을 해야 풀 수 있는 문제인가 생각을 해보았다. 한 20분정도 생각했는데 이 방법은 아니었다. 다른 저장 방법은 없을까 고민했지만 떠오르지 않았다. 위의 생각에 빠져서 해당 숫자에서 -1 , +1 사이에 있어야 하는 것을 간과한 것이다.. 그래서 질문하기 게시판을 참고했다. 코드가 있는 질문들은 과감하게 넘기고 점화식을 물..
-
BOJ) 성곽알고리즘/백준 2020. 7. 6. 18:18
성곽 2234번: 성곽 문제 대략 위의 그림과 같이 생긴 성곽이 있다. 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로를 나타낸다. 이러한 형태의 성의 지도를 입력받아서 다음을 계산하는 프로� www.acmicpc.net 풀이 생각보다 코드가 길어진 문제다. 각 방에 대해 상하좌우에 벽이 있는지 없는지를 int형 숫자로 주어진다. 이 숫자는 각각 벽이 있다는 의미를 가진 2진수 숫자를 모두 더한 값이다. 벽의 방향 숫자 서 1 북 2 동 4 남 8 위의 벽 정보에 따라서 map의 숫자가 정해진다. 만약 서쪽과 북쪽에 벽이 있다면, 해당 방의 숫자는 3으로 주어지고, 동쪽과 남쪽은 12가 주어지는 식이었다. 그래서, 거추장스럽지만 0~15까지 움직일 수 있는 방향을 미리 저장했다. (..
-
BOJ) 숫자판 점프알고리즘/백준 2020. 7. 6. 18:01
숫자판 점프 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 풀이 5x5 크기의 숫자판에서 숫자 6개를 골라, 만들 수 있는 숫자의 갯수를 구하는 문제다. 또한, 000001 or 000000과 같은 숫자가 허용되고 이동할 때는 먼저 거쳐간 칸을 다시 거쳐가도 된다는 조건이 있다. 따라서, int형보다는 String으로 문제를 푸는 것이 적합하다고 생각했고, visit이 필요없는 문제였다. 그래서 처음에는 dfs안에서 좌표 for문을 돌면서 각 좌표 상하좌우에 있는 ..
-
BOJ) 연산자 끼워넣기알고리즘/백준 2020. 7. 5. 20:18
연산자 끼워넣기 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, �� www.acmicpc.net 풀이 어렵지 않은 문제지만, 푸는데 많은 시간이 들었다. return하는 부분에서 조건을 잘못 설정해줘서 찾는데 한참이 걸렸다.. ㅎㅎ ㅠㅠ 방법은 간단하다. 숫자 배열을 입력받아 저장하고, 연산자 배열(+,-,*,/ 순서)을 저장하면 이 문제는 끝이다. 숫자 사이사이 연산자를 집어 넣는 경우로, 숫자 배열을 가리키는 index를 통해 DFS를 풀어나가면 된다. 여기서 숫자 배열을 가리키..
-
BOJ) 벽 부수고 이동하기 4알고리즘/백준 2020. 7. 3. 16:37
벽 부수고 이동하기 4 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 � www.acmicpc.net 풀이 처음에는 모든 벽에 대해서 벽을 허물고 값을 구하고자 했다. 하지만, 주어진 n과 m의 최대값이 1000이나 되기 때문에 시간초과가 뜰 것 같았다. 그래서 생각한 것은 0에 대해서 grouping을 해주는 것이다. 빈칸이 이어진 곳들에 대해서 그룹 index를 남기고, 몇 개의 빈칸이 존재하는지 세주어서 저장하는 것이다. 이후에, Map을 돌면서 벽을 허물었을 경우, 상하좌우에 (인접한 곳에) 빈칸 그룹이 가지..
-
BOJ) 부등호알고리즘/백준 2020. 7. 3. 16:27
부등호 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제�� www.acmicpc.net 풀이 답은 바로 구했지만, 메모리를 너무 많이 잡고 속도가 느려서 몇 번을 다시 풀었다. 처음에는 모든 경우의 수를 다 구해서, 부등호의 갯수 n개 +1 만큼의 숫자를 뽑은 경우를 답 리스트에 넣어주었다. 이후, 정렬을 통해 양 끝에 있는 수를 출력해주었다. 정말 별로인 코드다... 그래서 조금 고쳐보기로 했다. String으로 다 저장해서 정렬을 하는것이 아니라, Long 타입 변수를 통해 MAX와 MIN 값을 저장해주었다. 로직 자체가 문제라서 메모리와 속도에 ..
-
BOJ) 스타트와 링크알고리즘/백준 2020. 7. 2. 16:22
스타트와 링크 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 풀이 주어진 짝수 인원(4~20)이 축구 경기를 하는데, n/2 : n/2 경기를 해야한다. 이 때, 실력차이가 가장 적게나는 경우를 찾는 문제다. 결국, 모든 경우의 수를 다 파악해야하는 Brute-force 문제였다. n이 20이나 되지만, DFS를 선택했다. 왜냐하면, N=20인 경우, 10 : 10 경기를 하기 때문에, 결론적으로는 2^20까지 가지 않기 때문이다. 중간에 한쪽 팀이 N의 절반이 넘어가는 경우를 가지치기만 해준다면 가능하다고 생각했다. dfs를 통..