알고리즘
-
BOJ) 리모컨알고리즘/백준 2020. 7. 11. 20:22
리모컨 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼�� www.acmicpc.net 풀이 리모콘이 고장나면 고치거나 바꿔야하는데, 그대로 써서 골치아프게한 문제다. 우선, 1~9 버튼과 채널 위아래 이동 + - 버튼 11개가 있는 리모컨이다. 그리고, 입력에서 버튼이 고장난 갯수와 버튼의 위치를 알려주는데, 여기서 런타임에러가 한번 떴다. 처음에는 if(n !=ZERO)를 해주지 않아서, n이 0인 경우 ( 고장난 버튼이 없는 경우 ) 에 입력을 받고 저장하려고 시도해서 에러가 났다. 그래서 if문을 통해 걸러줬다. ..
-
BOJ) 카드 구매하기알고리즘/백준 2020. 7. 8. 20:07
카드 구매하기 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 풀이 갑자기 dp문제를 풀고싶어서 이 문제를 풀었다. 이 문제는 한번에 정답을 맞추지 못했다. 총 세번을 제출했는데, 첫번째는, 에라토스테네스의 체를 이용해서 소수를 판별하는 것처럼, 특정 인덱스 i 에서 n까지 i 씩 증가하면서 초기에 저장된 가격과 i를 여러번 곱한 값 중 더 큰 값을 저장해주었다. for(int i=1; i
-
BOJ) 유기농 배추알고리즘/백준 2020. 7. 8. 19:53
유기농 배추 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 � www.acmicpc.net 풀이 이 문제도 grouping 문제여서, find-union을 써볼까 했지만, 크게 효율적일 것 같다는 느낌이 없었고, 이 문제에 적용하기에는 조금 복잡해질 것 같다고 생각했다. 그래서 그냥 BFS로 풀었다.. ㅎㅎㅎ 총 세번을 제출했고, BFS, BFS, DFS 순으로 제출했다. 첫번째는 평소에 풀던 것 처럼 grouping을 해주면서, gourping이 끝난 이후 저장된 groupIdx를 출력해줬다. 하지만, group을 지어서 값을 변경하거나 이용하지..
-
BOJ) 파이프 옮기기 1알고리즘/백준 2020. 7. 8. 19:37
파이프 옮기기 1 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 풀이 옮길 수 있는 모든 경우의 수를 찾는 문제기 때문에 브루트포스 문제다. 직접 다 돌리는데는 BFS나 DFS만큼 편한게 없다고(?) 생각해서 DFS로 풀었다. 문제를 풀면서 막혔던 부분은 첫째로, 문제 조건을 잘못 이해했다는 것이다. 파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수 이 문구에서 N,N을 보지 않고 N,y or x,N으로 이동한 파이프들을 구해줬었다... 두번째로는 실수라기 보다는 기둥의 시작점..
-
BOJ) 인구 이동알고리즘/백준 2020. 7. 7. 20:28
인구 이동 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모�� www.acmicpc.net 풀이 인접해있는 땅과 인구의 차이가 주어진 L과 R 사이에 존재하면 평균을 내면서, L과 R 사이에 존재하지 않을 때 까지 묶어주는 문제다. 처음 제출하자마자 맞았지만, 효율성이 조금 떨어진다고 생각해서 코드를 수정했다. 얼마 전 포스팅했던 성곽 문제랑 푸는 방법이 비슷하다. grouping을 해주고 각 group의 평균 값을 HashMap에 저장한다. 전체 grouping이 끝나면, 각 gourp마다 평균 값을 넣어주면서 조건에 부합..
-
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까지 움직일 수 있는 방향을 미리 저장했다. (..