코딩/백준 (JAVA) 검색 결과
25 개의 검색 결과가 있습니다.
코딩/백준 (JAVA)

백준 14466번: 소가 길을 건너간 이유 6 (Java)

접근 https://www.acmicpc.net/problem/14466 14466번: 소가 길을 건너간 이유 6 첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. www.acmicpc.net 다리로만 건너서 만날 수 있는 소들의 쌍의 수를 구하는 문제이다. 다음과 같은 방법을 이용하여 문제를 해결하였다. 1번부터 K번까지 소들에게 번호를 매기고, 해당 번호를 map에 표시해준다. 1번 소에서 부터 bfs 탐색을 수행하여 만날 수 있는 소들을 하나의 그룹으로 묶어준다. 탐색 중에 길로 연결되어 있는 구간은 통과할 수 없다고 인식하고 더 진..

2022. 7. 3. 19:50
코딩/백준 (JAVA)

백준 1800번: 인터넷 설치 (Java)

접근 https://www.acmicpc.net/problem/1800 1800번: 인터넷 설치 첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차 www.acmicpc.net dfs가 먼저 떠올랐지만 방문 처리 조건과 같은 세세한 내용이 떠오르지 않아 힌트를 확인하고 풀었다. 그래프 이론/이분 탐색/다익스트라/매개 변수 탐색 이라는 힌트를 받고 문제를 해결할 수 있었다. 핵심은 임의의 수 x보다 클 경우 경로의 가중치를 1로 놓고, 그렇지 않을 경우 가중치를 0으로 놓는 다익스트라 함수를 설정한다. 이 함수를 이용하여 N번..

2022. 7. 2. 23:10
코딩/백준 (JAVA)

백준 16639번: 괄호 추가하기 3 (Java)

접근 https://www.acmicpc.net/problem/16639 16639번: 괄호 추가하기 3 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 곱하기의 연산자 우선순위가 더하기와 빼기보다 높기 때문에, 곱하기를 먼저 계 www.acmicpc.net 문제 힌트에서 다이나믹 프로그래밍(DP) 문제임을 확인하고 문제 풀이 진행하였다. DP임을 알고 문제를 다시 읽어보니 1+2+3 이라는 문제가 있을 때, (1+2)+3 으로 풀 수도 있고, 1+(2+3) 으로 풀 수도 있는데 이 과정에서 1+2와 2+3을 각각 dp에 저장하여 dp[i][j]에는 i부터 j까지 계산했을 때의 최대값을 저장할 수 있도록 일반화 하여 문제를 풀면 ..

2022. 7. 2. 00:47
코딩/백준 (JAVA)

백준 18500: 미네랄 2 (Java)

접근 https://www.acmicpc.net/problem/18500 18500번: 미네랄 2 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 구현 문제로 문제에서 주어진대로 코딩하면 되는 단순한 문제였다. 다만 연결된 클러스터를 찾는 과정에서 BFS 알고리즘을 이용하였다. 분명 풀어봤던 문제라고 생각했는데 모종의 이유로 거의 같은 미네랄 문제가 하나 더 있다고 한다. (질문답변 게시판 참고, 별로 중요한 이유는 아니다.) 덕분에 같은 문제를 서로 다른 코드로 풀어볼 수 있는 의도하지 않은 기회가 되었다. 코드 import java.io...

2022. 6. 29. 03:06
코딩/백준 (JAVA)

백준 17780번: 새로운 게임 (Java)

접근 https://www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 문제에서 주어진 대로 구현만 하면 되는 단순 구현 문제였다. 백준에 삼성 관련 문제들이 이런 스타일인 것 같다. 문제의 키포인트는 맨 아래에 있는 말만 이동할 수 있다. 1번말부터 탐색하되 해당 말이 맨 아래에 있으면 이동하지 않고 넘어가면 된다. 하늘색 칸으로 이동 시 방향을 반대로 하고 1칸 이동하되, 반대쪽에도 하늘색 칸일 경우 방향만 바꾸고 제자리에 있는다. 맵 바깥으로 나가는 경우도..

2022. 6. 28. 01:23
코딩/백준 (JAVA)

백준 10021번: Watering the Fields (Java)

접근 https://www.acmicpc.net/problem/10021 10021번: Watering the Fields Input Details There are 3 fields, at locations (0,2), (5,0), and (4,3). The contractor will only install pipes of cost at least 11. Output Details FJ cannot build a pipe between the fields at (4,3) and (5,0), since its cost would be only 10. He therefore b www.acmicpc.net 최소 신장 트리(MST, Minimum Spanning Tree) 문제였다. 모든 노드들이 연결되어 ..

2022. 6. 25. 23:51
반응형