https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 1. Logic 특정 지점에서 출발하는 것을 선택하지 못하고 선택하더라도 그 지점에서 최솟값이 나오리라고 장담할 수 없다. 그렇기 때문에 도착한 섬이 출발한 섬과 다른 섬인지를 구별하는 아이디어를 떠올려야 하는 문제이다. 문제에서는 섬을 1로 입력받지만 나는 처음에 -1로 받은 뒤 각 섬마다 섬 내부에서 BFS를 돌아서 각 섬에 숫자를 매겨줬다. 각 섬의 번호가 매겨지면 섬마다 BFS를 돌며 다른 섬까..
알고리즘
군대에 처음 들어올 때 세웠던 목표 세가지가 있었다. 목표를 꼭 이루기 위해 블로그에서도 적어놨었다. 그중에 가장 이루고 싶었고 무조건 이루고 나가야겠다고 다짐했던 첫번째 목표인 백준 solved.ac 티어 플래티넘을 달성했다. 이전에는 프로그래밍을 거의 해보지도 않았고 알고리즘이라고 했을때 단순 입출력 받아서 처리하는게 알고리즘인줄 알았다. 지금 생각하면 약간 부끄럽다..ㅎ 이 생각을 군대 들어오기전까지 가지고 있었으니까 얼마 지나지 않은 과거이다. 개발자를 진로로 삼아야겠다는 다짐을 군대 오기 약 3달전에 했으니 그럴수도 있나? 여튼 전공은 컴퓨터공학과지만 진로를 잡은 시기가 늦어 그만큼 남들을 따라잡기 위해 스스로 꾸준히 했다. 문제가 안풀리면 짜증나지만 풀렸을 때 희열감이 미치겠다. 희열감 없었으..
https://www.acmicpc.net/problem/14921 14921번: 용액 합성하기 홍익대 화학연구소는 다양한 용액을 보유하고 있다. 각 용액은 -100,000,000부터 100,000,000사이의 특성 값을 갖는데, 같은 양의 두 용액을 혼합하면, 그 특성값은 두 용액의 특성값의 합이 된다. 당신 www.acmicpc.net 1. Logic 기본적인 이분탐색 문제이다. 0에 가깝다는 것을 판단하는 것은 절댓값을 통해 가장 작은 값을 찾으면 된다. 2. Code #include using namespace std; int n; vector input; int ans = 0x3f3f3f3f; void solve() { int start = 0; int end = n - 1; while(star..
https://www.acmicpc.net/problem/1477 1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다. N = 0인 경우 둘째 줄은 빈 줄 www.acmicpc.net 1. Logic 처음에 이 문제를 보고 0~L까지 거리를 구한 값을 우선순위 큐에 넣은 다음 큰 숫자부터 2로 나눠서 m만큼 반복하면 쉽게 풀릴 것 같다고 생각했다. 하지만 여기에는 반례가 있었다. 만약 테스트 케이스가 0 2 100 다음과 같이 주어졌을때를 가정해 보면 먼저 답은 33이 나와야한다. 우선순위 큐에는 0~100까지 100이 들어가있을 것이다. 우선순위 큐로 항상 2로 ..
https://www.acmicpc.net/problem/2295 2295번: 세 수의 합 우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최 www.acmicpc.net 1. Logic 이 문제를 접근할 때 처음에는 이분탐색이 아닌 투포인터로 접근하려고 했었다. 입력이 1000개이기 때문에 시간복잡도를 맞춰야 했고 N^3으로는 풀지 시간내에 계산을 못한다. 적어도 N^2logN정도를 맞춰야 했다. 이분탐색으로 가능했는데 이분탐색에 대한 로직은 1. 입력 받은 수를 토대로 3개의 수 중 2개의 수를 합쳐놓은 sum 배..
https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 1. Logic - 처음 문제를 딱 봤을 때 map이 먼저 생각났다. map로 선언한 후 접근하면 풀릴 것 같았다. 그리고 이후에 문제의 범위를 봤을때 500000이길래 이분탐색을 사용해서 숫자를 찾아야하는구나 라고 느꼈다. 사실 map과 이분탐색 둘다 해봤는데 둘다 통과 된다. 하지만 이분탐색이 시간복잡도가 더 작을 뿐이다. 2. Code map을 이용한 풀이 #i..
https://www.acmicpc.net/problem/16401 16401번: 과자 나눠주기 첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN ≤ 1, www.acmicpc.net 1. Logic 스탠다드한 이분탐색 문제이다. 중앙값을 구한 뒤 입력 받은 사탕들 중에서 나눗셈연산자로 사탕의 갯수를 구해주면 된다. 2. Code #include using namespace std; int nephew, cookie; vector input; bool check(int val) { int re..
https://www.acmicpc.net/problem/13144 13144번: List of Unique Numbers 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. www.acmicpc.net 1. Logic 이 문제는 투포인터를 사용하여 풀 수 있다. 문제를 푸는 로직은 1. start, end를 0으로 초기화 한다. 2. input 받은 값을 순회하며 중복이 없을 때 까지 map에 입력한다. 3. 중복이 있는 문자가 나오면 멈추고 수열의 갯수인 end-start-1개를 더해준다. 4. 과정을 반복하며 입력받은 수의 끝까지 반복해준다. 2. Code #include using namespac..
https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 1. Logic 조건대로 계산해보면 피보나치 수열과 같다는 것을 알 수 있다. 그대로 Topdown 방식으로 구현해줬다. 2. Code #include using namespace std; long long dp[91]; long long solve(int n) { if(n == 1 or n == 2) return 1; long long &ret = dp[n]; if(ret != 0) ..
https://school.programmers.co.kr/learn/courses/30/lessons/12987 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. Logic 무조건 한번은 경기를 해야하기 때문에 안할 수는 없고 순서를 바꿔줄 수는 있다. 그렇기 때문에 A를 항상 작게 유지시켜 줘야한다. 오름차순 정렬을 한 후 A
