https://school.programmers.co.kr/learn/courses/30/lessons/43236# 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도 : Level 4 알고리즘 유형 : 이분탐색, 매개변수탐색 풀이 시간 : 51분 문제 풀이 이분탐색은 어떤 값을 조건으로 잡는지가 매우 중요하다. 문제 설명을 간단히 하자면, 징검다리 중 바위 `N`개를 제거하는 모든 경우들 중 거리의 최솟값이 가장 큰 값을 return하라이다. 한 줄로 요약하려니 이해하기 힘들지만 문제에서 설명해주는 예제를 보면 이해가 쉬울 것으로 생각된다. 우선, 변수들의 범위를 확인해보면 $distance ≤ 1..

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번 회원이 모든 회원을 만나는..

삼성 SW 역량테스트 2024 하반기 오전 1번 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai 알고리즘 유형 : 구현, 시뮬레이션, BFS 풀이 시간 : 2시간 57분 문제 풀이 문제 쓱 읽고 별 거 없네 ~라고 생각했다가 좌표를 매칭해주는 과정에서 큰코다친 문제다. . . .이 문제의 핵심 포인트는 "시간의 벽 단면도(이하 단면도)와 미지의 공간의 평면도(이하 평면도) 간 좌표 연결"이라고 생각한다. 문제에서 제공하는 맵의 정보는 다음과 같다.한 변의 길이가 $N$인 2차원 평면이며, 그 사이 어딘가에는 한 변의 길이가 $M$인 정육면체 형태의 ..

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을 먼저 곱해..

https://www.acmicpc.net/problem/20207 난이도 : 골드 5 알고리즘 유형 : 그리디, 정렬 풀이 시간 : 32분 문제 풀이 본 문제는 주어진 일정을 커버하기 위한 코팅지의 최소 넓이를 구하는 문제이다.최소 넓이를 구하기 위해 그리디하게 문제에 접근할 수 있을 것이라 판단하였다. 또한, 지문에 정렬 조건을 친절히(?) 설명해주어서 그대로 적용하였다. 내 풀이 순서는,1. 지문에서 제시한 방법대로 정렬을 진행한다.2. 정렬된 일정을 순회하며 겹치는 일정 개수를 저장해주기 위한 배열(chart)에 해당 일정을 저장하였다.3. chart 배열을 순회하며    3-1. 배열의 값이 0인 경우 : 코팅지를 더이상 붙일 필요가 없으므로 코팅지의 넓이를 계산해 더해준다.    3-2. 배열..

https://www.acmicpc.net/problem/31797 난이도 : 실버 4 알고리즘 유형 : 큐 풀이 시간 : 14분 문제 풀이 입력을 받고, n번째가 될 때까지 첫 번째 값을 맨 마지막으로 보내주는 과정의 반복이다.H의 최대 길이가 10000이었기 때문에, 배열에 해당 사람의 번호를 저장해 줘도 괜찮을 것이라 생각하였다. 내가 풀이한 방법은1. 입력을 받아 손의 위치(배열의 idx 번호)에 해당하는 사람의 번호를 저장하였다.2. 손의 위치 배열을 순회하며 해당 사람의 번호가 존재한다면, queue에 순차적으로 push 하였다.3. n번만큼 queue를 돌며 맨 앞 녀석을 마지막으로 업데이트 시켜주었다.4. 최종적으로 큐의 맨 마지막 인자에 해당하는 사람 번호를 출력 코드/*아~파트 아파트!..