알고리즘
-
BOJ) 선분 위의 점알고리즘/백준 2020. 8. 28. 02:01
선분 위의 점 11663번: 선분 위의 점 첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 www.acmicpc.net 풀이 2달 전에 이 문제를 풀다가 계속 시간초과랑 오답이 번갈아 뜨면서 포기했던 문제였다. 오늘도 풀면서 3번이나 틀렸지만 결국 풀어냈다..!! 우선, 문제의 조건에 따라 각 점들은 int형으로 주어지고, 선분의 left, right 범위는 long 타입으로 주어진다. 그리고 완전탐색을 하게되면 가지치기를 엄청나게 잘하지 않는 이상은 시간초과가 뜬다고 생각했다. 그래서 binary search를 이용했다. 점들의 배열을 오..
-
BOJ) 토너먼트알고리즘/백준 2020. 8. 27. 15:43
토너먼트 1057번: 토너먼트 김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 www.acmicpc.net 풀이 프로그래머스에서 풀었던 문제와 유사한(? 혹은 똑같은) 문제다. 그 당시 엄청 어렵게 풀었었기 때문에, 이번에는 쉽게 푼 분들의 풀이를 익히면서 풀었다. 먼저, 첫번째 방법은 left와 right의 숫자가 같아질 때 까지 /2를 해주는 것(경기를 진행하는 것) left와 right에 +1을 해주는 이유는 첫번째 경기는 1번부터 시작하기 때문이다. (1번 2번 경기 => (1+1)/2 === (2+1)/2 === 1) 두번째 방법은 XOR 연산 후, 2진수..
-
BOJ) 점프알고리즘/백준 2020. 8. 27. 15:30
점프 1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거�� www.acmicpc.net 풀이 0,0을 시작으로 n-1,n-1까지 도달할 수 있는 경우의 수를 구하는 문제다. 각 인덱스에 적혀있는 칸만큼 오른쪽 혹은 아래로 움직일 수 있으며, 범위 밖으로는 움직일 수 없고 칸에 적힌만큼 정확히 이동해야한다. 그래서 모든 인덱스를 순차적으로 돌면서 dp 값이 0이 아니고, 해당 인덱스가 움직일 수 있는 값이 0이 아닐 때, dp를 최신화해줬다. 경우의 수를 누적시키며 답을 찾아간다고 생각하면 된다. 처음에는 dfs로 풀려고 생각하다가, 경로의 개..
-
BOJ) 누울 자리를 찾아라알고리즘/백준 2020. 8. 26. 15:46
누울 자리를 찾아라 1652번: 누울 자리를 찾아라 첫째 줄에 방의 크기 N이 주어진다. N은 1이상 100이하의 정수이다. 그 다음 N줄에 걸쳐 N개의 문자가 들어오는데 '.'은 아무것도 없는 곳을 의미하고, 'X'는 짐이 있는 곳을 의미한다. www.acmicpc.net 풀이 세로와 가로를 직접 검증하는 메소드 두 개를 만들어서 쉽게 풀었다. 하지만, 기준점이 되는 좌표를 정하는 메소드로 만들었으면, 코드를 더 줄이고 중복을 줄일 수 있었을텐데 아쉽다. 확실히 문제 풀 때는 거기까지 생각하기는 힘든 것 같다. 아무튼, 내가 푼 방법은 가로와 세로 좌표를 각각 순차적으로 돌면서 다음 좌표가 빈칸인지 확인하며, 빈칸일 때까지 쭉 이어나가는? 방법이다. map에 직접 하는게 편하겠지만, 가로와 세로 각각 ..
-
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점을 얻고, 승부에 사용된 카드는 버린다. (무승부의 ..