백준

초기에 $n+1$개의 집합 ${0}, {1}, {2}, \\dots , {n}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.집합을 표현하는 프로그램을 작성하시오.문제 링크union-find 알고리즘을 먼저

동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를

민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하

사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 번호가 부여된 평면 상의 점 n 개가 주어지며, 이 중 어느 세 점도 일직

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.일부 학

숌 회사에서 이번에 새로운 전략 시뮬레이션 게임 세준 크래프트를 개발하기로 하였다. 핵심적인 부분은 개발이 끝난 상태고, 종족별 균형과 전체 게임 시간 등을 조절하는 부분만 남아 있었다.게임 플레이에 들어가는 시간은 상황에 따라 다를 수 있기 때문에, 모든 건물을 짓는

올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다.올해는 인터넷 예선 본부에서는 최종 순위를 발표하지 않기로 했다. 그 대신에 작년에 비해서 상대

문제 우리는 어떤 장난감을 여러 가지 부품으로 조립하여 만들려고 한다. 이 장난감을 만드는데는 기본 부품과 그 기본 부품으로 조립하여 만든 중간 부품이 사용된다. 기본 부품은 다른 부품을 사용하여 조립될 수 없는 부품이다. 중간 부품은 또 다른 중간 부품이나 기본 부

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.입력첫째 줄

문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과

트리나라는 N개의 도시로 이루어져 있고, 각각의 도시는 1번부터 N번까지 번호가 매겨져 있다. 트리나라의 도로 체계는 트리를 이룬다. 즉, 트리나라에는 N-1개의 양방향도로가 있다. 또, 모두 연결되어 있기 때문에, 임의의 두 도시 사이를 항상 오갈 수 있다.스타트링크

문제 간선에 가중치와 방향성이 없는 임의의 루트 있는 트리가 주어졌을 때, 아래의 쿼리에 답해보도록 하자. 정점 U를 루트로 하는 서브트리에 속한 정점의 수를 출력한다. 만약 이 문제를 해결하는 데에 어려움이 있다면, 하단의 힌트에 첨부한 문서를 참고하자. 입력 트

문제 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, 각 길은 방향성이 없어서 A번 마을에서 B번 마을로 갈 수

문제 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1

백준: 외판원 순회 2

백준: 애너그램

문제 풀이 코드 BFS DFS

4485번: 녹색 옷 입은 애가 젤다지?소지금을 최대한 적게 잃기 위해 지나가는 각 칸의 도둑루피의 합이 최소이어야 한다.이를 위해 다익스트라 알고리즘을 사용하여 해결하였다.각 칸의 십자 방향으로 인접한 칸을 연결된 노드로 보고,그 칸의 도둑루피 값을 가중치로 하여 최

12851번: 숨바꼭질2동생을 찾는 가장 빠른 시간 만을 출력한다면 간단한 bfs 문제이지만 동생을 찾는 방법의 수 또한 출력해야 하기에 복잡해졌다.각 칸마다 수빈이가 처음 방문 했을 때, 첫 방문은 아니지만 첫 방문과 같은 시간에 도착했을 때두 가지 경우로 나누어 해

13549번: 숨바꼭질3순간이동 할 때와 걷을 때의 시간이 다르기 때문에 우선순위 큐를 사용해야한다.다익스트라 알고리즘을 활용하여 문제를 해결할 수 있고일반적인 bfs 알고리즘에 우선순위 큐를 사용하여 해결 할 수 있다.bfs로 해결 가능한 이유는 이 문제가 특별하기

21608번: 상어 초등학교문제의 3가지 조건을 우선순위에 맞게 잘 구현해야 한다.이를 위해 나는 우선순위 큐를 활용하여 계산하였다.우선순위 큐의 우선순위 계산은 문제의 조건을 그대로 따라 만들었다.자리마다, 사람마다 4개씩 좋아하는 친구인지 확인하는 작업이 굉장히 비

