참여하고 있는 알고리듬 스터디에서 이 주제로 발표를 했었는데,반응이 괜찮아서 여기에도 포스팅한다. 다들 15분 내로 유니온 파인드 알고리듬을 터득하게 해주겠다.  유니온 파인드가 뭐냐  먼저, 위 그림처럼 1부터 6까지의 개별 집합에 속한 각각의 노드들이 있다고 가정해보자.개별적인 집합이므로 해당 집합의 루트 노드는 자기 자신인 상태로 볼 수 있다.    여기서 1-2-3 노드끼리 연결하고, 5-6 노드끼리 연결해서 총 세 개 집합으로 분리한다면?    상태는 이렇게 변하게 될 것이다.지금 묶인 방향으로 보면 2번은 1번에 묶이고, 3번은 2번에 묶였으니,1-2-3이 속한 집합에서 루트는 1이 될 것이다. 마찬가지로 4가 속한 집합은 여전히 4뿐이니 4가 루트인 집합이 되고,5-6이 속한 집합은 6번 노..

요즘 백엔드 직군 코딩 테스트를 Java로만 제한하는 트렌드로 변하기 시작했다.그래~ 개발도 그렇고, 과제 테스트도 그렇고, 이제 Java도 C처럼 편하게 다루려면 풀긴 해야지 그래서 오늘부터 Java로 첫 ps 도전~  문제 내용1 ~ n의 번호가 있는 택배 상자가 창고에 있습니다. 당신은 택배 상자들을 다음과 같이 정리했습니다. 왼쪽에서 오른쪽으로 가면서 1번 상자부터 번호 순서대로 택배 상자를 한 개씩 놓습니다. 가로로 택배 상자를 w개 놓았다면 이번에는 오른쪽에서 왼쪽으로 가면서 그 위층에 택배 상자를 한 개씩 놓습니다. 그 층에 상자를 w개 놓아 가장 왼쪽으로 돌아왔다면 또다시 왼쪽에서 오른쪽으로 가면서 그 위층에 상자를 놓습니다. 이러한 방식으로 n개의 택배 상자를 모두 놓을 때까지 한 층에 ..

내용 새로 업데이트 예정 (~25년 상반기)

문제 문제링크: https://www.noj.am/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 문제 분석 동굴 내부에 도둑 루피들만이 쫙 깔려있는 상황이다. 어차피 잃을 수밖에 없지만 기왕 이렇게 된 거, 최대한 덜 잃게 가보자는 것이다. 자세한 풀이 DP로 풀어야겠다고 생각해서 오케이, 최소로 만들면서 내려가보자고~ 위쪽, 왼쪽 중 최소인 것만을 선택해 합해주는 로직을 만들었따 #include using namespace std; int N; int cnt=1; int boar..

문제문제 링크: https://www.noj.am/25945 25945번: 컨테이너 재배치항구의 컨테이너 하치장 바닥에는 컨테이너를 쌓을 수 있는 칸이 일렬로 총 $n$개가 그려져 있고, 현재 하치장에는 총 $m$개의 컨테이너가 쌓여 있다. 개별 컨테이너의 높이는 모두 $1$로 동일하며www.acmicpc.net  문제 분석요약하면, 컨테이너들이 칸마다 잔뜩 있는데높이 차이가 거의 안 나도록 만들고 싶다는 것이다. 근데, 난 컨테이너고 나발이고그냥 '땅 메우기'라고 생각하기로 했다.부족한 부분은 메워주고, 많은 부분은 빼주면 끝 아닌가? 컨테이너들을 모두 합해 칸 수 N으로 나누면 평균 층을 구할 수 있다. 모든 컨테이너들을 고르게 분포시키면,무조건 평균 층과 같거나 평균 층보다 위에 있을 수밖에 없다...

문제 문제링크: https://www.noj.am/1063 1063번: 킹 8*8크기의 체스판에 왕이 하나 있다. 킹의 현재 위치가 주어진다. 체스판에서 말의 위치는 다음과 같이 주어진다. 알파벳 하나와 숫자 하나로 이루어져 있는데, 알파벳은 열을 상징하고, 숫자는 www.acmicpc.net 문제 분석 이 문제를 풀기위해서 체스? 몰라도 된다. 그냥 상하좌우대각 8방향으로 1칸씩 움직이는 게 끝이니까 킹을 움직여주는 게 끝인 간단한 문제인데, 여기서 킹받는 포인트는 돌이랑 겹칠 때, 그리고 체스판 밖으로 나갈 때를 고려해줘야 한다는 것이다. 근데 생각해보면 그것도 간단하다 사실 별로 킹 안 받음 겹칠 때의 상황도 문제에서 아주 잘 보여주고 있잖아 필요한 것 목록. 1. 킹과 돌의 x, y좌표 (행/열)..

문제문제 링크: https://noj.am/2630 2630번: 색종이 만들기첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다.www.acmicpc.net 문제 분석제목이 색종이 만들기? 색종이로 무언가를 만든다는 건가?아니면 색종이 그 자체를 만든다는 걸까? 색종이로 뭘 만들긴 개뿔을 만들어 읽어보니깐 그냥 큰 종이를 작은 종이들로 나누는 거였다글도 길고, 무슨 표같은 것도 있지만 쉽고 간단하게 알려주겠다. 우선 색도 두 개밖에 없으니 색종이는 무슨, 그냥 타일이라 생각하자. 그리고 지금 당신은 부모님한테 혼나는 중이다.시선은 바닥을 보면..

문제문제링크: https://www.noj.am/12789 12789번: 도키도키 간식드리미인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두www.acmicpc.net  문제 분석 잡설이 구구절절 길어서 그렇지 막상 읽어보면입력 값들을 순서대로 나열할 수 있으면 Nice, 아니면 Sad를 출력하라는 간단한 내용이다. 이렇게 시험기간 격려 간식 이벤트에 학생들이 마구 줄을 선 상황.T자형 공간을 활용해 배부받은 표의 숫자순으로 학생들을 보내야한다 심지어 그림도 아주 직관적이다필요한 것 목록.1. 순서를 알려주는 변수.2. 아직 차례가 아닌 수들을 담았다가, 차례가 되면 뺄 ..