본문 바로가기

알고리즘 문제/백준50

[백준 - Java] 15683번 : 감시 (삼성 SW 역량 테스트 기출 문제) 문제 www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 설명 헷갈려서 엄청 오래 걸린 문제다... 근데 진짜 말그대로 1~5번까지 cctv를 90도씩 돌려가며 조합해서 사각지대의 최솟값을 구해야 한다. 방향을 바꾸는 과정은 시계방향으로 상 우 좌 하로 0, 1, 2, 3 순서이다. (순서는 그냥 자기 마음대로 정해면 됨 나는 상우하좌가 편해서 저렇게 외웠다!) CCTV는 1~5까지 총 5개의 형태가 있다. 각각의 경우를 90도 회전하는 경우를 생각해.. 2021. 2. 11.
[백준 - Java] 14499번 : 주사위 굴리기 (삼성 SW 역량 테스트 기출 문제) 문제 www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 설명 주사위 굴리는걸 어떻게 해야 하나 고민하는데 시간을 많이 쏟았다 ㅠ____ㅠ 근데 주사위만 굴리면 다 해결되는 문제. ㄹㅇ 아래 주사위를 기준으로 상하좌우 굴려보면 규칙을 찾을 수 있다. 2 4 1 3 5 6 나는 주사위의 Top, Bottom, Up, Down, Left, Right 6면을 모두 고려해 주사위를 굴렸는데 이렇게 하지 .. 2021. 2. 10.
[백준 - Java] 3190번 : 뱀 (삼성 SW 역량 테스트 기출 문제) 문제 www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 설명 문제에서 설명한 대로 차례로 구현하면 된다. 특이점이라면 뱀의 정보를 Deque에 저장한다. Deque는 양방향으로 구현한 Queue로 머리와 꼬리의 위치가 추가되고 삭제되는 뱀의 정보를 저장하기에 적합하다. 방향의 경우 상 좌 하 우 (0, 1, 2, 3) 순서로 dx, dy배열을 만들었고, 나머지 연산을 통해 간단히 90도 방향 전환을 할 수 있게 만들었다. ex) snakeDir = (snakeDir+.. 2021. 2. 9.
[백준 - Java] 1931번 : 회의실 배정 문제 www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 처음엔 막 시작시간이랑 끝 시간이랑 비교하고 이중 for문 쓰면서 삽질했는데 시간 초과남~~! 정렬을 써서 for문은 최대한 한번으로 끝내도록 설계해야 함 끝나는 시간을 기준으로 오름차순 정렬, 끝나는 시간이 같다면 시작 시간 기준 오름차순으로 정렬을 해놓는다. 끝나는 시간이 제일 빠른 회의부터 마지막 회의까지 돌면서 현재 회의의 끝나는 시간과 같거나 더 늦은 시간에 시작하는 회의라면 회의실을 사용할 수 있다. 이런 식으로 마지막까지 확인하면 사용할 수 있는 최대의 회의수를 구할 수 있다. 전체 코드 import java.. 2021. 1. 25.
[백준 - Java] 1946번 : 신입 사원 문제 www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 설명 처음에는 이해가 안 갔다. 하지만 생각해보면 쉬운 문제. 먼저 서류 등수를 기준으로 오름차순 정렬을 한다. 정렬을 해놓으면 이중 for문을 쓰는 등의 일일이 찾는 일 없이, for문 하나로 순차적으로 파악이 가능해진다. (정렬 안 하고 이중 for문이라도 쓰는 순간 시간 초과남!!) 서류 1등은 다른 지원자들과 비교 안 해도 됨. 서류 2등부터 면접 등수만 가지고 다른 지원자보다.. 2021. 1. 25.
[백준 - Java] 1389번 : 케빈 베이컨의 6단계 법칙 문제 www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 풀이 전 여담 풀고 나니 별거 아닌 문제였는데 많은 시간을 소비했다ㅠㅠ 일단 나는 BFS로 풀었다. 근데 검색해보니 이게 플로이드 와샬 알고리즘이라고 한다. (추후에 공부 다시 해서 정리할 것!!) * BFS 원래 알고리즘 대로 쓰면 안 됨 조건이 필요 예제에서 1번과 5번 친구의 경우 (1, 3, 4, 5)로 4번 만에 친구가 되는데 (1, 4, 5)로 최.. 2021. 1. 23.
[백준 - Java] 16234번 : 인구 이동 문제 www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 설명 문제의 설명이 부족한 것 같다. 처음에 나는 인구 이동을 할 때마다 정답 변수 answer를 +1 해주어 총인구 이동 수를 구했다. 하지만 인구 이동 할때마다 +1 해주는 것이 아니라, 인구 이동이 총 며칠 동안 이루어졌는지를 구해야 한다. 즉, 전체 정점(나라)을 돌면서 연합이 이루어지고, 인구가 이동하는 작업을 따져본다면 인구 이동은 0~n번 일어날 수 있다. 예를 들어 입력 5번의.. 2021. 1. 20.
[백준 - Java] 5567번 : 결혼식 문제 www.acmicpc.net/problem/5567 5567번: 결혼식 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2,3,4 3명의 친구를 결혼식에 초대한다. www.acmicpc.net 설명 ai와 bi가 친구라면, bi와 ai도 친구관계이기에 양방향 그래프로 만들었다. 그리고 친구관계를 인접 리스트를 이용해 표현했다. 상근이는 1번이고, 1번과 인접한 정점(친구). 1번과 인접한 정점의 인접한 정점(친구의 친구) 딱 3번을 거친, 3번까지 BFS 탐색한 정점까지만 결혼식에 초대할 수 있다는 것. 정점의 방문여부를 확인하는 visited배열은 기존에 작성할 때 boolean으로 주로 선언.. 2021. 1. 19.
[백준 - Java] 1325번 : 효율적인 해킹 (자바는 시간초과!!!!) 문제 www.acmicpc.net/problem/1325 1번 정점으로 5번 정점은 해킹될 수 있다. 5번 정점을 시작으로 dfs를 돌면서 인접한 2번 정점에 들렸다. -> 2번 정점으로 5번 정점은 해킹될 수 있다. public static void dfs(int start, boolean[] visited, ArrayList[] list) { visited[start] = true; //System.out.print(start + " "); for (int node : list[start]) { if (!visited[node]) { computer[node]++; dfs(node, visited, list); } } } dfs 재귀 호출 전 총 N개의 크기를 가진 computer 배열에 인접한 정점.. 2021. 1. 18.
[백준 - Java] 7576번 : 토마토 문제 www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 주요 변수 설명 int[][] map : N * M의 2차원 배열을 만들어 토마토의 정보를 저장한다. int mapCount = (N*M) - 빈칸의 총 개수 : 모든 토마토가 익었나 확인을 하기 위해, 전체 공간의 개수를 파악해놓는다. int ripenedCount : 익은 토마토의 총 개수 int day : 익을 때 까지의 날짜 ArrayList ripenedTomato : 매번 익은 .. 2021. 1. 15.
반응형

티스토리툴바