Dino Rudy

NextPermutation 함수란? NextPermutation은 말 그대로 다음 순열을 알아내는 함수입니다. 이때 다음 순열이란 사전 순으로 순열을 정렬했을 때 사전적으로 바로 다음번에 오는 순열이라는 뜻이죠 N개의 원소(원소 1~N)를 갖는 순열은 기본적으로 N! 개가 있습니다. 예를 들어 1,2,3의 순열은 사전 순으로 1,2,3 1,3,2 2,1,3 -이놈의 np? 2,3,1 -요놈 3,2,1 로 3! -> 6개 만약 2,1,3 다음의 순열을 알고 싶다! 이때 사용하는 게 nextPermutation입니다. 2,1,3의 다음 순열은 2,3,1이죠 다른 말로 하면 A라는 순열의 다음 순열 B는 사전적으로 A 바로 다음에 오는 순열입니다. 그렇다면 마지막 순열인 3,2,1의 다음 순열은? 없습니다...

알고리즘 스터디 16주 차 지난 10월 24일 일요일에는 삼성전자 코딩 테스트를 보고 왔습니다. 가벼운 마음으로 응시하러 갔었지만 그래도 백준에서 삼성전자 기출문제집을 풀면서 10문제 중 8~9문제는 시간 내에 잘 풀어서 내심 기대하기도 했었지만 코딩 테스트를 보고 아직 실력이 부족하다는 생각이 들었습니다. 시험은 오후였고 2 문제가 나왔는데 백준 사이트 기준으로는 골드1 두 문제가 나왔습니다. (기존에 기출 문제 중 골드1 한 문제와 플레5 한 문제가 가장 어려운 문제였습니다.) 보통 어려운(골드1~2) 문제 1개와 보통(골드3~4) 이나 쉬운 문제(골드 5이하) 1개로 총 2문제 정도 나온다고 예상했었는데 예상을 뒤엎고 어려운 문제가 2 문제가 나왔습니다. 이번은 한 문제만 풀어도 무조건 합격일 것 ..

알고리즘 스터디 14주 차 이번에 삼성전자에 sw직군으로 서류를 제출했었는데 서류 합격을 하여 금주 24일 일요일에 코딩 테스트를 보러 가게 되었습니다. 이번 주는 스프링을 배우기 시작하여 알고리즘에 시간을 많이 투자하지는 못했지만 삼성 코딩 테스트를 준비하기 위해 백준 사이트에서 삼성 SW 역량 테스트 기출문제집에 수록된 문제들을 위주로 하루에 1문제에서 2문제 정도 풀고 있습니다. 문제집에 수록된 문제가 총 41문제인데 지금 현재 25문제를 풀었고 아직 16문제가 남았습니다. 서류가 통과될 줄 알았으면 좀 더 빨리 삼성 기출문제를 위주로 풀었을 텐데 하는 아쉬움이 남지만 그래도 꾸준히 다른 문제들을 풀어왔기 때문에 일요일에는 가벼운 마음으로 코딩 테스트를 보러 가려고 합니다. 싸피 1학기가 거의 다 ..

알고리즘 스터디 12주 차 요즘 알고리즘을 풀다 보면 익숙한 유형들이 많이 눈에 들어옵니다. 어려운 문제라고 해도 익숙한 유형들이 합쳐져 있는 경우는 시간은 오래 걸리지만 그래도 제법 잘 풀어내고 있다고 생각합니다. 하지만 잘 풀고 있다는 생각이 들수록 다른 사람의 코드를 잘 안 보게 되는 건 안 좋은 일인 것 같습니다. 자만은 아니지만 익숙한 유형의 문제를 풀고 어느 정도 효율성이 나온다고 생각하면 제가 푼 방식이 옳다고 여기며 다른 사람들의 다른 풀이를 참고하지 않으려고 하는 것 같습니다. 한 문제 한 문제 푸는 것도 오래 걸리다 보니 문제를 풀면 기쁘지만 리뷰를 하고 정리를 하는 여유가 없어진 것 같습니다. 어렵게 푼 문제일수록 리뷰하고 정리해야 하는데 요즘 문제 풀기에만 급급한 것 같은 제가 보이..

