문제 https://school.programmers.co.kr/learn/courses/30/lessons/178870 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 오름차순으로 정렬된 수열의 합이 K인 최단 길이 부분 수열을 찾는 문제였다. 문제 풀이 처음에 완전탐색을 이용해 풀었다가 시간 초과가 났고, 중간에 중단 조건을 걸어 시간을 많이 줄였지만 그래도 시간 초과가 나서 다른 방법을 찾았다. 수열의 최대 길이가 100만이라 O(n^2) 방법이 아닌 O(n)으로 풀어야할 것 같아서 투포인터를 사용해 풀었다. sum이 k보다 클 경우 l 값을 빼준 후..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/1829# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr level2 문제로 dfs를 이용해 영역 개수와 최대 크기를 찾는 문제였다. 문제 풀이 처음에 fail이 떠서 당황했는데, 전역 변수 사용 시 함수 내에서 초기화하라는 주석을 보고 dx와 dy, visit를 solution 내에서 초기화했더니 pass가 떴다. #include using namespace std; int dx[4] = {1,-1,0,0}; int dy[4] = {0,0,1,-..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/181187 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 큰 원 - 작은 원 을 하는 문제였다. 문제 풀이 처음에는 4분의 1 범위에 대해서 완전탐색을 했고, 시간 초과가 났다. 항상 문제를 풀 때 시간복잡도가 어떤 방법으로 풀어야 할지 생각을 좀 해야겠다. 사실 이번에도 안될거 알면서 완전탐색으로 해본거라... 안될 것 같으면 다른 방법을 찾자!! 코테는 제한 시간이 정해져 있으니까! #include #include #include using ..
문제 https://www.acmicpc.net/problem/1259 1259번: 팰린드롬수 입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 1 이상 99999 이하의 정수가 주어진다. 입력의 마지막 줄에는 0이 주어지며, 이 줄은 문제에 포함되지 않는다. www.acmicpc.net 팰린드롬 수인지 아닌지 확인하는 문제였다. 문제 풀이 정수를 문자열로 입력받았고 left와 right를 옮기면서 동일한지 확인해줬다. 만약 다르다면 팰린드롬 수가 아닌것으로 판단했다. 최근에 골드 문제만 풀다가 브론즈 문제를 푸니까 너무 쉽고 좋다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include using namesp..
문제 https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net string 배열을 길이순, 사전순으로 정렬하는 문제였다. 문제 풀이 사실 c++을 사용하면서도 string은 잘 사용하지 않고 char 배열을 많이 사용했는데, 확실히 string이 더 편하긴 하다. 앞으로는 string을 적극 사용해야겠다. string 사전순으로 비교할 때 >로만 비교할 수 있는게 충격적이다. 조건이 2개 이상일 경우 compare 함수를 커스텀하는 것도 처음..
문제 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 각 N에 대해 N → X → N 최단 경로를 구하고, 각 최단 경로 중 최댓값을 구하는 문제였다. 문제 풀이 N이 1000까지여서 플로이드 워셜 알고리즘을 이용해 풀었다. 최댓값은 이전 문제를 풀 때 정한 값이다. 이 문제에서는 100 * 10000보다 큰 값이면 돼서 이전에 사용하던 값을 그대로 사용했다. #define _CRT_SECURE_NO_WARNING..
문제 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 1 → u → v → N (혹은 1 → v → u → N)의 최단 경로의 길이를 찾는 문제였다. 문제 풀이 플루이드 워셜 알고리즘을 이용해 풀었다. 처음에 1 → u → v → N 경우에 대해서만 최솟값을 찾아줘서 틀렸는데 1 → v → u → N 경우와도 비교해 최솟값을 구해서 맞췄다. MAX_INT 값은 간선의 최대 길이인 1000 * 간선의 ..
문제 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 노드와 노드 사이의 최장 길이를 찾는 문제였다. 문제 풀이 처음에 모든 정점에서 dfs를 돌려서 Max 값을 구했는데 그랬더니 시간 초과가 났다. V가 최대 100,000이어서 시간 초과가 나는 것은 당연했고 다른 방법을 찾았다. 첫 번째의 dfs로 1번 노드와 비교했을 때 가장 멀리 있는 정점을 찾았고, 그 정점에서 다시 dfs를 해서 최장 길이를 구했다. 솔직히 이 문제가..
