백준 골드

문제: A와 B 2분류: 문자열, 브루트포스 알고리즘, 재귀난이도: 골드5S를 T로 바꿀 수 있는지가 아니라 T를 S로 바꿀 수 있는지를 재귀함수로 확인한다.현재 문자열이 S와 같다면 1을 반환현재 문자열의 마지막 문자가 “A”라면 마지막 문자를 제외한 문자열에 대해

문제: 개똥벌레분류: 이분 탐색, 누적 합난이도: 골드5석순과 종유석을 서로 다른 배열에 입력 받고 오름차순 정렬 한다.첫 번째 구간부터 H번째 구간까지 차례대로 이분탐색 한다.이분탐색 시 아래의 과정을 반복한다.(h = 구간, answer = 장애물의 최솟값, cou

문제: 용액 합성하기분류: 두 포인터난이도: 골드5배열의 왼쪽 끝과 오른쪽 끝에 포인터를 두어 두 포인터가 가리키는 특성값의 합이 음수이면 왼쪽 포인터를 오른쪽으로, 양수이면 오른쪽 포인터를 왼쪽으로 옮기며 0에 가장 가까운 특성값의 합을 구한다.

문제: Contact분류: 문자열, 정규 표현식난이도: 골드5new RegExp()를 통해 (100+1+|01)+를 정규식으로 생성하고 각 문자열을 test()에 대입하여 일치하는지 확인한다.

문제: 거짓말분류: 자료 구조, 그래프 이론, 그래프 탐색, 분리 집합난이도: 골드4Union-Find 알고리즘을 사용한다.하나라도 같은 파티에 참여하는 인원들을 한 그룹으로 묶는다.각 파티마다 파티에 참여하는 첫 번째 사람과 나머지 사람들을 Union 한다.각 파티에

문제: LCS분류: DP, 문자열난이도: 골드5dpi : 문자열1의 i번째 인덱스까지의 문자열과 문자열2의 j번째 인덱스까지의 문자열의 LCS의 길이두 문자열에 대해 한 글자씩 비교하며 dp 배열에 현재까지 비교한 문자열에 대한 LCS의 길이를 저장한다.문자열 str1

문제: 주간 미팅분류: 그래프 이론, 다익스트라, 최단 경로난이도: 골드4다익스트라 알고리즘을 통해 풀 수 있었다.KIST부터 각 장소까지의 최단 거리 배열과 씨알푸드부터 각 장소까지의 최단 거리 배열을 구한다.한 사람의 거리 d는 (집-KIST의 최단 거리) + (집

문제: 동전 2분류: DP난이도: 골드5DP를 활용해 풀 수 있다.dp 배열에서 각 동전의 가치에 해당하는 부분을 1, 나머지를 Infinity로 초기화한다.그리고 모든 동전에 대해 해당 동전을 사용했을 때 동전의 가치 v에서부터 k까지, 각 값을 만들기 위해 필요한

문제: 강의실 배정분류: 자료 구조, 그리디 알고리즘, 정렬, 우선순위 큐난이도: 골드5최소힙을 가지는 우선순위 큐를 사용하여 풀 수 있다.강의를 시작 시간 순으로 정렬한다.첫 번째 강의가 끝나는 시간을 우선순위 큐에 넣는다.두 번째 강의부터 마지막 강의까지 아래를 반

문제: LCS 2분류: DP난이도: 골드4LCS의 길이는 DP를 사용하여 구했고 LCS는 재귀 함수를 사용하여 구했다.문자열 A의 인덱스를 i, 문자열 B의 인덱스를 j라고 했을 때 dp\[i]\[j]는 우선 왼쪽과 위쪽 중 더 큰 값으로 초기화 한다. 그리고 A\[i

문제: 연구소분류: 구현, 그래프 이론, 브루투포스 알고리즘, 그래프 탐색, 너비 우선 탐색난이도: 골드4빈 칸의 위치와 초기 바이러스의 위치를 미리 배열로 뽑아두고 각각 조합을 구할 때, BFS로 바이러스를 확산시킬 때 사용한다.전체적인 풀이 과정은 아래와 같다.빈

문제: 단어 수학분류: 그리디 알고리즘난이도: 골드4각 알파벳별로 가중치를 구한다.모든 단어에 대해 일의 자리부터 높은 자리 순으로 각 알파벳에 1, 100, 1000, …과 같이 자릿 수를 누적하여 더한다.예를 들어 AECE라는 단어가 있을 때 아래와 같이 더한다.일

문제: 수 묶기분류: 그리디 알고리즘, 정렬, 많은 조건 분기난이도: 골드4수열의 각 수를 묶을 때 그 합이 최대가 되게 하기 위해서는양수는 큰 수부터 차례대로 두 개씩 묶는다.단, 1의 경우는 묶지 않고 그대로 더한다. ex) 3, 5, 7, 9가 있을 때 35+79

문제: 사분면분류: 수학, 분할 정복난이도: 골드4사분면 조각 번호의 자릿수 d가 주어질 때 좌표평면을 2^d 크기의 행렬로 가정하고 문제를 풀이한다.2^d 행렬 내에서 사분면 조각의 좌표를 구한다.구한 좌표에서 주어진 이동 횟수만큼 이동했을 때의 좌표를 구한다.이동한

문제: 빗물분류: 구현, 시뮬레이션난이도: 골드5다른 사람 풀이를 참고했다.현재 블록을 기준으로 왼쪽에 있는 블록 중 가장 높은 블록과 오른쪽에 있는 블록 중 가장 높은 블록을 찾는다.그리고 둘 중 더 낮은 블록의 높이에서 현재 블록의 높이를 빼면 현재 블록 위로 고이

문제: Moo 게임분류: 분할 정복, 재귀난이도: 골드5Moo 수열은 세 가지 부분으로 나눌 수 있다.S(k-1)o가 k+2개인 수열S(k-1)N번째 글자는 길이가 N 이상인 Moo 수열 중 가장 짧은 Moo 수열의 세 가지 부분 중 하나에 속해있다.직접 Moo 수열을

문제: 두 동전분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색난이도: 골드4DFS로 풀이했다.이동 횟수를 계속해서 증가시키며 상하좌우 4방향으로 동전을 이동시킨다. 더이상 탐색할 필요가 없는 아래의 두 경우에는 곧바로 함수를 종료하여 불필요한 실행을 막는다.이동 횟

문제: AC분류: 구현, 자료 구조, 문자열, 파싱, 덱난이도: 골드5함수 D를 수행할 때 현재까지 함수 R을 몇 번 수행했는지에 따라 앞의 수를 지울지 뒤의 수를 지울지 결정한다.현재까지 함수 R을 짝수 번 수행했다면 뒤집고 뒤집어서 원래 순서대로 돌아오기 때문에 배

문제: 공통 부분 문자열분류: DP, 문자열난이도: 골드5DP를 통해 풀이했다.첫 번째 문자열의 문자를 참조하는 인덱스 a,두 번째 문자열의 문자를 참조하는 인덱스 b가 있다고 하자.두 문자열을 앞에서부터 비교하며 현재 각 문자열의 문자가 같은 경우에만 dp\[a]\[

문제: 공항분류: 자료 구조, 그리디 알고리즘, 분리 집합난이도: 골드2g가 주어졌을 때, 최대한 많은 비행기를 도킹하기 위해 g번부터 1번까지 도킹을 시도한다.예를 들어 g가 4라면 1번~4번 게이트 중 하나에 도킹할 수 있다.일단 4번에 도킹이 가능한지를 살피고 안

문제: 운동분류: 그래프 이론, 최단 경로, 플로이드-워셜난이도: 골드4문제에서 주어지는 마을의 개수가 최대 400개로 삼중 반복문을 돌려도 충분하기 때문에 플로이드 와샬 알고리즘을 사용했다.모든 마을 사이의 최단 거리를 구하면서 출발지와 도착지가 자기 자신인 경우에만

문제: 서강그라운드분류: 그래프 이론, 다익스트라, 최단 경로, 플로이드-워셜난이도: 골드4플로이드 와샬 알고리즘으로 최단 거리 테이블을 만들고 이를 행별로 탐색하며 어떤 지역까지의 거리가 m보다 작거나 같은 경우에만 아이템 개수를 세아린다.세아린 아이템 개수가 정답

문제: 공유기 설치분류: 이분 탐색, 매개 변수 탐색난이도: 골드4이분탐색을 통해 두 공유기 사이의 최대 거리를 구한다.이분탐색을 진행하기 위해 먼저 집 좌표를 오름차순으로 정렬한다.이후 left와 right에 각각 집 사이의 최소 거리, 최대 거리를 저장하고 left

문제: 집합의 표현분류: 자료 구조, 분리 집합난이도: 골드5Union-Find 알고리즘으로 풀 수 있는 기본적인 문제였다.합집합 연산 시 union 하고 같은 집합인지 확인하는 연산 시 find를 통해 루트의 동일 여부를 확인한다.코드를 제출했는데 런타임 에러(EAC

문제: 알고스팟분류: 그래프 이론, 그래프 탐색, 데이크스트라, 최단 경로, 0-1 너비 우선 탐색난이도: 골드4다른 사람 풀이를 참고했다.BFS를 사용하되 벽을 최소로 부숴야 하므로 최대한 벽이 없는 곳부터 방문한다.다음 위치가 빈 방이라면 unshift()를 통해

문제: 타임머신분류: 그래프 이론, 최단 경로, 벨만-포드난이도: 골드4타임머신으로 시간을 되돌아가는 경우도 있다는 것은 음의 간선이 존재한다는 말이다.따라서 벨만포드 알고리즘을 통해 최소 시간을 구하고 음의 사이클 또한 확인한다.음의 사이클이 존재한다면 -1을, 그렇

문제: 웜홀분류: 그래프 이론, 최단 경로, 벨만-포드난이도: 골드3플로이드 와샬 알고리즘을 통해 풀이했다.도로는 양방향 이동이 가능하고 웜홀은 단방향 이동만 가능하다는 점에 주의하여 최단 시간을 저장하는 dist 배열을 초기화한다.이후 플로이드 와샬 알고리즘으로 di

문제: 회문분류: 문자열, 두 포인터난이도: 골드5왼쪽 끝, 오른쪽 끝에 각각 포인터를 두고 동시에 중간으로 한 칸씩 이동하며 서로 다른 문자가 있는지 확인한다.서로 다른 문자가 있다면이미 회문은 아니고, 유사회문이거나 아니거나 둘 중 하나다.왼쪽이나 오른쪽 포인터 중

문제: PPAP분류: 자료 구조, 문자열, 스택난이도: 골드4스택을 활용하여 풀이했다.주어진 문자열의 문자를 순차적으로 탐색하며 아래를 수행한다.현재 문자부터 길이 2만큼을 잘라낸 문자열이 "AP"이면스택의 상위 두 원소가 모두 “P”인 경우, 이들과 잘라낸 문자열 “

문제: 키 순서분류: 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 최단 경로, 플로이드-워셜난이도: 골드4자신의 키가 몇 번째인지 알기 위해서는 자신보다 키가 더 작은 학생의 수와 더 큰 학생의 수를 정확히 알아야 한다.이를 위해 모든 학생에 대해 해당 학생을 시작점

문제: 회장뽑기분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 최단 경로, 플로이드-워셜난이도: 골드5플로이드 와샬 알고리즘을 사용하여 풀이했다.서로 친구인 a, b에 대해 최단 거리 테이블에서 dist\[a]\[b]와 dist\[b]\[a]를 1로 초기화한다.이

문제: 좋은 친구분류: 자료 구조, 슬라이딩 윈도우, 큐난이도: 골드4큐를 이용하여 풀었다.queuelen : 이름의 길이가 len인 학생의 등수가 들어있는 큐위와 같다고 할 때, 이름이 최대 20글자라고 했으므로 21개의 빈 배열을 원소로 갖는 배열을 선언한다.입력이

문제: 세 수의 합분류: 자료 구조, 이분 탐색, 해시를 사용한 집합과 맵, 중간에서 만나기난이도: 골드4다른 사람 풀이를 참고했다.세 개의 수를 고른다고 했으므로 우선 두 수의 합들을 구한다.이후 (문제에서 세 수의 합이 가장 큰 경우를 구하라고 했으므로)집합의 가장

문제: 센서분류: 그리디 알고리즘, 정렬난이도: 골드5우선 밀접해 있는 센서들 간의 거리를 구해야 한다.이를 위해 입력 받은 센서들의 위치를 오름차순 정렬한다.정렬 후 밀접한 두 센서 간의 거리를 구한다.그 후 가까운 센서들을 묶어서 각 묶음 당 하나의 집중국을 세워야

문제: 과제분류: 자료 구조, 그리디 알고리즘, 정렬, 우선순위 큐난이도: 골드3과제 마감일 중 가장 긴 마감일을 maxDay, 과제 정보를 담는 배열 homeworks가 있다고 하자.homeworks를 과제 점수를 기준으로 내림차순 정렬한다.maxDay가 0이 될 때