자바
-
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점을 얻고, 승부에 사용된 카드는 버린다. (무승부의 ..
-
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과 연결..