알고리즘/백준
-
BOJ) 섬의 개수알고리즘/백준 2020. 8. 26. 15:38
섬의 개수 4963번: 섬의 개수 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사 www.acmicpc.net 풀이 섬의 개수를 찾는 문제로, 인접한 8구역이 땅이면 이동할 수 있다는 조건을 가지고 있다. 제약 조건이 기존 4곳에서 대각선들만 추가됐을뿐, 일반적인 grouping 문제다. grouping 문제는 이전 문제들에서 많이 다뤘기 때문에 큰 풀이는 남기지 않으려고 한다. 다만, 좌 우의 상/하 대각선을 예외처리 없이 검사하기 위해 map의 크기를 입력받은 n,m값 +2로 설정해줬다는 점이 특이하다 정도는 주의할만 하다. 그리고, 한 메소드 당 하나의 기능만 ..
-
BOJ) 수 찾기알고리즘/백준 2020. 8. 26. 15:31
수 찾기 1920번: 수 찾기 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안�� www.acmicpc.net 풀이 binary search인 것을 몰랐으면, 아마 시간 초과가 뜨고 나서야 시도했을 것 같다. 하지만, binary search라는 것을 알고 문제를 풀 때는 어렵지 않은 문제다. binary search에서 가장 중요한 것은 여러번 언급했듯, 기준점이다. 이 문제에서는 기준점이 명확하게 특정 숫자다. 특정 숫자를 담고있는 배열의 index를 찾는 문제라고 생각하면되겠다. 기준이 되는 배열은 Arrays...
-
BOJ) 가장 큰 정사각형알고리즘/백준 2020. 8. 26. 15:22
가장 큰 정사각형 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 풀이 전에 푼 적이 있는 문제여서, 비교적 쉽게 풀 수 있었다. 당시에는 어떻게 풀어야하는지 막막했었는데, 그때 봤던 풀이가 아직 머릿속에 남아있었다. 우선, 맵을 돌면서 1인 경우에 좌측 상단, 좌측, 상단 세 군데를 확인한다. 세 곳의 최소값 +1(자기자신)이 dp의 값이 된다. dp[y][[x] += min(dp[y-1[[x-1], dp[y-1][x], dp[y][x-1]) 이 된다는 소리다. 변이 2인 사각형은 2로, 3을 만족하는 사각형은 3으로 값이 정해지는 것이다. (손으로 위의 식을 풀어가다보면 쉽게..
-
BOJ) 작은 수 내기알고리즘/백준 2020. 8. 25. 18:04
작은 수 내기 16471번: 작은 수 내기 여자친구와 함께 보드게임카페에 간 주언이는, 여러 보드게임을 하며 데이트를 즐겼다. 3시간 커플세트로 결제를 하려던 순간, 주언이는 가격표 옆에 쓰여 있는 새로운 이벤트를 보았다. 바로 www.acmicpc.net 풀이 예전 문제들은 뭘 풀었는지 보다가, 이전에 작성했던 코드가 테스트 케이스 개편으로 시간 초과가 떠있는 것을 확인했다. 시간 초과를 그대로 두기에는 조금 찝찝해서 다시 풀어봤다. 각자 N장의 카드를 받는다. (N은 홀수다) 2. 각자 카드를 1장씩 골라서 카드에 적힌 수의 크기를 비교한다. (각 카드에 적힌 수는 0이상, 100,000이하의 정수다) 3. 더 작은 수가 적힌 카드를 낸 사람이 1점을 얻고, 승부에 사용된 카드는 버린다. (무승부의 ..
-
BOJ) 트리의 부모 찾기 (11725, JAVA)알고리즘/백준 2020. 8. 25. 17:58
트리의 부모 찾기 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 처음에는 1차원 배열로 문제를 풀려고 하다가, 연결 관계에서 부모 관계를 파악하기 힘들다는 문제를 발견했다. 그래서 BFS로 풀어야겠다는 마음을 먹었다. 우선 map을 저장해줘야 하는데, 배열을 사용할 수 없다. (최악의 경우 100,000 by 100,000가 된다) 그래서, ArrayList 배열에 map의 관계를 저장했다. (레코드 조회만 필요하기 때문에 ArrayList가 더 적절하다고 판단했다.) 맵이 저장된 다음에는 Queue를 통해 부모를 짝지어주었다. root인 1부터 시작하면서 1과 연결..
-
BOJ) 욕심쟁이 판다(1937, JAVA)알고리즘/백준 2020. 8. 25. 17:54
욕심쟁이 판다 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 풀이 메모이제이션을 활용한 dp문제다. 생각보다 너무 어려웠다. 알고리즘을 조금 쉬었다가 메모이제이션을 적용시켜서 dp를 활용하려니까 감이 잡히지 않았다. 그래서 다른 사람들의 풀이를 보면서 이해했다. 먼저, out of index를 방지해줄 inInArea 메소드와 움직일 수 있는 조건인지 확인하는 canMove 메소드를 만들었다. 이후, dfs 메소드인 findBamboo를 통해 문제의 조건에 따라 움직이며 최대 날을 구했다. 해당 위..
-
BOJ) 팰린드롬? (10942, JAVA)알고리즘/백준 2020. 8. 25. 17:49
팰린드롬? 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 풀이 효율적이지 않은 코드지만, 왠만한 팰린드롬 문제는 다 통과될 수 있도록 코드를 작성했다. 검사할 글자의 개수가 홀수일 때는 중앙점을 기준으로 좌 우로 -1, +1을 각각 해주면서 비교해주면 된다.짝수인 경우에는 중앙이 left가 되고, 중앙+1을 right로 비교해주면 된다.따라서, 위의 조건에 따라 짝수인 경우에는 left를 mid로 설정해주는 것을 예외처리 해줘서, left와 right가 같은지 확인할 수 있도록 했다. 코드 import java.io.BufferedReader; i..
-
BOJ) ACM 호텔(10250, JAVA)알고리즘/백준 2020. 8. 24. 17:00
풀이 1년 전에 못풀어던 문제였다. (문제를 풀기 시작하고 알았다.) 호텔의 층수, 한 층마다 방의 개수, 손님의 순번이 순차적으로 주어진다. 호텔에 머무는 손님들은 왜인지 모르겠지만, 가장 적게 걷는 것을 선호한다고 한다.그래서 각 층의 1호방 -> 각 층의 2호방 순으로 순차적으로 배정된다.(101, 201, 301 ... 102, 202호 이런 식으로 방이 배정됨) 풀고나니까 생각보다 간단했다. 우선 배정될 층의 높이는 n % h를 통해 구해줬다. n층에서 몇번째 위치하는지 구한것이다. 주의해야할 점은 n % h == 0인 경우에는, 가장 꼭대기 층에 배정해줘야 한다는 점이다. (배정 층의 순서를 생각해보면, 1층 -> 2층 -> 3층 ... h층인데, h % h => 0이기 때문) 다음으로는 해당..