Hello, Freakin world!

www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제 풀이 재귀를 이용해 팀을 나눕니다. 그리고 나눈 팀들을 비트로 변환하여 저장합니다. 그리고 비트를 이용해 완전탐색하면서 팀의 능력치를 구합니다. 구현 상의 팁 저는 하나의 팀을 구하고 비트 XOR 연산을 통해 반대편 팀을 구했습니다. (다른 분들의 코드를 보니 팀을 나누는 시점에 각각의 팀들을 저장하는 것도 좋아보이긴 하지만...) import java.io.*; import java.util.*; /* 백준 14889번 - ..

www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 풀이 DFS를 이용한 조합탐색 + 비트마스킹을 이용해 풀었습니다. 선택하는 치킨집의 범위가 최대 13으로 작기 때문에 조합 탐색으로 구한 각각의 상태정보를 비트에 저장한 뒤, 각각의 선택한 치킨집 상태정보를 이용해 최소 치킨거리의 합을 계산합니다. 그리고 그 값들 중 최소값을 찾아냅니다. ... /* 백준 15696번 - 치킨 배달 https://www.acmicpc.net/probl..

www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크� www.acmicpc.net 문제 풀이 입력이 작기 때문에 벽 생성이 가능한 모든 경우에 벽을 세운 뒤, 바이러스를 퍼트려 최대 공간을 찾아내면 됩니다. 구현 상의 팁이라면 이차원 배열의 상의 가능한 세가지 조합을 구할 때, 요소들의 번호를 1차원화시키는게 편합니다. 4x3 행렬이라면 0 1 2 3 4 5 6 7 8 9 10 11 위와 같이 번호를 매기면 단순하게 3중 for문을 이용해 모든 경우를 찾을 수 있습니다. 그리고 좌표 평면으로 변환도 쉽..

www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 이 문제는 어려운 문제는 아니지만 재밌는 요소가 있습니다. 가장 맨 위 A-B+C+D-E 의 예를 보시면 - 부호 다음으로 괄호를 열고 - 부호 이전까지 괄호를 닫는 식으로 마이너스 항들을 괄호로 확장해가면서 식의 결과값을 최소화 할 수 있습니다. 이를 바로 구현하기 전에 그 바로 아래를 살펴보시죵 ㅎㅎㅎ 만약 a번째 항 바로 앞에서 마이너스 부호가 최초로 나타났다고 가정합니다. (그전까지는 숫자항들을 모..

www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변� www.acmicpc.net 단순하게 모든 블럭을 배열로 구현해 체크하려고 했는데 다른 풀이들을 보니 그랬으면 큰일났겠구나 싶었다. 그 중 잘 정리된 글의 링크를 일단 첨부. velog.io/@skyepodium/%EB%B0%B1%EC%A4%80-14500-%ED%85%8C%ED%8A%B8%EB%A1%9C%EB%AF%B8%EB%85%B8 백준 14500 테트로미노 # 문제 ### DFS를 사용해서 합의 최댓값을 구하는 문제. (ㅜ 모양은..

www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이들을 보면서 왜 끝나는 시간에 대해 정렬하는가? 일찍 끝나는 회의부터 배정하는 방법이 최적해가 될 것임을 어떻게 증명할 것인가? 라는 생각들이 들었습니다. 답을 얻으면서 그리디 알고리즘에 대해 깊이 생각해 볼 수 있었습니다. 왜 먼저 끝나는 시간에 대해 정렬하는가? 위에 대한 답은 '탐욕법을 적용할 최적의 부분 구조를 만들기 위해서' 라는 결론을 얻었습니다. 이를 이해하기 위해서는 회의실을 배정한다는 행위에 대한 이해도 필요합니다. 회의실을 배정받기 위해서는 기본적으로 이전의 회의가 없거나 끝나 있어야 합니다. 만약 회의실을..

www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 제게는 이런 종류의 약간 복잡한 구현 문제가 코테의 숨은 복병입니다. 이런 종류의 구현 문제는... 문제를 잘 이해하고 뭐 그냥 많이 풀어보면서 패턴을 많이 익혀두는 수 밖에 없겠네요. ... /* 백준 14503번 - 로봇 청소기 https://www.acmicpc.net/problem/14503 */ public class Main { static int n,m; static int[][] room; st..

https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄�� www.acmicpc.net 구간 트리의 개념과 기분 구현을 할 수 있는지 묻는 문제입니다. 구간 트리에 대한 설명은 아래 글을 참고하세용 javachoi.tistory.com/292 구간 트리(Segment Tree) 구간 트리란? 구간 트리의 정체는 이진 트리입니다. 구간 트리 라는 이름은 그저 특정 용도로 사용되는 이진 트리의 한 형태를 나타낼 뿐입니다. 대..

구간 트리란? 구간 트리의 정체는 이진 트리입니다. 구간 트리 라는 이름은 그저 특정 용도로 사용되는 이진 트리의 한 형태를 나타낼 뿐입니다. 대게 구간 트리는 일차원 배열 상의 특정 구간에 대한 요청에 빠르게 대답하기 위해 사용합니다. 예를 들어, 1 2 3 4 5 라는 숫자 배열이 있다고 하겠습니다. 이 배열의 특정 구간의 합을 구한다고 할 때, 가장 간단한 방법은 그 특정 구간을 순회하면서 값을 더해나가는 겁니다. 이 경우 시간 복잡도는 O(n)이 됩니다. 만약 배열의 길이가 10억쯤 된다면 어떨까요? 컴퓨터가 1초에 1억번 정도의 루프를 돌린다고 하면 10초가 걸리겠네요. 그리고 또 이 합연산이 여러번 호출될 가능성이 있다면 어떨까요? 이 연산은 매번 합을 새로 구하기 때문에 문제가 됩니다. 구간..

www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 오랜만에 bfs 문제를 만나게 됐네요 ㅎㅎㅎ 처음에 낸 풀이는 메모리 초과가 떴습니다. 문제는 방문한 노드들을 체크하는 시점 때문에 발생한 문제였는데요. 예를 들면 dfs에서는 노드를 방문하고 나서야 현재 노드에 방문 체크를 하게 됩니다. 하지만 bfs는 방문 이전 시점, 즉 이전 노드에 의해 큐에 추가 될때 이미 방문 체크를 해버립니다. 왜 이렇게 하는가? 라는건 조금만 생각해..