angxxu.log

25543번: X 만들기 (1,0), (0,1), (-1,0), (0,-1)에 위치한 압정들을 제거하면 남은 압정들이 X자 모양을 이룬다. www.acmicpc.net 한참 헤매다가 LIS를 공부한 후 풀어냈다. LIS 공부한 후에도 시간초과 나서 어떻게 해결할지 좀 헤맴............어렵다......................나는 몽총이................. 1. 점을 ArrayList에 저장하고, x좌표를 기준으로 정렬한다. 2. 정렬된 list를 가지고 dp를 사용해서 LIS를 구한다. 전체 점을 각각 원점으로 했을 때, 1~4사분면의 LIS 길이를 구한다. 즉, LIS를 구하는 dp 배열 area는 다음과 같이 생겼다. int[][] area = new int[5][N]; (5인..

BOJ의 "Q25543 - X만들기"를 풀이하다가 LIS에 대해 알게 되었고 공부한 내용을 기록하고자 한다.!! 이 키워드 몰랐으면 못 풀었을 것 같ㄷ아................ https://angxxu.tistory.com/46 [BOJ][Java] Q25543 - X 만들기 25543번: X 만들기 (1,0), (0,1), (-1,0), (0,-1)에 위치한 압정들을 제거하면 남은 압정들이 X자 모양을 이룬다. www.acmicpc.net 한참 헤매다가 LIS를 공부한 후 풀어냈다. LIS 공부한 후에도 시간초과 나서 어 angxxu.tistory.com LIS(Longest Increase Subsequence)란? 최장 증가 부분수열 알고리즘이다. 말 그대로 가장 긴 증가하는 부분 수열을 구..

Big-O 기준으로 정리한다. 즉, 최악의 경우를 고려한다! 1. 시간복잡도 효율 순서 Better O(1) < O(log n) < O(n)

https://www.acmicpc.net/problem/3151 3151번: 합이 0 Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. www.acmicpc.net 투포인터 문제다. 일단 주어진 배열을 오름차순으로 정렬한 후 시작했다. 처음엔 한 원소를 잡고, 그 원소를 0으로 만드는 target을 정한 뒤 투포인터로 두 원소의 조합을 찾아내려 했다. 하지만 중복된 원소가 있어서 빼먹는 경우의 수가 생겼고, (풀 순 있겠지만) 예외처리가 복잡해졌다. 따라서, 반대로 두 원소를 정하고 합을 0으로 만드는 원소 하나를 투포인터로 탐색했다. 마찬가지로 중복된 원소가 있..

17951번: 흩날리는 시험지 속에서 내 평점이 느껴진거야 시험지를 12, 7, 19, 20과 17, 14, 9, 10 으로 나누면 맞은 문제 개수의 합의 최소는 50이다. www.acmicpc.net 문제 풀이 이런 류의 이분탐색 문제를 접하면, 주어진 배열에서 left right로 범위를 나누어 탐색하려 했는데 아무리 생각해도 알고리즘을 생각해내기 힘들 경우, 높은 확률로 이 문제처럼 배열이 아닌 "찾고자 하는 값의 범위"를 이분탐색해야한다. 이 점을 염두에 두고 풀이하면 실마리를 찾기가 보다 수월하다. (나만 맨날 이거 헷갈리는 걸 수도 있음) 그룹 중 최소값이 최대가 되는 최적해를 이분탐색으로 찾는다. 범위의 left는 원소 중 최소값(어쨌든 원소 하나는 무조건 포함하므로), right는 모든 원..

1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 문제 풀이 포인터 두 개로 탐색하는 문제이다. 숫자의 개수가 2000개이므로, 완전탐색을 하면 3중for문으로 구현해야해서 N^3으로 시간초과이다. (찾을 숫자 고르고, 그 숫자를 위해 더할 숫자 두 개 고르니까 3중for문) 주어진 배열을 일단 오름차순으로 정렬한 뒤, left를 왼쪽 끝(0), right을 오른쪽 끝(N-1)에 위치한다. left는 오른쪽으로만 이동하고, right은 왼쪽으로만 이동할 것이다. 따라서 당연히 left는 이동할수록 sum이 커지고, right는 이동할수록 ..

14658번: 하늘에서 별똥별이 빗발친다 첫째 줄에 네 정수 N, M, L, K가 주어진다. (1 ≤ N, M ≤ 500,000, 1 ≤ L ≤ 100,000, 1 ≤ K ≤ 100) N은 별똥별이 떨어지는 구역의 가로길이, M은 세로길이, L은 트램펄린의 한 변의 길이, K는 별똥별의 수를 www.acmicpc.net 문제 풀이 구역의 크기가 가로,세로 각 50만이고, 트램펄린 또한 한 변의 길이가 10만이나 된다. 따라서 2차원배열에 별의 위치를 저장해놓고 탐색하는 방식은 사용할 수 없다. 별의 개수를 보면 최대 100개밖에 되지 않으므로, 별을 기준으로 반복문을 돌리며 찾아주면 된다. 또, 문제에 애매하게 써있어서 헷갈렸는데 (별똥별이 떨어지는 위치는 겹치지 않으며 별똥별은 트램펄린의 모서리에 부딪..

그냥 dfs로 '불이 켜진 인접한 방'을 돌기만 하면, 이전에 불이 꺼진 상태라서 지나쳤으나, 그 후 불이 켜졌을 경우가 누락된다. 따라서 나는 두 가지 경우에 방문처리를 해주었다. - 인접한 방 중 불이 켜져있는 곳 방문 - 스위치로 불을 켰는데 켜진 방 주변에 visited된 방이 있을 경우, 불 켠 방 방문 private static void dfs(Pos now){ ArrayList switches = list[now.x][now.y]; for(Pos p: switches){ //불이 꺼져있는 방이면 스위치를 켠다. if(!light[p.x][p.y]){ totalCnt++; light[p.x][p.y] = true; //불 켠 곳 방문할 수 있는지 검사(인접한 곳에 visited가 true인 곳..

2174번: 로봇 시뮬레이션 첫째 줄에 두 정수 A, B가 주어진다. 다음 줄에는 두 정수 N, M이 주어진다. 다음 N개의 줄에는 각 로봇의 초기 위치(x, y좌표 순) 및 방향이 주어진다. 다음 M개의 줄에는 각 명령이 명령을 내리는 순 www.acmicpc.net 크게 어려운 점은 없는 문제인데, board의 방향이 좌표평면과 똑같다는 점에서 유의해야 했다. board[B+1][A+1] 크기로 선언해야하고, 나는 로봇의 x, y좌표를 입력받을 때 y좌표를 뒤집어서 저장해 주었다. ( 1,2,3,4) -> 각각 (4,3,2,1)로 저장 그 이후로는 내 행렬 모양대로 풀었다. 1. 로봇정보 저장 로봇행렬을 만들어서 각 인덱스에 로봇정보(로봇의 방향, x좌표, y좌표)를 저장하고, int[][] boar..

순열의 개념으로 브루트포스 / 백트래킹 하는 문제였다. 재귀로 풀이했고, index가 N개가 되면 경우의 수(totalCnt)를 증가시켰다. 체크하다가 중량이 500 이하가 되는 순간이 있으면 그 경우는 제외하였다. 재귀함수를 호출해준 후 selected여부와 weight를 다시 원상복구시켜야한다는 것을 유의해야 한다. (그 이후에 체크할 다른 경우의 수에서는 선택하지 않았기 때문에) package 완전탐색.permutation; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Q18429_근손실 { /*..