Hello, Freakin world!

https://www.acmicpc.net/problem/10757 10757번: 큰 수 A+B 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 풀이 방법 1. 먼저 두 수 중 가장 긴 자릿수에 맞춰서 짧은 수 앞에 0을 붙입니다. 2. 맨 뒤에서부터 덧셈하는 하는데 합이 10 이상일 경우에 다음 자릿수 합에서 1을 더해줍니다. 아래 코드에서 주목할 만한 포인트 - 아래 구현에서 calculate(a,b)에서 항상 a b.length()) { String temp = a; a = b; b = temp; } System.out.println(calculate(a,b)); } /* 항상 b의 길이가 a보다 항상 크거나 같다 */ private stat..

www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 그래프 탐색을 이용한 구현 문제였습니다. 풀이 방식 1. 전체 나라에 대해서 DFS하면서 인구 이동이 가능한 나라끼리 그룹으로 묶어 줍니다. 2. 1에서의 정보를 바탕으로 같은 그룹의 나라들의 값을 갱신합니다. 2번이 끝나고 다시 1번을 수행합니다. 그룹으로 묶어 주는 과정에서 그 어떠 나라도 국경을 열지 않았다면 그룹의 개수를 N*N개가 됩니다. 각 그룹은 자기 자신을 포함하는 그룹이 되겠지요...

www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 이 문제도 꽤 까다로웠네요. 주의할 점은 경사로를 만들 수 있는지 체크할 때 올라가는 방향, 내려가는 방향 모두 체크해야 된다는 점입니다. 그리고 해당 블럭에 경사로가 이미 설치되어 있는지도 기록해줘야 합니다. import java.io.*; import java.util.ArrayList; import java.util.List; import java.util.StringTokenizer; public class Main { sta..

www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net dblab.duksung.ac.kr/ds/pdf/Chap05.pdf 위 pdf에 모든 알고리즘 설명이 들어가 있다. 꽤 유명한 문제였던 듯하다. 하지만 처음 문제를 접하면 풀기 쉽지 않을 듯한 문제다. import java.io.*; import java.util.ArrayList; import java.util.List; import java.util.Stack; public class Main { ..

www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 완전 탐색, DFS를 이용하면 풀 수 있는 문제다. 문제 자체의 알고리즘 난이도는 높지 않다. 하지만 한참 고민했던 문제다. 문제에서 cctv는 5가지 타입이 존재하고 타입별로 가능한 탐색 방향이 존재한다. 이를 단순하게 구현하려면 배열에 5가지 타입별로 각자 방향을 일일이 저장해두고 그대로 이용할 수도 있겠지만... 지저분해지는 코드가 눈에 선했기 때문에 이를 어떻게 구현할지 꽤 오랜 시간동안 생각..

www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 문제 자체는 DFS를 이용한 전형적인 길찾기 문제와 비슷했습니다. 주의할 점이라면 다음 좌표로 이동할 때, 주변에 장애물이 없는지 살펴야 합니다. 세로나 가로로 이동할 때는 상관이 없지만 대각으로 이동하는 경우에 이동하려는 좌표 위, 왼쪽이 모두 빈 공간이여야하기 때문입니다. package backjoon.dp.p17070; import java.io.*; import java.util..

www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 � www.acmicpc.net 해결하는데 굉장히 오래 걸렸습니다. 계속 분할 정복 방식으로 구간을 나눠 최적의 공유기 위치를 설치하려는 방식으로 접근했기 때문인데, 이 방식은 가능함의 여부를 떠나서(아마도 시간 제한에 걸릴 듯) 문제가 굉장히 복잡해지게 합니다. 관점을 살짝 바꿔야 합니다. 실제 수직선 위의 구간을 나눠가면서 공유기를 설치하는게 아니라, 최적화할 값들의 범위의 구간을 나..

www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망�� www.acmicpc.net 문제 풀이 얼리 어답터(EA)를 이용해 모든 아이디어를 퍼트리기 위해서는 다음의 규칙이 필요합니다. 1. 현재 노드가 EA인 경우 - 자식 노드가 EA인 경우 - 자식 노드가 EA가 아닌 경우 2. 현재 노드가 EA가 아닌 경우 - 모든 자식 노드가 EA여야 한다. 위의 규칙을 적용해 트리 구조에서 재귀를 이용해 해결할 수 있습니다. 재귀를 이용해 구현할 때, 리프노드에서의 종결 조건과 맞물려서 최소값..

www.acmicpc.net/problem/1014 1014번: 컨닝 최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목은 상당히 까다롭기로 정평이 나있기 때문에, 몇몇 학생들은 시험을 보는 도중에 다른 사람의 답지를 베끼려 한 www.acmicpc.net 한달 전인가? 너무 어려워서 패스했던 문제였습니다. 그런데 지금은 풀리네요. 풀이가 보였습니다. (오오... 성장해버렸구나) 저는 DP와 비트마스킹을 이용해 풀었습니다. DP 문제를 풀 때 역시 가장 중요한 건 부분 문제를 정의하는 겁니다. arrageStudent(i, previousRowStatus) : 0 ~ i번째 영역에서 이전 행의 상태가 previousRowStatus 일 때 배치할 수 있는 최대 학생 수 위처럼 정..

www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성�� www.acmicpc.net 문제 풀이 모든 지원자 중 자신보다 면접, 서류 분야 점수가 더 낮은 사람이 존재하는 경우 탈락하게 됩니다. 입력이 크기 때문에 N^2 로는 통과할 수 없습니다. 아래의 그림을 살펴보면 힌트를 얻을 수 있습니다. 빨간색으로 체크 친 지원자가 떨어지게 되는데, 해당 포인트는 점선으로 이뤄진 영역에 임의의 포인트를 포함합니다. 먼저 x축으로 입력을 정렬한 후 어떤 포인트를 포함하는 경우는 ..