출저 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV140YnqAIECFAYD "Complete Binary Tree를 배열로 구현하고 탐색" 이 문제는 Complete Binary (완전 이진트리라고함.. full , complete, perfect 등에 번역이 헷갈려 영어로 기억함.) 의 중위 순회를 구현하는 문제이다. Complete binary tree 는 배열로 구현가능하며, 배열 안에서 인덱스로 특정 노드의 부모, 자식 위치를 구할 수 있다. 아래와 같다. 노드 i의 부모 : (i-1) /2 노드 i의 왼쪽 자식 : (2*i) +1노드 i의 오른쪽 자식 : (2*i) +2 참 쉽쥬? 그리고 중위 ..
출저 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15PTkqAPYCFAYD"트리 구현" 트리를 구현하면된다. Complete Binary Tree 였다면 모두 배열에 넣고 좀더 쉽게 구할수 있었겠지만, 그냥 이진트리여서 그러지 못하고 트리를 구현했다. 대신 부모로 가는 경로를 쉽게 구하고자 해당 노드의 left, right 이외에 parent 변수도 함께 넣어줬다. 그렇게 한 후, A와 B의 공통 조상을 구하기 위해 A와 B의 조상을 번갈아가면서 찾으며 마킹을 했다. 이미 누군가가 지나간 노드의 경우 공통 조상이 되므로, 그 공통 조상을 구했고, 그 하위부터 다시 재귀적으로 공통 조상의 자식들을 l,r ..
출저 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu "조합" 해당 문제는 어떤 row를 고를 것인지가 중요하다. 그리고 탐색한 결과를 모든 열이 k 개 연속된 숫자가 있는지 검사하는 것을 구현하는 것이 키포인트이다. 어떤 row를 고를 것인가는 조합과 같다. 바꾸는 row의 개수를 최소로 하는 값을 찾으면 되므로, 아래의 경우를 탐색한다. 그리고 만족하는 값을 찾았다면 결과 출력. 모두 바꾸지 않는 것 ~모든 행을 다 바꾸는 것 여기서 특정 row를 1 혹은 0 으로 바꾼 후에는 원래 상태로 복구 시켜주는 것이 필요하다. 마치 백트래킹 처럼.. 따라서 선택한 row를 0 혹은 1로..
출저 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4yC3pqCegDFAUx "와 어려웠다.인수분해" 처음엔 0~9 까지 숫자를 눌러 X를 구하려고 했다. 굉장히 구현이 잘 되지 않았다. 1 = 11*1 = 11*1*1 = 1 이런 경우 어떻게 처리할까.. 그래서. 약간의 기초적인 수학적인 지식이 필요했다. 어떤 수들을 곱해서 X가 만들어 졌고, X를 계속 인수분해 하다보면 계산기를 눌러 가능한 a * b *.. *... * 의 형태로 나올 것이다.. 따라서 해당 문제에서는 주어진 X값을 인수분해 하여 해당 a * b 의 형태로 바꾼 후에, a와 b를 계산기로 칠 수 있는지 확인하고, 그렇지 않다면 다시 ..
출저 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIseXoKEUcDFAWN&categoryId=AWIseXoKEUcDFAWN&categoryType=CODE "그리디" 당연히 좀 더 큰 금액을 할인 받는것이 전체 금액이 최소가 된다. 따라서 주어진 가격을 내림차순 정렬하여 세 개 상품씩 그룹을 지어 가장 작은 가격을 더해 총 할인액을 구하는 것이 할인이 최대인것. 그리디. 내림차순 정렬하고 선택한다. 123456789101112131415161718192021222324252627282930313233343536373839404142import java.io.BufferedReader;import jav..
출저 : https://www.acmicpc.net/problem/2026 "DFS 문제를 잘 읽어야함..." 문제를 잘 안 읽어서 계속 틀렸음. 문제를 잘 읽어 보면 선택된 K명의 모든 애들이 다 친구여야 함. 최초에 1-3-2-4 의 관계가 되면 나는 1,2,3,4 모두 답으로 출력했음. 이거 빼고는 그냥 DFS 문제. 따라서 아래 68~ 73 라인을 추가했음. 팁으로 경로를 찍을 때는 list 보다는 아래와 같이 result 배열 하나만을 생성해 이를 이용해 경로를 찍는 것이 더 좋다고 생각됨. 또 하나, 전부 친구인지 아닌지 판별하는 부분에서 boolean 변수를 사용할 수도 있지만 이미 생성된 j를 가지고 끝까지 돌았는지 j == index 인지 판별하면 변수 생성을 하나 줄일수 있으미.. 12..
출저 : https://www.acmicpc.net/problem/1389 "다익스트라,BFS,DFS 다~~" 다익스트라를 연습할 수 있는 좋은 문제 인 듯, 일단 다익스트라는 BFS를 활용해 시작지점으로부터 연결된 모든 노드로 가는 최소값을 찾는 알고리즘이다. ( 단, 다익스트라는 가중치가 각각 다른 경우에 유용하며, 이 문제에서는 가중치가 1이므로 그냥 BFS 혹은 DFS 탐색하면됨...) 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869import java.io.BufferedReader;import java.io.IO..
출저 : https://www.acmicpc.net/problem/2583 "BFS" 영역을 나 누 자 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Collections;import java.util.LinkedList..
출저 : https://www.acmicpc.net/problem/2234 "BFS 그리고 비트마스킹(필수는아님..)" 비트마스킹을 사용하지 않고도 0 ~ 15 까지의 숫자별로 가능한 방향을 이차원 배열로 정의해줘서 풀면됨... 하지만 아래 풀이는 비트마스킹 써씅ㅁ. solve1()을 통해 아래 두개의 답을 구할 수 있다. 1. BFS를 돈다.2. 1번 BFS를 돌면서 각 방의 size가 구해지므로 최대값을 비교해 구한다. 마지막 문제에 대한 답을 구하는게 관건인듯 하다. 나는 1,2 번을 구하면서 새로운 int[][] arr 을 정의해서 이곳에 0~ 방의 개수 까지 카운터를 마킹했다.(영역 나누기 처럼) 동시에 각 index마다 방의 크기를 ArrayList에 저장해두었다. 그 후에 새로 정의한 맵 a..
출저 : https://www.acmicpc.net/problem/1463 "DP DP 딥" 1을 가지고 N을 만든다고 역으로 생각하자. dp[3] 까지 최소값을 구한다. 1이 되겠다. 그 이후에 4를 만드려면 어떤 방법이 있을까? 2 에서 2를 곱하거나 3에서 더하기 1을 하거나. dp[n/2] + 1 ( n % 2 == 0 )dp[n] = dp[n/3] + 1 ( n % 3 == 0 ) dp[n-1] 이중에 최소값을 dp[n]으로 한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344import java.util.Scanner; public class Main { static int n; static int..
- Total
- Today
- Yesterday