문제 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를 해서 최장 길이를 구했다. 솔직히 이 문제가..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/181188?language=cpp 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 그리디 문제로 정렬 후 그때그때 최선의 선택을 해서 답을 도출하는 문제였다. 문제 풀이 처음에는 target을 정렬한 다음 section vector를 만들어 겹치는 구간을 만들고 각 target 마다 구간 내 가장 겹치는 곳이 많은 곳을 미사일을 쏘는 곳으로 정한 후 section vector에서 --를 해주려고 했었는데 문제 조건에서 target 길이와 s,e 길..
문제 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 구라쟁이 지민이를 위해 그룹을 만들어 해결하는 문제였다. 문제 풀이 처음 문제를 봤을 때는 진실을 아는 사람들을 vector에 집어넣고 while로 더 이상 들어가지 않을 때까지 돌린 후, 마지막에 각 파티마다 확인하는 방법을 생각했다. 코드로 옮기기 전부터 너무 비효율적인 것 같아 고민하던 찰나에 유니온 파인드가 생각났고, parent를 만들어서 푸는 방법을 떠올렸다. 진실을 아는 사람들의 paren..
gitaction ci.yml을 만들었는데 dev 브랜치에 pull request가 올라가도 workflow에 아무 일이 생기지 않았다. 뭐가 문젠지 한참을 고민하다 혹시나 하고 dev 브랜치를 보니 workflow가 반영이 안되어 있었다..! gitaction yml 파일을 main에서 바로 생성하고 push해줬는데, dev에서는 계속 main에 PR 올리고 merge만 해서.. 정작 dev에는 workflow 파일이 반영이 되어있지 않았다. main 브랜치 내용을 dev에 가져오니 잘 실행됐다. main 브랜치에 바로 뭔가를 하는 일이 거의 없다보니 pull 해오는 것을 까먹고 있었다.. 항상 잊지말자~!
