Hello, Freakin world!

www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 쉬울 줄 알고 덤볐다가 꽤 시간을 잡아 먹은 문제입니다. 문제를 살펴보면 해야될 작업이 딱 두 가지가 떠오를 겁니다. 1. 쪼개지는 빙산의 개수 구하기 2. 배열을 순회하면서 얼음 녹이기 1번은 전형적인 그래프 컴포넌트 개수 구하기 문제입니다. 2번은 하나의 좌표가 주어질 때, 상하좌우에 0이 있는 개수만큼 값을 빼주면 되고요. 저는 1,2번 작업을 분리시켜서 구현했었는데, 시간 초과가 발생했습니다. 그래..

11월동안 매일 무조건 할 작은 목표들 - 독서 1줄 - 팔굽혀 펴기 1개 수첩에 리스트를 적고 매일 기록할 것.(현재 11.08까지 성공적으로 진행 중) 독서 - 글쓰기 분야 책 1권 읽기 - 폴리매스 1독

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/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 종만북의 유니온 파인드 코드를 참조한 풀이입니다. 주의할만한 몇 가지 포인트에 대해서만 짚고 가겠습니다. 1. 이름을 int형의 id값으로 변환 문자열로는 트리를 구성하기 불편하기 때문에 int형으로 변환했습니다. 2. find 연산에서의 경로 최적화 이는 중복 연산을 피하기 위해 트리의 구조를 수정하는 작업입니다. find를 수행할 때마다 루트를 찾음과 동시에 경로에 있는 노드의 parent를 모두..

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..