https://www.acmicpc.net/problem/1253 난이도 : 골드 4 알고리즘 유형 : 이분탐색, 투포인터  풀이 시간 : 51분 문제 풀이 대락난 감;;; 했던 문제. 문제의 이해를 잘못해서 삽질을 엄청 한 문제이다. 처음 문제에 접근했을 때는, 해시맵을 사용해서 배열의 데이터들을 저장한 다음, 2중 반복문을 돌면서 해시맵에 키가 존재한다면, ans에 더해주려고 하였다. 하지만, 틀렸습니다. 를 받았고 이유를 찾아보다가 여러 상황이 있음을 깨달았다. 1. 입력되는 값의 크기는 오름차순으로 주어지지 않는다.2. 같은 입력값이 들어올 수 있다.3. 한 번 선택된 GOOD수(좋다)는 다시 선택되면 안된다.4. GOOD수를 만들 때는 선택된 나머지 두 수가 포함되면 안된다. 또한, $N ≤ 2..

https://school.programmers.co.kr/learn/courses/30/lessons/77486 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도 : Level 3 알고리즘 유형 : 트리, 해시맵 풀이 시간 : 33분 문제 풀이 일단 문제가 꽤 길다. 문제를 읽어보면 어떤 직원이 판매한 칫솔의 수익에서 10%만큼 직원의 추천인(트리의 부모)에게 전달되고, 이 구조가 재귀적으로 반복되고 있음을 알 수 있다.문제를 풀며 주의해야 할 점은 수익을 나누는 방법인데, 돈을 받은 직원은 받은 돈의 10%를 추천인 직원에게 넘기고, 나머지를 자기가 갖게 되는 것이다. 다시 말해서 돈의 10%를..

https://www.acmicpc.net/problem/4485 난이도 : 골드 4 알고리즘 유형 : BFS , 다익스트라 풀이 시간 : 49분 문제 풀이 목적지까지 가는 데 뺏기는 루피의 최솟값을 구하는 문제이다. 처음에는 단순히 BFS 돌리면 되겠지 ~ 하고 룰루랄라 돌렸는데 아뿔싸 ! BFS를 돌리는 도중, 방문처리를 하게 되면 다른 노드에서 온 값에 대해 처리를 하지 못해 빼앗기는 최소 루피를 구할 수 없게 된다.따라서 나는 다익스트라 알고리즘을 사용해보았다. 다익스트라 알고리즘이란 ? 최단거리를 찾기 위한 알고리즘 중 하나이며, 현재 값과 가중치를 더해 새로운 값과 비교하고, 우선순위큐를 사용하므로 최단거리를 찾을 수 있다.  그런데, 우선순위큐를 구현하고, 실행하자 바로 시간초과가 뜨는 것이..

https://www.acmicpc.net/problem/2457 난이도 : 골드 3 알고리즘 유형 : 그리디  풀이 시간 : 42분 문제 풀이 문제의 조건을 먼저 확인해보면, 1. 공주가 가장 좋아하는 계절인 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 한다.2. 정원이 넓지 않으므로 정원에 심는 꽃들의 수를 가능한 적게 한다. 라고 명시되어있다. 여기서 우리가 생각해야 할 조건은 2번 조건이다. 정원에 심는 꽃들의 수를 가능한 적게 하며 공주의 요구사항을 만족해아 하기 때문에 우리는 완전탐색, 그리디와 같은 알고리즘을 생각할 수 있다.문제 조건을 확인해보면, 입력으로 주어지는 꽃이 피고 지는 날짜의 개수가 $N ≤ 100000$으로 주어져있다. 완전탐색을 사용하면 시간초과가 ..

https://www.acmicpc.net/problem/1865 난이도 : 골드 3 알고리즘 유형 : 그래프이론, 벨만-포드 풀이 시간 : 1시간 7분 문제 풀이 이 문제를 접하며 벨만포드 알고리즘을 처음 다뤄보았다. 근데 문제에 허점이 많은 것 같다 ... 결론부터 말하자면 접근은 벨만포드 알고리즘으로 하였지만, 풀이 방법은 벨만포드 알고리즘이라고 할 수 없다.그 이유를 면밀히 따져보자. 우리가 흔히 아는 다익스트라 알고리즘의 경우, 현재 정점에서 다음 정점까지 최소한의 비용을 업데이트하며 탐색을 이어나간다. 따라서 다익스트라 알고리즘은 그리디 알고리즘의 원리를 따른다. 하지만, 벨만포드 알고리즘은 모든 정점에 대해서 탐색을 진행해본다. 따라서 완전탐색에 가깝다고 생각한다. 벨만포드 알고리즘이 더 궁..

https://www.acmicpc.net/problem/2660 난이도 : 골드 5 알고리즘 유형 : 그래프탐색, BFS 풀이 시간 : 22분 문제 풀이 예를 들어 어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다. 어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나 친구의 친구임을 말한다. 또한 어느 회원의 점수가 3점이면, 다른 모든 회원이 친구이거나, 친구의 친구이거나, 친구의 친구의 친구임을 말한다.문제 설명이 조금 헷갈리게 되어있었지만, 잘 읽어보면 궁극적으로 각 회원의 점수는 다른 회원을 만나기까지의 깊이(Depth)와 같다고 생각하면 된다.이를 그림으로 표현하면 다음과 같다.( 검정 숫자 : 정점의 번호 | 빨간 숫자 : 방문 시간 )1번 회원이 모든 회원을 만나는..

https://www.acmicpc.net/problem/1389 난이도 : 실버 1 알고리즘 유형 : 그래프탐색, BFS풀이 시간 : 26분 문제 풀이 문제를 간략히 요약하자면, "한 사람이 모든 사람을 만나는 데 걸리는 비용이 가장 적은 사람을 찾아라"이다.정점 N의 범위가 작았고(N ≤ 100), 모든 사람의 경우를 구해야 하기 때문에 BFS를 사용하여 값을 구한 뒤, 최솟값을 비교하면 될 것이라고 생각하였다.최솟값 비교의 경우, BFS를 진행하며 방문한 다른 정점과의 거리를 모두 더한 뒤 거리의 합을 비교하는 방식을 사용하였다. 위 문제를 풀며, 효율성을 높이기 위해 다음과 같은 방법을 사용하였다.정점의 합을 계산해 주는 과정에서 이전에 계산된 정점의 합보다 커지게 된다면, 그대로 함수를 종료하도..

https://www.acmicpc.net/problem/1072 난이도 : 실버 3 알고리즘 유형 : 이분탐색 풀이 시간 : 35분 문제 풀이 X ≤ 1000000000 으로 주어졌기 때문에 완전탐색으로 풀면 시간초과가 날 것이라고 판단하였다.따라서, 이분탐색 알고리즘을 사용해 Z가 증가하는 최솟값을 찾아주는 방법을 사용하였다.여기서, 조절해주어야 하는 값은 "이후 실시한 게임 수"로 정하였다.왼쪽(left) : 0오른쪽(right) : X의 최댓값(1000000000)중앙값(mid) : 실시한 게임 수 ※ 주의할 점 ※1. 최댓값의 범위가 매우 크기 때문에, int형 대신 long long int형을 사용하였다.2. 확률 Z 계산 시, c++의 부동소수점 계산 오차를 방지하기 위해 100을 먼저 곱해..