Samsung SDS 2022 동계 알고리즘 특강 회고

1. 모집 같이 공부하시는 영운님(@yeongun)의 추천으로 특강에 지원하게 되었다. 사실 SDS 프로 시험을 보고 삼성에 입사를 하기 위한 목적이 아닌, 순수하게 '대기업 알고리즘 특강이 얼마나 재밌고 퀄리티가 높을까?' 에 대한 호기심으로 지원하게 되었다. 2. 사전테스트 (코딩테스트) 총 6문제를 받는다. 다른 일반적인 코딩테스트와 달리 기간을 넉넉하게 주고, 지원자가 원하는 시간에 한 문제를 클릭해서 테스트에 응시하면, 해당 문제의 시간이 count되는 형식이었다. 응시자가 원하는 시간대에 한 문제씩 응시할 수 있다는 점에서 다른 코딩테스트와는 느낌이 달랐다. 문제의 제한시간은 없었지만, 또 그만큼 오래걸리면 안된다는 부담감이 있었기에 한 문제, 한 문제 집중해서 응시했다. 어떤 문제들이 출제됐..

[취미생활] 드럼 첫 녹화 영상 ! 곡 '시작' - 가호

2021년 7월 27일에 시작한 드럼 !! ~ 단순히 스트레스 해소와 악기를 다뤄보고 싶다는 욕심에 시작하게 되었다 무작정 괜찮은 드럼 학원을 알아보기 시작했고 다니는 헬스장 근처 DrumBox 라는 학원에 다니기 시작했다. (링크는 맨밑에) 일주일에 한 번 1시간씩 수업을 들었고 전자 드럼이 아닌 쌩 드럼을 칠 수 있어서 좋았다 7월부터 기록한 사진 (동영상도 많지만,,, 생략) 너의 의미, 옥탑방, Butter, Dynamite, 날아, 시작, 붉은노을 지금 까지 연습한 곡들이다. ! 너의의미, 옥탑방 까지는 빠르게 진도를 나갔지만 Butter, Dynamite 부터 어렵기 시작한 것 같다 ! 이제 대부분의 곡들이 1달 이상이 걸리는 연습을 하고 있는데 ㅠㅠ 평소의 연습 부족이라 이렇게 걸리면서도 버..

[Java] BaekJoon 3678. 성냥개비 (골드2) (DP)

문제출처: https://www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net 문제이해 목표 성냥개비의 개수가 주어졌을 때, 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 큰 수를 찾는 프로그램을 작성하시오. 주의: 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. 풀이 1. 주어진 성냥개비를 모두 사용해 만들 수 있는 작은 수 구하기 결론: DP로 풀이한다. dp[] 배열구조: dp[시작0,1][남은 자릿수][남은 성냥개수] 왜 첫번째 배열을 ..

[Java] BaekJoon 1725. 히스토그램, BaekJoon 6549. 히스토그램에서 가장 큰 직사각형(모노톤스택)

히스토그램 문제출처: https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net 문제이해 목표 주어진 히스토그램에 대해, 위그림처럼 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하시오. 풀이 정답 도출 매커니즘 이해 현재 인덱스(now) 기준으로 - 왼쪽에서 자신과 제일 가까우면서 작은 높이의 인덱스 번호 (left[now]) - 오른쪽에서 자신과 제일 가까우면서 작은 높이의 인덱스 번호 (right[now]) - righ..

[Java] BaekJoon 14226. 이모티콘 (BFS) (골드5)

문제출처: https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 문제이해 목표 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다. (2 DP와 BFS로 풀이 (탐색 우선 순위는 해당 이모티콘을 출력하기까지 Price(시간)가 낮은 순서대로) min[]: 최소 걸리는 시간을 다루는 배열 인덱스: i개의 이모티콘, 값: i개의 이모티콘을 만드는데 걸리는 시간의 최솟값 1. 증식 방법 - 자기보다 1 적은 이모티콘으로 탐색 -> min..

[Java] BaekJoon 3197. 백조의호수(BFS) (플레5)

문제출처: https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 문제이해 목표 2마리의 백조가 호수에서 살고 있다. 이 둘을 만나게 해주자 ! - map에는 빙판과 물이 존재한다. - 백조는 물 위로 밖에 다닐 수 없다. - 물을 끼고 있는 빙판은 하루가 지나면 녹아 물이 된다. 며칠이 지나여 백조들이 만날 수 있는지 계산해보자 ! 풀이 2개의 BFS 진행이 필요하다 !! [1] 백조1을 기준으로 BFS(백조2를 찾기위한..

[Java] BaekJoon 2696 중앙값 구하기 (골드2) (힙에 대한 이해)

문제출처: https://www.acmicpc.net/problem/2696 2696번: 중앙값 구하기 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주 www.acmicpc.net 문제이해 목표 어떤 수열을 읽고, 홀수번째 수를 읽을 때 마다, 지금까지 입력받은 값의 중앙값을 출력하는 프로그램을 작성하시오. 풀이 흐름 Queue 2개를 만든다. 비교적 작은 수들이 모여있는 leftQueue -> 내림차순 정렬 (큰 수 먼저 나오게) 비교적 큰 수들이 모여 있는 rightQueue -> 오름차순 정렬 (작은 수 먼저 나오게) 핵심은 홀 ..

[Java] BaekJoon 2579. 계단오르기 (DP) (실버3)

문제출처: https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제이해 목표 각 계단에는 점수가 있고, 계단을 오른다. - 최대 점수 획득이 목표 조건 - 연속된 세 개의 계단을 밟아서는 안된다. - 계단은 한계단을 오르거나 뛰어 넘을 수 있다. - 마지막 도착 계단은 반드시 밟아야한다. 풀이 1. 조건이 연속된 세 개의 계단이므로 (처음의 첫 3계단은 예외처리 하거나 데이터 읽어놓기) 2. arr[ i ] => i번째의 계단 점수 DP[ i ] => i번째까..