Algorithm/문제 풀이

[BAEKJOON_2589 - JAVA] 보물섬

문제 www.acmicpc.net/problem/2589 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 풀이 보물의 위치를 정하는 것이 낯선 문제였다. 최단 거리로 이동하는데 가장 긴 시간이 걸리는 곳 → 최단, 최소가 들어간 경우 BFS를 활용한다는 생각 육지인 경우 BFS를 활용한 탐색. BFS를 사용한 최단거리 중 최댓값을 구하는 처음 접하는 문제였다. (최단거리 중 최댓값) 문제 난이도는 평이한 것으로 느껴졌다. 과정 Pos (row, col, 이동횟수) class를 만들어 활용. map을 탐색하며, 육..

2020. 12. 24. 04:37

Algorithm/문제 풀이

[BAEKJOON_9663 - JAVA] N-Queen

문제 www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 ※ 퀸은 위와같이 직선과 대각선 방향으로의 이동 제한이 없다. 1. 첫번째 열에 퀸을 해당 위치 놓는 경우 해당 행,열,대각선에는 다른 퀸을 놓을 수 없다. 2. 다음 열에서 퀸을 놓을 수 있는칸에 다른퀸을 추가한 뒤, 놓을 수 없는칸을 표시 3. 다음 열 또한 마찬가지로 추가 4. 다음과 같은 결과를 얻을 수 있다. 위와 같은 과정으로 열을 기준으로 퀸을 놓을 위치를 탐색해 나간다. 2차원 배열로의 탐색보다 ind..

2020. 12. 24. 04:02

Algorithm/문제 풀이

[BAEKJOON_2805 - JAVA] 나무자르기

문제 www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M을 www.acmicpc.net 풀이 처음에는 부르트포스로 접근 → N(1,000,000) * H(1,000,000,000) → 100만 * 10억 → 시간초과 발생 binary search 사용 → O(N * logM) 잘라낸 나무들의 길이의 합이 자료형의 범위를 벗어날 수 있으므로, long형 타입 사용 과정 입력받은 나무들의 정보를 오름차순으로 정렬 이분탐색 minHeight와 maxHeigh..

2020. 12. 24. 03:22

Algorithm/문제 풀이

[BAEKJOON_14719 - JAVA] 빗물

문제 www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치� www.acmicpc.net 풀이 처음에는 인덱스를 받음과 동시에 처리하려 시도했지만 실패 -> 오른쪽에 물을 담을 빌딩의 위치를 특정하지 못했다. 이후 2차원 배열을 통한 구현 -> 1차원 배열의 구현이 더 효율적일것으로 생각했다. 코드의 가독성을 위한 1차원 배열 구현 변화 : 한번에 두개 사이의 물의 양을 계산 -> 각 위치의 빌딩에서의 물의 양을 계산 네이버,카카오 코딩테스트를 보면서 시간내에 정확하고 빠르..

2020. 9. 13. 23:31

Algorithm/문제 풀이

[BAEKJOON_2206 - JAVA] 벽 부수고 이동하기

문제 www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net 풀이 30분을 잡고 시작했지만 3시간이 걸렸던 어려웠던 문제 보통의 BFS와 다르게 방문관리를 2가지 버전으로 해주어야 했다. ( 시작 시간 AM 01:00 ~ 종료 시간 : AM 04:00) 클래스 Info를 만들어 ( 행, 렬, 이동한칸의 개수, 벽을 부순 여부)를 큐에 담았지만 2차원 배열의 방문관리로는 문제를 풀 수 없었음. 중요한 포인트 벽을 부수고 먼저 도착했을 경우..

2020. 9. 5. 04:37

Algorithm/문제 풀이

[Programmers - JAVA] 네트워크

programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있�� programmers.co.kr 문제 풀이 연결된 네트워크의 연결된 개수를 찾는 문제 과정 연결된 경우를 확인하기 위한 boolean형 visited 생성. dfs 실행전 네트워크의 수 증가. 모든 노드에 대해 dfs 실행. (단, 방문했던 경우는 제외. 연결된 곳 포함) 노드 방문 표시. 해당 노드에서 다른 노드로 연결된게 있는지 전체 탐색. 있는 경우 dfs 호출. 알고리즘 지식 DFS(깊이 우..

2020. 8. 31. 06:55