알고리즘
2020 카카오 인턴십 for Tech developers 코딩테스트 2번
문제 programmers.co.kr/learn/courses/30/lessons/67257 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 programmers.co.kr 문제 분석 개념은 어렵지 않았으나 1번과 같이 구현이 까다로웠던 문제였던것 같다. 잘못된 연산방식이 나오지 않고, 하나의 연산자는 두개의 수를 연산하는 작업을 하는 것이 조건으로써 주어졌으므로, 나는 수와 연산자 string을 하나하나씩 분리해서 vector에 집어넣고, 하나씩 꺼내면서 우선순위에 맞게 연산하였다. 3개의 연산자에 대해, 순열이므로 3! = 6이고, 전..
코딩 테스트 대비 백준 정리
지금 까지 푼 문제중에서 꽤 어렵거나 배울만한 점이 있었던 것들을 정리해보자. 1. 1016번 : 제곱 ㄴㄴ 수 1 ≤ min ≤ 1,000,000,000,000 (long long) min ≤ max ≤ min + 1,000,000 (10^6, 8MB) 제곱 ㄴㄴ 수 : 1 외의 정수 제곱수로 나누어 떨어지지 않는 수 예시 : 1~10 = 1,2,3,5,6,7,10은 제곱수? ㅇㅇ / 4,9는 제곱수? ㄴㄴ 1부터 sqrt(max)까지 모두 하나하나씩 한다? -> min의 범위가 너무 큼 나누어진다? -> 소수가 아니다. 즉, 제곱수로 나누어 떨어진다 -> 소수의 제곱으로 나누어 떨어진다. 예시) 18 -> 3^2 * 2 그렇다면 1,000,000,000,000까지의 모든 소수를 확인할 수 있을까? 제..
백준 1939 중량제한
문제 문제 분석 이전에 2585번 경비행기를 푼 경험이 있어서 그런지 그렇게 어렵진 않았다. 차라리 이걸 먼저 풀어보고 그걸 풀었으면 더 빠르게 풀 수 있지 않았을까 하는 아쉬움도 있었다. 이 문제 또한 파라매트릭 서치를 쓰는 문제였는데 DFS와 BFS만으로는 풀 수 없는 문제일까? 라는 생각때문에 한번 고민을 해봤었는데, 다음과 같은 이유 때문에 힘들것 같다고 느꼈다. 우선 조건에 대해서 살펴보면 O(N) = 10^4이고, 연결 그래프의 최댓값을 알기 위해서는 start_idx -> end_idx로의 모든 경로를 다 찾은다음에 비교하는 수 밖에 없기 때문에, 경로의 갯수는 O(N*M) = O(10^9) 까지도 될 수 있기 때문에 불가능한 경우가 생길 수 있을 것이다. 아마 BFS는 메모리 초과, DFS..
백준 2585 경비행기, 파라매트릭 서치 심화
문제 문제 분석 개인적으로 접근 방법은 알겠는데 구현에 어려움이 있던 문제였다. 코테에 나왔다면 영락없이 바로 걸러졌을듯 이 문제의 요점은 최단거리가 아니라 [경로를 포함하는 간선 길이의 최댓값] 중 최솟값 을 찾는것이다 우선 가장 먼저 접근했던 방법은 그리디 방식이었다. 그런데 접근 방식에 대해서 생각해보니 이치에 맞지 않았다 1번 가정 : 다음 점은 반드시 x+a, y+b 즉 점을 기준으로 1사분면에 존재할 것이다 -> 지그재그와 같은 경로가 최적이라면 더 1사분면으로 가는 것이 더 손해일 수도 있다. 2번 가정 : 하나의 길이를 정해두고 그 길이보다 반드시 큰 경로로만 갈 것이다. -> 말이 안됨 첫번째 선택한 길이 더 클 수도 있음, 길이는 의미가 없다. 결국에 생각하다 보니, 길이를 정해두고 그..
백준 1655 가운데를 말해요
문제 문제 분석 꽤나 재미있었던 문제였다. 우선 조건부터가 0.1초로 재미있었는데 10^7이라는 제약조건이 꽤나 문제의 접근방식을 제한했던 것 같다. 입력의 범위는 입력횟수 N에 대하여 1 > mid; cout large_pq.size()) { large_pq.push(mid); mid = small_pq.top(); small_pq.pop(); } if(small_pq.size() + 1 < large_pq.size()) { small_pq.push(mid); mid = large_pq.top(); large_pq.pop(); } } cout
프로그래머스 42895 N으로 표현
문제 문제 분석 나는 그냥 DP로 풀었다. 현재 N의 갯수가 i라고 할 때 가능한 모든 경우의 수를 DP[i][something]에 저장하자고 하고 1부터 i-1까지는 모두 다 정확하게 정의되어 있다고 하자. 그렇다면 i는 다음과 같이 2개로 나눌 수 있다. (1, i-1), (2, i-2), (3, i-3) ...(i-1, 1) 그리고 이렇게 분할된 두개의 조각에 존재하는 모든 조합의 사칙연산의 결과값을 DP[i][idx]에 저장한다. 이렇게 하다보면 결국에는 될것이다. 이걸 dfs로써 풀 수 있다고 하는데 그런 분들의 코드를 보면 하나같이 왼쪽의 데이터를 새로운 데이터로 구성하고 오른쪽은 고정된 값들 ( temp = temp * 10 + N / 즉 N, NN, NNN등)으로만 구성하던데 이렇게 하면 ..