취업 준비 및 일상

개념 V개의 점이 있는 그래프에서, 최단 거리를 찾는 알고리즘 for문을 3번 돌면서, dist[i][j]를 'i번째 점부터 j번째 점까지 곧바로 가는 최솟값, 곧바로 or 1번 점을 거치거나 거치지 않으면서 가는 최솟값, 곧바로 or 1번 점을 거치거나 거치지 않으면서 or 2번 점을 거치거나 거치지 않는 최솟값, ... , 곧바로 or 1번 점을 ... or V번 점을 거치거나 거치지 않으면서 가는 최솟값'을 구하는 알고리즘이다. 일반적으로 DP랑 따로 배우긴 하나(그래프 최단거리 알고리즘 배울 때 묶어서 배우...지?), DP 알고리즘이다. Time Complexity: 점의 개수 V에 대하여 for문 3번 돌기 떄문에 O(V^3) 음의 간선이 있어도 가능하나, 음의 사이클이 있으면 불가능 (음의 ..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데,..

https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄..

Intro 안녕하세요, 주어진 문제를 해결하는데 몰입하는 개발자, 박윤진입니다. 꾸준히 노력하여 성취하며 성장하고자 합니다. Educations 2010.03 - 2013.02 잠실중학교 졸업 2013.02 - 2015.02 한성과학고등학교 조기졸업 2015.03 - 2022.02 서울대학교 수학교육과 졸업 2022.01 - 2022.06 SSAFY 7기 1학기 과정 수료 Achievements 2012년 고려대학교 전국수학학력인증시험 대상 2015년 2학기 청관장학회 장학생 선정 2016년 1학기 성적우수(우등) 장학생 선정 2016년 2학기 성적우수(우등) 장학생 선정 2019년 1학기 성적우수 장학생 선정 2020년 2학기 천재교육재단 장학생 선정 `22년 현대모비스 알고리즘 경진대회: 본선 진출(..

https://www.acmicpc.net/problem/5373 5373번: 큐빙 각 테스트 케이스에 대해서 큐브를 모두 돌린 후의 윗 면의 색상을 출력한다. 첫 번째 줄에는 뒷 면과 접하는 칸의 색을 출력하고, 두 번째, 세 번째 줄은 순서대로 출력하면 된다. 흰색은 w, 노란 www.acmicpc.net 문제 루빅스 큐브는 삼차원 퍼즐이다. 보통 루빅스 큐브는 3×3×3개의 작은 정육면체로 이루어져 있다. 퍼즐을 풀려면 각 면에 있는 아홉 개의 작은 정육면체의 색이 동일해야 한다. 큐브는 각 면을 양방향으로 90도 만큼 돌릴 수 있도록 만들어져 있다. 회전이 마친 이후에는, 다른 면을 돌릴 수 있다. 이렇게 큐브의 서로 다른 면을 돌리다 보면, 색을 섞을 수 있다. 이 문제에서는 루빅스 큐브가 모두..

https://solved.ac/event/220401 solved.ac 알고리즘 문제해결 학습의 이정표 🚩 Baekjoon Online Judge 난이도 및 티어 정보 제공 solved.ac 솔브닥에서 만우절이라고 메이플 스타포스 강화 시스템을 그대로 베낀 이벤트를 냈다. 가장 필요한 기능이라고 한다면, '현재 별조각이 piece개 있는데, target성까지 갈 확률이 얼마일까?라고 생각하여 해당 연산을 구현하였다. 순수한 브루트포스 노가다. 코드 public class 한별포스 { public static void main(String[] args) { starforce(10000, 23); // (가지고 있는 별조각 개수, 목표) } static void starforce(int piece, int..

바킹독 선생님은 CP를 위주로 공부했으면서도 강의 및 연습문제는 일반적인 취준생이 준비하는 코딩테스트 수준에 맞춰서 구성한다. 그래서 그런지, DP 문제집도 어려운 DP 대신 기본적인 DP 문제 위주로 구성되어 있다. 풀고나서 느낀점. 1. 쉬운 DP는 왠만하면 점화식을 피보나치 문제와 같은 방식으로 일차원 DP로 쉽게 구할 수 있다. 피보나치 관련 문제는 물론이며, '이친수', '파도반 수열', '01타일'과 같은 문제는 현재 항과 이전 항들간의 관계만 생각하면 식이 금세 나온다. 2. 그러나 조금만 어려워지면 (골드5 이상) 유형이 다양해지며, 발상도 문제마다 다르다. 나는 '자두나무', '타일 채우기'는 스스로 생각하여 풀었지만, '내리막길', '색상환'은 또 못 풀었다. 나는 소위 '양치기' 신봉..

https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 색을 표현하는 기본 요소를 이용하여 표시할 수 있는 모든 색 중에서 대표적인 색을 고리 모양으로 연결하여 나타낸 것을 색상환이라고 한다. 미국의 화가 먼셀(Munsell)이 교육용으로 고안한 20색상환이 널리 알려져 있다. 아래 그림은 먼셀의 20색상환을 보여준다. 그림 1. 먼셀의 20색상환 색상환에서 인접한 두 색은 비슷하여 언뜻 보면 구별하기 어렵다. 위 그림의 20색상환에서 다홍은 빨강과 인접하고 또 주황과..

문제 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다. 지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오. 입력 첫..

https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 문제 명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다. 먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다. 각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다. 예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자...