기록하지 않았다면 잃어버릴 시간들

새로운 것을 배우는게 즐거운 개발자입니다.

알고리즘/Codility

요약 백터 A를 input 받습니다. 벡터 A는 1부터 순차적으로 증가하는 원소를 가지고 있어야하는데 그 중 한원소가 빠졌다고 하네요. 그 빠진 원소를 찾아 output 합니다. 아이디어 1. 1부터 N+1까지 1씩 증가하는 등차수열이기때문에 set에 모든 원소를 넣으면 1부터 순서대로 정렬이됨 2. 1부터 N+1 까지 정렬된 set 원소를 1부터 N+1까지 비교해나가며 다를 경우 해당 원소 반환 코드 #include int solution(vector &A) { // write your code in C++14 (g++ 6.2.0) set arr; int cnt = 1; for (auto it : A) { arr.insert(it); } for (auto it : arr) { if (it == cnt)..

2021. 8. 15.

알고리즘/Codility

요약 개구리가 X의 위치에서 점프를하여 Y이상의 거리에 가야하는데 점프거리는 D입니다. X

2021. 8. 15.

알고리즘/Codility

요약 벡터 A를 input받아서 짝이 맞지 않는 숫자를 찾아내는 문제인데요. 문제의 예시를 설명하지면 A[0] = 9 / A[1] = 3 / A[2] = 9 / A[3] = 3 / A[4] = 9 / A[5] = 7 / A[9] = 9 일때 A[0]과 A[2] 는 9로 짝지어지고 A[1]과 A[3] 는 3, A[4] 와 A[9] 는 9로 짝지어 집니다. 9로 짝지어 지는 원소는 다른 방법으로도 가능하겠죠? 여기서 남은 원소는 A[5] = 7만 남게되는데 이 7을 output하는 문제입니다. 아이디어 우선 원소의 중복이 허용되지 않는다는 점에서 C++의 set과 map가 떠올랐습니다. 여기서 map보다는 set이 어울린다고 판단하여 set을 사용하기로 결정했고 int형 정수를 out한다는 것은 중복되지 않..

2021. 8. 15.

알고리즘/Codility

안녕하세요. lesson1에 이어 두번째입니다. 문제입니다. 요약 벡터 A와 정수 K를 input받아서 벡터 A의 원소를 K번 로테이션을 돌린 벡터를 output하는 문제입니다. 로테이션 방법은 가장뒤의 원소를 첫번째 원소로 이동시키고 나머지 원소들을 뒤로 한칸씩 밀어 내는 절차가 1회 로테이션입니다. 물론 로테이션시 벡터 원소에 손실이 없어야합니다. 위에 숫자에 관련된 설명을 보시면 이해가 더 잘 될것같네요. 아이디어 1. 벡터를 입력받아서 로테이션을 돌려야한다고 판단했을때 C++의 벡터 메소드를 사용하면 된다고 판단 코드 vector solution(vector &A, int K) { // write your code in C++14 (g++ 6.2.0) vector::iterator it; if (..

2021. 8. 14.

알고리즘/Codility

안녕하세요 오늘은 Codility가 코딩테스트에 자주 사용된다는 이야기을 듣고 구경하러 갔는데요. 영어로 된 사이트라서 어떤걸 해야할지 잘 모르겠더라구요... ㅠ 들어가자마자 보이는 lesson 카테고리에서 간단하게 몇문제 풀어 볼 수 있어서 도전해봤습니다. 문제는 영문으로 나와서 구글 번역기 돌려서 풀었습니다... ㅠ 요약 정수를 Input 받아서 2진수로 변환 후 1과 1사이에 나오는 0의 최대 길이를 Output으로 내면 됩니다. 예를 들어 9 -> 1001 : 2 // 529 -> 1000010001 : 4 입니다. 1과 1사이에 존재하지 않는 0은 카운팅 하지 않습니다. 32 -> 100000 : 0 아이디어 1. 정수를 2진수로 만들어 String으로 저장한다. 2. String의 앞에서부터 ..

2021. 8. 14.

알고리즘/이론

안녕하세요. 최근 PS 관련 풀이를 하던도중 다익스트라 알고리즘에 대해 접하게 되었는데요. 사실 학부시절때 이론은 수업을 들어서 알고 있었지만 깊게 공부해보지 않아서 코드로 적용하기가 힘들더라구요... 그래서 이번 기회에 조금 깊게 공부해본 내용을 설명 하게 되었습니다. ●다익스트라 알고리즘 요약 1956년에 에즈허르 데이크스트라가 고안 다익스트라 알고리즘은 두 꼭지점 사이의 최단 경로 거리를 구하는 알고리즘 방향성 그래프와 무방향성 그래프 모두에 적용가능 가중치가 음수이면 사용 불가능 현제 길찾기 알고리즘의 기초가 되는 알고리즘 최초의 다익스트라는 출발노드를 기준으로 최소비용 그래프를 저장하여 방문하지 않은 노드 중 가장 가까운 거리에 있는 노드를 먼저 방문을 한 후 또 다른 노드를 방문하게 될 때 기..

2021. 8. 8.

알고리즘/백준

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 백준 온라인저지 1753번 문제입니다. 다익스트라 #include #include #include #define MAX 20001 #define INF 987654321 #define endl "\n" using namespace std; int node[MAX]; vector connect[MAX]; int V, E, K; void init(int a) { for (i..

2021. 8. 4.