본문 바로가기

코딩노트210

[BOJ] 2470 : 두 용액 문제 링크 2470번: 두 용액 (acmicpc.net) 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 풀이 두 용액의 특성값의 합이 0에 가장 가까운 용액을 만드는 문제. 브루트포스로 해결하려 한다면 O(N^2) 이기때문에 당연히 시간초과가 난다. 투포인트 기법을 사용해야하는데 말 그대로 그냥 두 개의 점을 찍는 방식이다. 먼저 용액의 특성값들이 담긴 벡터를 오름차순으로 정렬한다. Left를 0 Right를 N-1로 잡고(Left와 Right가 두 점이 된다) 벡터의 Le.. 2022. 2. 2.

[BOJ] 10217 : KCM Travel 문제 링크 10217번: KCM Travel (acmicpc.net) 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net DP와 다익스트라 알고리즘을 함께 활용해야하는 문제였다. 풀이 처음에 Dp에 그 지점까지 왔을 때의 시간 또는 비용을 저장해서 다음 번에 다시 그 지점에 도착했을 때 시간적으로 혹은 비용적으로 더 비효율적이라면 멈추고 다른 경우를 생각하는 방식을 떠올렸다. 예전에 백트래킹 문제에서 이렇게 풀었던 기억이 나서 이번에도 백트래킹으로 접근했다. 하지만 백트래킹은 .. 2022. 1. 27.

[BOJ] 5719 : 거의 최단 경로 문제 링크 5719번: 거의 최단 경로 (acmicpc.net) 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 풀이 최단경로로 통하는 길을 모두 제외한 나머지 경로 중에서 갈 수 있는 최단경로를 구하는 문제. 1. 최단경로에 포함되는 정점을 제거하면 길이 있어도 못가기 때문에 안됨 2. 최단경로를 탐색하고 도로를 바로 제거하면 만약 최단경로가 여러개이면서 최단경로끼리 같은 도로를 공유한다면?? 두번째 최단경로는 탐색할 수 없다. => 그래서 내가 떠올린 아이디어는 탐색한 최단경.. 2022. 1. 27.

[BOJ] 9370 : 미확인 도착지 문제 링크 9370번: 미확인 도착지 (acmicpc.net) 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 어느 부분에서 틀렸는지 감이 안와서 한참을 헤맨 문제였다. 풀이 처음에 나는 다익스트라 알고리즘 한 번으로 풀려고 시도했다. 다익스트라로 돌면서 지정된 도로를 지나가기 전에는 도착점에 false를 표기하고 지정된 도로를 지나간 후 부터는 true를 표기하기로 했다. 그렇게 해서 만약 최단거리로 목적지를 갔을 때 true라고 표기돼있으면 그 목적지는 유효한 것으로 판단 하려고 했다. 1 2 3 4.. 2022. 1. 24.

[BOJ] 1707 : 이분 그래프 문제 링크 1707번: 이분 그래프 (acmicpc.net) 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 풀이 처음 떠올린 내 아이디어는 이렇다. DFS를 이용해 탐색하면서 인접한 정점은 현재 내가 있는 정점과 다른 그룹에 정점 번호를 집어 넣는다. 그리고 그룹에 새로운 정점이 들어올 때 마다 같은 그룹에 있는 앞서 들어온 정점들과 인접한지 체크한다. 그렇게 짠 코드가 아래의 코드이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 2.. 2022. 1. 21.

[BOJ] 1697 : 숨바꼭질 문제 링크 1697번: 숨바꼭질 (acmicpc.net) 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 실버라고 만만하게 봤다 풀이 BFS를 활용한 문제. 앞으로 한 칸을 가든 뒤로 한 칸을 가든 순간이동을 하든 사용되는 시간은 동일하다. 큐를 만들어서 위치와 시간을 저장하려고 했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #de.. 2022. 1. 20.

[BOJ] 1579 : 앱 문제 링크 7579번: 앱 (acmicpc.net) 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 풀이 일단 내가 생각해낸 아이디어는 Cost 를 기준으로 오름차순 정렬한 다음 백트래킹으로 메모리를 더해가면서 메모리의 합이 M을 넘으면 그때의 Cost를 기존과 비교해서 최솟값을 저장하는 방식. 먼저 앱에 대해서 우리가 취할 수 있는 경우의 수는 1. 비활성화 한다 2. 그대로 둔다 두 가지 방법이 있다. 이를 바탕으로 백트래킹을 작성하면 아래의 코드가 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 1.. 2022. 1. 20.

[BOJ] 10942 : 팰린드롬? 문제 링크 10942번: 팰린드롬? (acmicpc.net) 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 풀이 팰린드롬이란 양쪽이 대칭을 이루는 것을 말한다. 예를 들면 12321 같은 것들. 최대 2000길이의 수열을 1000000회 동안 매번 팰린드롬인지 검사하면 0.5초의 시간으로 절대 부족하다. 그래서 palinedrome이라는 이차원 배열을 만들어 palinedrome[Start][End] 까지가 팰린드롬인지 아닌지 저장해뒀다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2.. 2022. 1. 20.

[BOJ] 6716 : Collecting Beepers 문제 링크 6716번: Collecting Beepers (acmicpc.net) 6716번: Collecting Beepers Karel is a robot who lives in a rectangular coordinate system where each place is designated by a set of integer coordinates (x and y). Your job is to design a program that will help Karel pick up a number of beepers that are placed in her world. To do so www.acmicpc.net 백트래킹이라고 소개되어있어서 풀어본 문제지만 딱히 백트래킹으로 풀리는 문제가 아니라서 백트래킹 문.. 2022. 1. 19.

이전 1 ··· 20 21 22 23 24 다음

티스토리툴바