본문 바로가기

알고리즘 (2020 : 08 : 10 ~ )/구현, 시뮬

 (65)
[백준 / BOJ] 17363 우유가 넘어지면? 문제 출처 : https://www.acmicpc.net/problem/17363 17363번: 우유가 넘어지면? 첫 줄에 그림의 세로 길이와 가로 길이를 의미하는 정수 N과 M(1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에 걸쳐 그림의 각 줄을 의미하는 M글자의 문자열이 하나씩 주어진다. 문자열은 공백을 포 www.acmicpc.net 입력된 N*M배열을 왼쪽으로 90도 회전한 결과를 출력하는 문제다. 풀이 문제에서 하란대로 구현하면 되는 간단한 문제다. 입력받은 문자를 왼쪽으로 90도 회전한 값을 HashMap에 저장해 놓고 HashMap에 저장된 값과 매치해서 출력하면된다. 주요 소스코드 private void init(){ dic.put('.','.'); dic.put('O','O')..
[백준 / BOJ] 18430 무기 공학 (Java) 문제 출처 : https://www.acmicpc.net/problem/18430 18430번: 무기 공학 첫째 줄에는 길동이가 가지고 있는 나무 재료의 세로, 가로 크기를 의미하는 두 자연수 N, M이 주어진다. (1 ≤ N, M ≤ 5) 다음 N개의 줄에 걸쳐서, 매 줄마다 나무 재료의 각 위치의 강도를 나타내 www.acmicpc.net N*M그리드가 주어진다. 길동이는 N*M그리드의 각 칸을 적절히 잘라서 부메랑을 만들어야한다. 길동이가 만들수있는 부메랑들의 크기의 총합을 가장 크게하는 프로그램을 만드는 문제다. 풀이 N과 M이 5가 최대이므로 완전탐색으로 풀수있는 문제였다. 백 트래킹으로 구현한 전형적인 백트래킹 문제다. 구현중 주의할점은 아래와 같다. 현재 위치를 y,x라 했을때, 다음에 탐색..
[백준 / BOJ] 1244 스위치 켜고 끄기 문제 출처 : https://www.acmicpc.net/problem/1244 1244번: 스위치 켜고 끄기 첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 켜져 있으면 1, 꺼져있으면 0이라고 표시하고 사이에 빈칸이 하나씩 www.acmicpc.net 1번부터 N번까지 총 N개의 스위치가 있다. 쿼리가 주어졌을때, 최종 스위치 상태를 출력하는 문제다. 문제에서 주어진 그대로 구현하면 되는문제다. 출력이 20이 넘어갈때, 줄 바꿈을 해줘야하는점만 주의하면 어렵지않게 풀리는 문제였다. 주요 소스코드 private void girl(int num){ int left = num; int right = num; while(left >..
[백준 / BOJ] 13335 트럭 (Java) 문제 출처 : https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net n개의 트럭이 길이 w인 다리를 지나야한다. 다리가 견딜수있는 최대 무게가 L이라할때, n개의 트럭이 모두 지나기 위해서 걸리는 시간을 구하는 문제다. 풀이 구현 문제였다. 로직은 아래와 같다. 1. 다리의 현재 상태를 저장하는 큐를 하나 만든다. 이 큐에는 트럭이 다리에 진입한 시간, 무게가 저장될것이다. 2. 다리가 새로운 트럭을 ..
[백준 / BOJ] 17298 오큰수 (Java) 문제 출처 : https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net N개의 수로 이루어진 수열이 있다. 이 수열의 i번째 원소를 Ni라 할때, Ni보다 오른쪽에 있으면서 Ni보다 큰 수를 찾아서 구하는 프로그램을 만드는 문제다. 풀이 스택으로 푸는 문제다. 수열에서 Ni보다 오른쪽에 있는 수중 더 큰수를 찾아야한다. 즉, 입력받는 Ni을 스택에 계속 집어넣으면서, Stack의 가장 위에있는 원소가 입력받은 Ni보다 더 큰 경우 스택의 가장 위에있는 원소가 Ni..
[백준 / BOJ] 19644 좀비 떼가 기관총 진지에도 오다니 문제 출처 : https://www.acmicpc.net/problem/19644 19644번: 좀비 떼가 기관총 진지에도 오다니 킬로와 헥토는 좀비 떼로부터 탄약고를 사수하는 데에 성공했다. 포상 휴가나 조기 전역을 기대했으나 좀비 사태로 인해 계엄령이 선포되면서 오히려 전역이 연기되고 기관총 진지에 배치되었 www.acmicpc.net 기관총 진지에 좀비떼가 다가오고 있다. 킬로와 헥토는 기관총과 지뢰를 이용해 좀비를 막아야한다. 기관총은, L의 사거리에 있는 좀비를 모두 K데미지로 공격한다. 지뢰는 1M사거리에 있는 좀비를 제압한다. 이때, 킬로와 헥토가 좀비 떼에게서 살아남을수있을지 구하는 문제다. 풀이 그리디, 투포인터 문제였다. 좀비의 수(진지의 거리)와 유효사거리가 3*10^6 이므로 시뮬레..
[백준 / BOJ] 2493 탑 (Java) 문제 출처 : https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 서로 다른 높이를 갖고있는 N개의 탑이 있다. 이 탑을 일렬로 세우고 탑의 꼭대기에서 왼쪽으로 레이저를 발사한다. 이때, 레이저는 처음 만나는 탑만 수신할수있다. 각 탑에서 레이저를 발사할때, 각 탑별로 레이저를 수신하는 타워를 출력하는 문제다. 풀이 스택으로 푼 문제다. N이 500,000이므로, 완탐으로 풀경우 시간초과가 발생한다. 문제의 조건중 "레이저는 처음 만나는 탑만 수..
[백준 / BOJ] 3015 오아시스 재결합 문제 출처 : https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net N명의 사람이 한 줄로 기다리고있다. i번째 사람과 i+a번째 사람이 서로 보기위해선, i ~ i+a사이에 i와 i+a보다 큰 사람이 없어야한다. 이때, 서로 볼수있는 사람의 쌍을 구하는 문제다. 풀이 푸는데 시간이 좀 많이 걸린문제다. 처음엔, 세그먼트 트리로 생각했으나, N*N/2 시간이 걸릴것이라 생각하여 포기했다.(문제 질문을 보니 세그먼트로도 풀리는듯..

티스토리툴바