알고리즘 스터디 11주 차 이번 주에는 알고리즘 월말평가가 있어서 DP knapsack 알고리즘에 대해 스터디원들과 복습을 하였고 월말 평가 후 HashMap사용에 대한 이야기가 있어 HashMap 이론과 사용 방법에 대해 공부를 진행하였습니다. 곧 알고리즘 커리큘럼이 끝나기 때문에 알고리즘 복습을 꾸준히 하기 위해서 매주 수, 금은 알고리즘 이론 공부 매주 화,목은 알고리즘 문제를 푸는 날로 방향을 정했습니다. 또한 매일 화,목에 문제를 리뷰하기 전에 당일에 문제를 알려줬었는데 과제를 하고 보충을 듣다 보면 시간이 많이 부족한 스터디원들도 있어 이번주 부터는 다음 주에 풀어야 할 문제를 미리 금요일에 알려 줄 생각입니다. 알고리즘 커리큘럼이 끝나고 백엔드 커리큘럼을 시작하게 되면 알고리즘 문제를 많이 ..

알고리즘 스터디 1 차 알고리즘 스터디가 어느덧 10주 차가 되었습니다. 7월 21일부터 9월 22일까지(9주) 약 2달이 지났는데 현재는 웹엑스를 통해 매주 수요일 금요일마다 알고리즘 이론 공부를 하고 있습니다. 지금까지 알고리즘 공부를 하면서 코딩테스트에 나오는 대부분의 알고리즘을 배웠지만 카카오코딩 테스트를 보고 아직 실력이 많이 부족하다는 것을 느꼈습니다. 하지만 2달 전의 제 알고리즘 실력에 비하면 많은 향상이 있었다고 생각합니다. 개념조차 정확하게 몰랐던 프림, 크루스 칼, 다익스트라 , 플로이드 워셜 등의 알고리즘도 개념도 배우고 복습하며 익혀나가고 있습니다. 더 나아가 공간, 시간 복잡도를 줄이는 방법들도 차근차근 문제를 통해 익혀가고 있습니다. 동일한 시간과 메모리라는 자원으로 효율적인 ..

Union-Find란? Union-Find는 서로소 집합을 표현할 수 있는 자료구조로 크게 Union과 Find라는 2가지 연산으로 이루어져 있어 Union-Find라고 불립니다. Union-Find를 구현 위해서는 union이라는 연산과 find라는 연산에 대해 이해할 수 있어야 합니다. Find 연산의 개념 find 연산의 목적은 어떤 원소가 어떤 집합에 속하여 있는지 알아내는 연산입니다. 예를 들어 a, b, c, d라는 각각의 원소가 있다고 가정할 때 해당 원소가 어떤 집합에 속하여 있는지 알아내는 연산으로 find(a), find(b) 등을 통하여 해당 원소가 어떤 집합인지 알 수 있어야 합니다. find 연산을 구현하기 위해서는 해당 원소들이 어떤 집합에 포함되어 있는지 알 수 있는 자료구조(..

치즈 2636번 solved.ac 골드 5 https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 문제 해석 및 풀이 이 문제는 공기 중에 노출된 치즈가 몇 시간 뒤에 완전히 녹는지와 완전히 녹기 직전 단계에서 몇 개의 치즈가 남았는지를 구하는 문제입니다. 문제의 조건에서 가장 테두리 부분은 치즈가 놓여있지 않고 공기가 있는 부분입니다. 이 문제에서는 시간마다 없어지는 치즈를 구해 그 치즈를 없애야 합니다. 이 문제를 접근하기 위해서는 공기에 노출된 치즈를 알아야 하는데..

평범한 배낭 12865번 solved.ac 골드 5 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 문제 해석 및 풀이 이 문제는 zero-one knapsack 문제로 knapsack문제는 Dynamic Programming 알고리즘을 배울 때 대표적으로 등장하는 문제입니다. knapsack문제는 배낭에 주어진 무게를 넘지 않는 선에서 최대의 만족도를 갖는 문제를 구하는 문제인..