본문 바로가기

전체 글

백준 17822 원판 돌리기 https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net 삼성 공채에서 나온 시뮬레이션 문제다. 삼성 역테 A+를 목표로 하거나 공채 코테를 목표로 하려면 1시간 안에는 풀어야 한다고 생각한다. 주의 할 점은 시뮬레이션에서 지우거나 없애거나 바꾸거나의 동작을 할 경우 항상 예외를 생각해야한다. 이 문제의 경우 3가지 정도 까다로운 점이 있다. 1. 회전시키기 회전시키려는 배열의 크기가 작다면 임시 배열을 만들어서 회전시키는 걸 추천한다... 더보기
JAVA 클래스의 == , equals 에 대해 알아보자 [Java] Integer.valueOf(127) == Integer.valueOf(127) 는 참일까요? : TOAST Meetup [Java] Integer.valueOf(127) == Integer.valueOf(127) 는 참일까요? meetup.toast.com JAVA 에는 primitive type 과 reference type이 있다. primitivte type는 값 자체를 가지고 있는 변수고, (int float, ....) reference type는 값을 저장하는 주소를 가지고 있다. (Class , Collections 등등) 그러므로 C나 C++ pointer를 이용해서 call by reference를 적용시켰지만, java에서는 reference 자체를 넘기면 call by .. 더보기
백준 17069 파이프옮기기2 https://www.acmicpc.net/problem/17069 17069번: 파이프 옮기기 2 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 파이프를 가로 세로 대각선으로만 이동할 수 있고, 회전할때 45도로만 회전할수 있다. 그러므로 가로로 갈수 있는 방법은 가로 => 가로 대각선 =>가로이고, 세로로 갈수 있는 방법은 세로 =. 세로, 대각선 => 세로이며, 대각선으로 갈수 잇는 방법은 가로 => 대각선, 세로 => 대각선, 대각선 => 대각선이다. (물론 중간에 장애물이 있으면 안된다.) dp[dir][i.. 더보기
백준 세부 13905 https://www.acmicpc.net/problem/13905 13905번: 세부 첫 번째 줄에는 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)이 주어진다. 두 번째 줄에는 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 주어진다. (1≤s, e≤N, s≠e). 다음 M개의 줄 www.acmicpc.net 다익스트라를 변형해서 풀면된다. 기존의 다익스트라가 한 정점에서 다른 정점으로의 최단거리를 구한다고 하면 변형된 다익스트라는 한 정점에서 다른 정점으로의 경로중로 이동하는 가중치의 최소값들의 최대값을 구하는 것이다. 예시로 든 그림을 보면 1에서 5로 가는 경로는 총 4가지다. 1) 1-2-3-5 2) 1-7-3-5 3) 1 -7-5 4) 1-7-6-5 각.. 더보기
백준 12850 본대 산책 2 https://www.acmicpc.net/problem/12850 12850번: 본대 산책2 가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net N = 10억이므로 시간복잡도가 기존의 O(N)인 알고리즘 또한 먹히지 않는다. (물론 10억 개수의 변수를 메모리 공간에 저장하려고 하면 메모리 초과가 날 것이다.) Vertex 사이의 거리가 모두 같다는 점을 이용해서 그래프의 인접행렬의 거듭제곱을 하면 O(8*8*logN)시간에 경우의 수를 구할 수 있다. package 백준; import java.util.Scanner; public class 본대산책2 { static long map[][]; public static void main(String[] a.. 더보기
백준 15961 회전초밥 https://www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 연속해서 K 개의 초밥을 먹었을때 먹을수 있는 최대의 초밥 종류 갯수를 구하는 문제다. 완전탐색을 이용할 경우 초밥의 접시가 N이 최대 300만개, 연속해서 먹을수 있는 접시의 갯수 k 가 최대 3000이므로 시간복잡도가 O(N*k) = O(300만 * 3000) = O(90억)이므로 시간초과가 난다. 연속하는 경우 수를 구할때는 투포인터를 이용하여 풀.. 더보기
백준 13787 Infinity Maze https://www.acmicpc.net/problem/13787 13787번: Infinity Maze For each dataset, output in a line the final row, column and direction of the robot, separated by a single space. The direction should be one of the following: “N” (north), “E” (east), “S” (south) and “W” (west). No extra spaces or characte www.acmicpc.net 미로가 주어졌을때 로봇의 최종 위치와 방향을 찾는 문제다. 로봇은 앞으로만 가며 앞이 벽이나 미로의 경계일때만 90도 방향 시계방향으로 회전한다... 더보기
백준 15925 욱제는 정치왕이야 https://www.acmicpc.net/problem/15925 15925번: 욱제는 정치쟁이야!! 첫째 줄에 각 줄의 컴퓨터 개수 N과 이후의 컴퓨터실 사용 여부가 하나의 공백을 사이에 두고 주어진다. 사용 여부는 사용시 1, 미사용시 0으로 주어진다. (1 ≤ N ≤ 31, N % 2 == 1) 이후 둘째 줄부터 www.acmicpc.net 욱제는 컴퓨터를 끄거나 킬수 있다(그 줄의 켜져 있는 컴퓨터가 더 많다면 전부 다 키고 꺼져있는 컴퓨터가 더 많다면 전부 다 끈다.) 주어진 입력에서 컴퓨터를 모두 켜야하는 경우와 꺼야하는 경우로 나누고 킬수 있는 줄을 모두 켜보고 모든 컴퓨터가 켜져있으면 1 하나라도 꺼져있으면 답은 0이다. package 백준; import java.util.*; impor.. 더보기

티스토리툴바