10986번: 나머지 합입력으로 주어지는 수의 개수가 정말 많이 때문에 반복해서 문제를 풀기엔 시간이 모자르다.따라서 누적합을 활용하여 해결할 수 있다.문제에서 결과적으로 M으로 나누었을 때의 나머지 부분만을 원하기 때문에 입력으로 어떤 수가 들어와도 % m 연산으로

13911번: 집 구하기최단거리를 구해야하는 문제이다.다익스트라 알고리즘을 이용해서 해결할 수 있는데, 노드의 개수가 많아 모든 노드에 대해서 다익스트라 알고리즘을 적용하여 맥도날드와 스타벅스까지의 최단 거리를 구할 수 없다.각각의 집에서 맥도날드와 스타벅스까지의 거리

22856번: 트리 순회문제가 복잡해 보이지만 결과적으로 몇번 움직이는지만 안다면 간단한 문제다.루트에서 중위 순회의 마지막 노드를 가는 경로를 제외하고는 모든 노드를 탐색 후 부모 노드로 돌아가야 하므로 (트리의 간선의 수 \* 2) - (루트에서 중위 순회 마지막

16168번: 퍼레이드같은 간선을 두 번 이상 지나지 않으면서 모든 간선을 지나는 문제 즉, 오일러 경로에 대한 문제이다.중복 없이 모든 간선을 지나기 위해서는 그래프의 각 노드들의 차수를 확인해야 한다.이 문제는 무향 그래프에 관한 문제이기 때문에 노드의 차수가 짝수

5547번: 일루미네이션육각형 모양의 격자라고 쫄 필요 없다.십자모양과 다를것이 전혀 없이 노드에 이어진 간선이 4개가 아닌 6개일 뿐이다.세로의 인덱스가 홀수(1, 3, 5, ...) 일때, 짝수(0, 2, 4, ...)일때 서로 다른 위치로 간선이 있다는 것을 알고

1456번: 거의 소수에라토스테네스의 체를 사용하여 B보다 작은 소수들을 구하며 그의 제곱들을 하나씩 세주면 되는 문제이다.간단해 보이지만 10의 14제곱의 수를 처리해야 하는 만큼 정말 큰 수를 처리해야 해서 integer overflow가 발생하지 않도록 주의해야

문제 풀이 코드

1561번: 놀이 공원이전에 프로그래머스에서 이 문제와 유사한 입국심사문제를 풀어본 적이 있어서 이분 탐색 문제라는 것을 눈치챌 수 있었다.이분 탐색(매개변수 탐색) 문제이기 위해서는 탐색에 사용하는 수(매개변수), 그 수에 대응하는 비교할 값(함수 값)이 존재해야 하

문제 풀이 코드

문제 > 5875번: 오타 풀이 괄호의 종류에따라 -1, 1로하여 그 누적합을 구하면 현재 문자열의 괄호쌍이 올바른지 아닌지 판단할 수 있다. 이를 응용하여 누적합으로 문제를 해결할 수 있다. 잘못된 괄호의 개수가 최대 1개 이므로 코드

2671번: 잠수함 식별문자열이 올바른 패턴에 맞는지 확인하는 구현 문제이다.패턴이 반복되기 때문에 한 패턴이 올바른지 확인 후 다음 패턴으로 넘어가기 위해 재귀함수를 활용해서 해결했다.문자열의 인덱스를 파라미터로 하여 재귀함수를 호출했는데, 이때 인덱스가 문자열의 크

2110번: 공유기 설치프로그래머스의 징검다리 문제와 비슷한 문제이다. 이 문제도 이분 탐색을 이용하여 가장 인접한 공유기 사이의 거리가 최대가 되도록하는 문제다.이분 탐색으로 해결하기 위해 탐색할 x를 공유기 사이의 거리로 두고, f(x)를 인접한 공유기 사이의 모든

문제 1823번: 수확 풀이 수확한 벼의 개수에 따라 생기는 밭의 모양마다의 최대값을 이전 밭의 상태일때의 최대값을 이용하여 구하며 모든 벼를 수확했을 때의 최대값을 구하는 DP 문제이다. 똑같은 n개의 벼를 수학해도 왼쪽, 오른쪽 수확한 벼의 개수가 다른 경우

2812번: 크게 만들기입력으로 주어진 숫자의 순서를 바꿀 수 없다.k개의 숫자를 지운 수가 크기 위해서는 가능한 앞자리에 큰 수가 와야 한다.따라서 앞의 수보다 뒤에 큰 수가 있다면 지울 수 있는 한 많이 지워 큰수가 앞에 위치할 수 있도록 해야 한다.이를 위해 스택

1987번: 알파벳문제에서 출발 위치가 정해져있고, 보드의 크기가 최대 20 \* 20으로 작아 완전탐색 백트래킹으로 풀 수 있었다.같은 알파벳은 두 번 밟으면 안되기 때문에 이는 visited배열을 만들어 관리했다.알파벳 A 부터 Z까지 각각의 인덱스를 담는 26크기

20542번: 받아쓰기LCS와 비슷한 편집 거리 알고리즘이라는 방법으로 해결할 수 있다.제한사항으로 1 ≤ n × m ≤ 10,000,000 이 주어졌기 때문에 $O(n \\times m)$으로 해결할 수 있겠다고 생각했다.dp 테이블의 각 인덱스까지의 수정 개수를 이

20543번: 폭탄 던지는 태영이폭탄의 범위때문에 특정 위치의 폭탄 개수를 구하기가 쉽지 않다.하지만 태영이가 폭발 범위가 n을 넘어가게 던지지 않기 때문에 (0, 0), (0, n-1), (n-1, 0), (n-1, n-1)위치에 영향을 주는 폭탄 위치는 한 곳 밖에

18116번: 로봇 조립I a b 형태로 들어오는 a, b 부품은 같은 로봇이 부품이고, 서로 다른 로봇은 공동 부품을 가지지 않기 때문에 Union Find 알고리즘으로 해결할 수 있다.두 부품 a, b를 한 집합으로 처리하며 Q c의 형태로 들어오게 되면 c에 해당

문제 풀이 코드 참고 https://kibbomi.tistory.com/201

17070번: 파이프 옮기기1이 문제는 2가지 방법으로 풀이가 가능하다.우선 백트래킹으로 문제를 푸는 경우는 파이프를 옮기는 방법의 가지수 마다 그 결과가 (n,n)에 도달하는지를 확인하여 도달한다면 방법의 수 + 1로하여 문제를 해결할 수 있다.현재 파이프가 어떻게

1022번: 소용돌이 예쁘게 출력하기범위에 맞는 소용돌이를 구하고 숫자의 자릿수를 고려하여 공백을 삽입 후 출력하는 문제이다.출력할 숫자를 담을 (r2 - r1 +1 ) \* (c2 - c1 + 1) 크기의 2차원 배열을 만들고 소용돌이를 1부터 하나씩 숫자를 키워가며

1300번: k번째 수문제의 n이 최대 100000 이므로 n 제곱은 100억이 된다. 따라서 b 배열을 전부 구한 후 정렬하여 문제를 해결할 수 없고, 이분탐색으로 원하는 값을 찾아야 한다.하지만 이분탐색으로 어떻게 구현해야 할지 생각하기 너무 어려웠다. 우선 구해야

12015번: 가장 긴 증가하는 부분수열 2문제에서 요구하는 바는 가장 긴 증가하는 부분수열과 동일하지만 조건이 다르다. N이 최대 1,000,000까지 가능하여 $O(n^2)$의 풀이로는 해결할 수 없다.예를 들어 배열이 {10, 20, 30, 15, 20, 30,

2636번: 치즈공기와 접촉된 치즈를 찾는 작업과 공기와 접촉된 치즈가 녹아 없어지는 작업을 분리하여 실행해야 한다.찾는 작업과 녹아 없어지는 처리를 동시에 하게 될 경우 녹아 없어져 생긴 빈자리로 인해 올바른 결과가 나오지 않기 때문이다.공기와 접촉된 치즈를 찾는 작

2143번: 두 배열의 합모든 경우의 부 배열의 합을 A B 각각 구하고 두 부배열의 합이 T인 경우를 찾아주면 된다.합이 T인 경우를 찾기 위해 이분탐색을 이용해도 되고, 투 포인터를 이용해도 된다.A, B 부배열의 합을 구해둔 배열을 오름차순으로 정렬한다.A 부배열

9370번: 미확인 도착지s 부터 시작해서 목적지 후보로의 최단 거리를 구하는 문제이다. 이때 그 최단 거리 중 입력으로 주어지는 g, h 사이의 도로를 반드시 지나는 목적지 후보들을 출력하는 문제가 된다.출발지점이 하나 주어지고 그에 대한 최단 거리를 구해야 하므로

2211번: 네트워크 복수최소 스패닝 트리를 구하는 것인지, 다익스트라 최단 경로를 구하는 것인지 헷갈렷지만 슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 최소 시간이, 원래의 네트워크에서 통신하는데 걸리는 최소 시간보다 커져서는 안 된다. 라는 조건 때문에 다익스트라

10711번: 모래성처음엔 완전탐색으로 해결해보려 했다. 파도가 칠때마다 모든 모래성의 튼튼함 정도와 주변 모래성의 개수를 확인해서 해당 모래성이 무너질지 아닐지를 판단했는데, 당연하게도 시간초과가 발생했다.좀 더 빠른 방법을 위해 파도가 칠때마다 모든 모래성을 판단하

16118번: 달빛 여우늑대놈 때문에 많이 힘들었다.늑대는 여우보다 2배의 속도, 절반의 속도로 움직인다. 따라서 처음 입력으로 주어지는 그루터기 사이의 거리를 조절하여 늑대의 속도를 조절했다.거리를 2배로 하여 절반의 속도, 거리를 1/2배 하여 두배의 속도를 표현했

17471번: 게리맨더링N의 크기가 최대 10인데도 불구하고 추가시간 없는 0.5초에 쫄아서 완전탐색을 생각하지 못했다. 1 ~ n 까지의 구역을 두 개로 나누기 위해 비트마스킹을 이용해서 완전탐색을 했다.두 선거구를 나누었을 때 각 선거구의 구역은 서로 이어져 있어야

10775번: 공항큰 수의 비행기는 작거나 같은 수의 게이트에 도킹이 가능하다.큰수의 비행기가 작은 수의 게이트에 먼저 도킹을 하게 되면 나중에 작은 수의 비행기가 그 게이트에 도킹을 못하게 되므로 비행기는 가능한 가장 큰 수의 게이트에 도킹해야 한다.N 비행기가 N

17143번: 낚시왕낚시왕이 오른쪽으로 한칸씩 이동하고 낚시하고, 상어들이 움직이고 를 반복하며 잡힌 상어의 크기의 총합을 출력하면 된다.상어들이 이동할때 격자의 크기보다 speed가 큰 상어들이 있다. 이때 격자의 2배보다 큰 speed인경우 같은 자리, 같은 방향으

19235번: 모노미노도미노별다른 알고리즘 없이 그냥 구현 문제였다.파란색보드와 초록색보드가 서로대칭이다 보니 6X4 모양의 보드 하나로 퉁치고 계산했다.파란색보드에 입력할 때 빨간보드의x,y 좌표를 서로 바꾸어 주면 된다.두 보드 모두 6X4로 사용하기 때문에 두개를

11066번: 파일 합치기이 문제는 파일끼리의 순서가 뒤섞이면 안된다. 항상 파일의 순서를 지켜 연속적인 두 파일만을 합칠 수 있다.파일이 i번 ~ j-1번 까지의 파일을 모두 합치는데 비용을 dp\[i]\[j]이라 한다면점화식 dp\[i]\[j] = min(dp\[i

1918번: 후위 표기식문제에도 설명되어 있지만 후위 표기식은 피 연산자가 연산자 앞에 위치하며 연산자끼리의 우선순위를 비교하여 그 순서가 결정되고 괄호가 필요 없게 됩니다. 우선 순위가 높은 연산자가 낮은 연산자보다 먼저 배치됩니다. 중요한건 연산자들 사이의 우선순위

13398번: 연속합2연속합 문제에서 한가지 조건이 추가된 문제입니다. 연속합 문제 풀이를 응용하여 이번 문제를 해결할 수 있습니다.입력으로 주어진 배열이 arr이라 할때,연속합 문제는 currentMax\[i] = max(currentMax\[i-1] + arr\[i

1912번: 연속합문제를 풀기위해 모든 경우의 수를 비교하는 방법도 있지만, n <= 100,000 이라는 조건 때문에 불가능합니다. 모든 경우의 수를 따지지 않고 해결하기위해 다이나믹프로그래밍을 이용하여 빠르게 해결할 수 있습니다.우리가 구하고자 하는 최대 연속

21609번: 상어 중학교bfs를 사용하는 구현문제 입니다. 알고리즘은 복잡하지 않아 구현만 잘하면 풀 수 있었네요.문제의 오토플레이가 요구하는 4가지 기능을 구현해야 합니다.가장 큰 블록그룹 찾기찾은 블록그룹 삭제하기중력 작용하기격자 반시계로 90도 회전하기1\. 가

8980번: 택배사실 이 문제가 왜 그리디 알고리즘으로 해결이 가능한지 증명하지 못했습니다. 하지만 그럼에도 불구하고 할당받은 문제이기 때문에 풀이를 작성합니다.이 문제를 \[백준]1931번: 회의실 배정문제에 대입해 봅시다. 그렇다면 이 문제는 회의실이 C 만큼 있다

문제 14442번: 벽 부수고 이동하기2 풀이 목적지 까지의 최단 거리를 알기 위해 bfs 탐색을 활용합니다. 그런데 벽을 k개 까지 부술 수 있습니다. 따라서 bfs 탐색 queue에 현재 위치뿐만 아니라 지금까지 몇개의 벽을 부셨는지에 대한 값도 저장해야 합니다

19236번: 청소년 상어상어가 움직일 수 있는 위치가 여러곳이고, 그에따라 상어가 먹을 수 있는 물고기의 번호합이 달라집니다. 모든 경우의 수를 비교하기 위해 백트래킹을 이용하여 탐색합니다.

문제 1799번: 비숍 풀이 문제를 보자마자 처음 든 생각은 "그리디로 풀 수 있지 않을까?" 였습니다. 색칠되지 않은 위치에 비숍을 놓았을 때 놓을 수 없어지는 비숍의 수를 우선순위로 하여 적은 것부터 놓게 된다면 문제를 해결할 수 있다고 생각했습니다. 하지만

2339번 스도쿠답이 여러개인 경우도 고려해야 하기 때문에 백트래킹으로 모든 경우의 수를 살펴봐야합니다.우선 스도쿠의 규칙에 의해 중복된 숫자가 존재하지 않도록 각 행, 열, 3x3 사각형에 해당하는 중복 확인을 위한 배열을 만듭니다. 숫자가 스도쿠판에 하나 채워지면

문제 2553번: 마지막 팩토리얼 수 풀이 팩토리얼이 커진다면 2와 5가 계속해서 많이 곱해지기 때문에 가장 낮은 자리 수는 0으로 고정됩니다. 하지만 구해야 하는 수는 0이 아닌 가장 낮은 자리 수 이기 때문에 0을 제거하기 위해 10이 되는 2와 5가 곱해지는

13164번: 행복 유치원 먼저 티셔츠 만드는 비용의 합을 구하는 방법을 알아봅시다. 입력으로 주어지는 원생들의 키는 정렬되어 있습니다. 총 n 명에 대해서 각 키를 $$ a1, \\; a_1, \\;a_2, \\; \\cdots ,\\; a{n} $$이라 한다면모든