코딩 잘하고 싶어

코딩테스트에서 풀었던 문제다. 물론 100점을 맞지는 못했던 문제라서 내가 풀었던 풀이를 다시 살펴보고, 문제를 다시 풀어보았다. 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2022 테크 여름인턴십 코딩테스트 해설 2022년 카카오 여름 인턴십 코딩 테스트가 지난 5월 7일에 5시간에 걸쳐 진행되었습니다. 시간이 부족하여 문제를 풀지 못하는 아쉬움이 없도록 1시간을 늘려 테스트를 진행한 것이 작년과 조금 tech.kakao.com 문제 설명 더보기 XX산은 n개의 지점으로 이루어져 있습니다. 각 지점은 1부터 n까지 번호가 붙어있으며, 출입구, 쉼터,..

요즘은 이분탐색 문제를 풀고 있다. 이분탐색은 코드를 짜는것 자체는 어렵지 않지만, 어떤식으로 어떤 값을 탐색해나가야할지를 알아내는 것이 어렵다. 보통, 1억개 연산에 시간이 1초가 걸리기 때문에 이를 고려하여 시간초과가 날 것 같으면 이분탐색을 해야한다. 이 문제 역시, 어떤값을 이분탐색해야할지를 찾지 못해서 다른 사람의 풀이를 참고하였다. https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.n..

백준의 자료구조 문제들을 풀다가 조금 응용이 필요해서 어려운 문제를 발견했다. 풀이가 흥미롭고 좋은 내용이기도 해서 정리해보려 한다. 자료구조 문제들에는 좋은 문제들이 많은 것 같다. 문제를 읽고 힙을 이용해야하는 것 같아서 힙을 이용해 풀긴 했다. 문제를 볼 때부터 시간 제한이 0.1초로 빡센게 느낌이 쎄했는데, 역시나 시간초과로 문제를 틀렸다. 푼 내용 자체는 틀린것같진 않은데 시간 제한에서 걸린 것 같았다. 어떤 풀이를 이용해 풀어야할지 감이 안잡혀서 구글링을 통해 다른 사람의 풀이를 참고해보았다. 풀이가 정말 흥미로웠다. 아래에서 설명해보겠다. https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N..

자료구조 기초 응용 문제이다. 나는 list로 문제를 풀었지만 stack 두개를 가지고도 문제를 풀 수 있다는 걸 다른사람의 풀이를 보고 깨달았다. 커서를 기준으로 왼쪽과 오른쪽을 스택에 넣어 푼다는 점이 흥미로웠다. 간단하지만 은근히 자료구조를 잘 활용해야 풀 수 있다는 점에서 좋은 문제라고 생각했다. https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net #include using namespace std; int mai..

요즘 백준에서 그래프 유형 문제를 많이 풀다보니 그래프 문제를 푸는 실력이 많이 좋아진 것 같다. 카카오 문제를 풀면 괜히 기분이 좋다 ㅎㅎ 문제를 보고 플로이드 와샬 문제라는 것을 깨닫고 풀었는데, 다익스트라로도 좋은 풀이가 있는 것을 보고 정리해보려한다. https://programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, ..

그래프 문제로 어려운 난이도는 아니지만 좋은 문제 같아서 정리해보려한다. 풀이를 생각하는 과정이 마음에 들었다. https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 마을 안의 도시끼리 한 길로만 연결되고 나머지 길은 없앨 수 있다는 점에서 최소 스패닝 트리를 생각했다. 크루스칼 알고리즘을 사용하여 풀 수 있다. 유지비를 최소로 하기 위해서 정렬 후 유지비가 작은 길부터 크루스칼 알고리즘을 사용하면 된다. 그런데..

예전에 풀어본적이 있던 유형의 문제 같은데 풀이가 잘 생각나지 않았다. 다른 사람의 풀이를 보고 대충 힌트를 얻어 구현했다. https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net #include using namespace std; int n, result = INT_MIN; string s; int cal(int a, int b, char op){ switch(op){ case '+': a += b; break; case '*': ..

dfs를 이용하여 푸는 문제이다. 풀이를 생각해보는데 쉽게 떠오르지 않았다. 고민 끝에 다른사람의 풀이를 참고하였다. https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net #include using namespace std; vector node[10002]; bool visited[10002] = {false,}; int result = 0; int endPoint = 0; void dfs(int p, int len){ if(v..