티스토리

IT 개발 돼지의 일상

검색하기

블로그 홈

IT 개발 돼지의 일상

jaejin89.tistory.com/m

돼지개발자 님의 블로그입니다.

구독자: 0

방명록 방문하기

주요 글 목록

백준 1231. 중위 순회 :: 돼지개발자 출저 : 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 참 쉽쥬? 그리고 중위 .. 공감수 1 댓글수 0 2019. 2. 14.
SWEA 1248. 공통조상 :: 돼지개발자 출저 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15PTkqAPYCFAYD"트리 구현" 트리를 구현하면된다. Complete Binary Tree 였다면 모두 배열에 넣고 좀더 쉽게 구할수 있었겠지만, 그냥 이진트리여서 그러지 못하고 트리를 구현했다. 대신 부모로 가는 경로를 쉽게 구하고자 해당 노드의 left, right 이외에 parent 변수도 함께 넣어줬다. 그렇게 한 후, A와 B의 공통 조상을 구하기 위해 A와 B의 조상을 번갈아가면서 찾으며 마킹을 했다. 이미 누군가가 지나간 노드의 경우 공통 조상이 되므로, 그 공통 조상을 구했고, 그 하위부터 다시 재귀적으로 공통 조상의 자식들을 l,r .. 공감수 0 댓글수 0 2019. 2. 14.
SWEA 2112. 보호 필름 :: 돼지개발자 출저 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu "조합" 해당 문제는 어떤 row를 고를 것인지가 중요하다. 그리고 탐색한 결과를 모든 열이 k 개 연속된 숫자가 있는지 검사하는 것을 구현하는 것이 키포인트이다. 어떤 row를 고를 것인가는 조합과 같다. 바꾸는 row의 개수를 최소로 하는 값을 찾으면 되므로, 아래의 경우를 탐색한다. 그리고 만족하는 값을 찾았다면 결과 출력. 모두 바꾸지 않는 것 ~모든 행을 다 바꾸는 것 여기서 특정 row를 1 혹은 0 으로 바꾼 후에는 원래 상태로 복구 시켜주는 것이 필요하다. 마치 백트래킹 처럼.. 따라서 선택한 row를 0 혹은 1로.. 공감수 0 댓글수 0 2019. 2. 14.
SWEA 1808. 지희의 고장난 계산기 :: 돼지개발자 출저 : 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를 계산기로 칠 수 있는지 확인하고, 그렇지 않다면 다시 .. 공감수 0 댓글수 1 2019. 2. 12.
SWEA 4050. 재관이의 대량 할인 :: 돼지개발자 출저 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIseXoKEUcDFAWN&categoryId=AWIseXoKEUcDFAWN&categoryType=CODE "그리디" 당연히 좀 더 큰 금액을 할인 받는것이 전체 금액이 최소가 된다. 따라서 주어진 가격을 내림차순 정렬하여 세 개 상품씩 그룹을 지어 가장 작은 가격을 더해 총 할인액을 구하는 것이 할인이 최대인것. 그리디. 내림차순 정렬하고 선택한다. 123456789101112131415161718192021222324252627282930313233343536373839404142import java.io.BufferedReader;import jav.. 공감수 0 댓글수 0 2019. 2. 10.
백준 2026. 소풍 :: 돼지개발자 출저 : 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.. 공감수 0 댓글수 0 2019. 2. 8.
백준 1389. 케빈 베이컨의 6단계 법칙 :: 돼지개발자 출저 : https://www.acmicpc.net/problem/1389 "다익스트라,BFS,DFS 다~~" 다익스트라를 연습할 수 있는 좋은 문제 인 듯, 일단 다익스트라는 BFS를 활용해 시작지점으로부터 연결된 모든 노드로 가는 최소값을 찾는 알고리즘이다. ( 단, 다익스트라는 가중치가 각각 다른 경우에 유용하며, 이 문제에서는 가중치가 1이므로 그냥 BFS 혹은 DFS 탐색하면됨...) 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869import java.io.BufferedReader;import java.io.IO.. 공감수 0 댓글수 0 2019. 2. 7.
백준 2583. 영역 구하기 :: 돼지개발자 출저 : 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.. 공감수 0 댓글수 0 2019. 2. 7.
백준 2234. 성곽 :: 돼지개발자 출저 : https://www.acmicpc.net/problem/2234 "BFS 그리고 비트마스킹(필수는아님..)" 비트마스킹을 사용하지 않고도 0 ~ 15 까지의 숫자별로 가능한 방향을 이차원 배열로 정의해줘서 풀면됨... 하지만 아래 풀이는 비트마스킹 써씅ㅁ. solve1()을 통해 아래 두개의 답을 구할 수 있다. 1. BFS를 돈다.2. 1번 BFS를 돌면서 각 방의 size가 구해지므로 최대값을 비교해 구한다. 마지막 문제에 대한 답을 구하는게 관건인듯 하다. 나는 1,2 번을 구하면서 새로운 int[][] arr 을 정의해서 이곳에 0~ 방의 개수 까지 카운터를 마킹했다.(영역 나누기 처럼) 동시에 각 index마다 방의 크기를 ArrayList에 저장해두었다. 그 후에 새로 정의한 맵 a.. 공감수 0 댓글수 0 2019. 2. 7.
백준 1463. 1로 만들기 :: 돼지개발자 출저 : 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.. 공감수 0 댓글수 0 2019. 2. 1.
백준 2579. 게단 오르기 :: 돼지개발자 출저 : https://www.acmicpc.net/problem/2579 "DP 쓸 때, dp값과 map에 값을 활용해보자.." 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader; public class Main { static int N; static int[] dp; static int[] map; public static void main(String[] args) throws IOException{ BufferedReader br = n.. 공감수 0 댓글수 0 2019. 2. 1.
백준 1149. RGB거리 :: 돼지개발자 출저 : https://www.acmicpc.net/problem/1149 "DP" 어려웠다. 기초적인 dp문제라고 했는데 왜 이리 어려웠지...ㅎㅎ dp[x] = dp[x-1] + min(x) ; 까지는 생각을 하고, 해답을 봤다. 그리고 최초 dp[0] 가 R,G,B 일 때를 모두 체크하기위해 dp[x][3] 배열을 만들어 해당 dp 값을 이용한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringToken.. 공감수 0 댓글수 0 2019. 2. 1.
백준 1003. 피보나치 함수 :: 돼지개발자 출저 : https://www.acmicpc.net/problem/1003 "DP" 12345678910111213141516171819202122232425262728293031323334353637import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader; public class Main { static int T,N; static int z, o; static int dp[][]; static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws IOException { BufferedReader b.. 공감수 0 댓글수 0 2019. 2. 1.
백준 15685. 드래곤 커브 :: 돼지개발자 출저 : https://www.acmicpc.net/problem/15685 "아이디어가 필요한 구현문제" 삼성 기출 문제. 각 세대를 더해 갈 수록 기존에 찍었던 선들을 모두 왼쪽으로 돌려서 다시 그려준다. 초기에 생각만 잘하면 쉽게 풀릴 문제 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Lis.. 공감수 0 댓글수 0 2019. 1. 31.
백준 1932. 정수 삼각형 :: 돼지개발자 출저 : https://www.acmicpc.net/problem/1932 "DP, bottom-up / DP라고 무조건 재귀 생각하지말자." 알고리즘은 삼각형의 맨 밑부분부터 시작해서 dp 갱신을 시작한다. 처음에 재귀로 구현했는데 시간초과가 났다. dp 값을 비교해서 기존 dp 값보다 작으면 탐색하지 못하게 하였는데??? 라고 생각했다. dp 값이 나중에 큰 값으로 갱신된다면, 이전 까지 탐색 경로들은 그냥 지나칠 거임.. 따라서 해당 지점에 가능한 가장 큰 값이 맨 나중에 갱신되는 데이터가 주어졌다면 아마 dp 값 비교를 통한 가지치기는 적용 안될듯. 1234567891011121314151617181920212223242526272829303132333435363738394041424344impo.. 공감수 0 댓글수 0 2019. 1. 31.
백준 10026. 적록색약 :: 돼지개발자 출저 : https://www.acmicpc.net/problem/10026 "BFS " Red를 Green 으로 바꾸고 같은 색상 끼리 BFS를 돌려 구역을 구한다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182import java.awt.Point;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import ja.. 공감수 0 댓글수 0 2019. 1. 31.
백준 15684. 사다리조작 :: 돼지개발자 출저 : https://www.acmicpc.net/problem/15684 "브루트포스" 기존에 있는 사다리에 가능한 가로축을 모두 탐색해보는 브루트 포스 문제이다. 그럼 사다리를 배열에 어떻게 표현할까? 풀이에서 배열에 1로 체크된 값은 해당 위치에서 오른쪽으로 사다리가 존재한다고 생각하는 것이다. 따라서 인접한 열에 1 이 있지 않도록 가능한 모든 경우를 체크한다. 이렇게 생각하고 실제 탐색할때는 내 위치와 내 왼쪽 위치를 탐색한다. 1. 내 위치에 1이 있다. 오른쪽 사다리로 가라.2. 내 왼쪽에 1이 있다. 왼쪽 사다리로 가라 위와같이 경우의 수를 만들고 실제로 사다리를 타봐서 체크한다.. 12345678910111213141516171819202122232425262728293031323334.. 공감수 1 댓글수 0 2019. 1. 31.
백준 15683. 감시 :: 돼지개발자 출저 : https://www.acmicpc.net/problem/15683 "구현, 브루트 포스" 아래와 같이 구현했다. 삼성 기출 문제. 특정 위치에 있는 CCTV가 종류별로 있는데, 이를 4방향으로 돌려가며 사각지대 0의 개수를 최소로 줄이는 경우를 찾는 것이다. 아래 풀이에서는 각 CCTV 마다 한 방향만을 설정해주었는데, 회전 가능한 4방향에 대해서 다 정의해 준다면, 2번 CCTV 는 2회, 5번 CCTV는 1회로 횟수를 더욱 줄일 수 있다. 근데 나는 귀찮아서 그냥 4방향 다 돌렸따.... 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616.. 공감수 0 댓글수 0 2019. 1. 30.
SWEA 3752. 가능한 시험 점수 :: 돼지개발자 출저 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWHPkqBqAEsDFAUn "구현... 다시보자! 꾸에에에엑" 다시보자... 왜 이런 생각을 못했을까. 처음에 그냥 브루트 포스로 전체 경우의 수를 재귀로 다 돌려보았다. 시간 초과. 풀이 참고해서 풀었따. 알고리즘은 아래와 같다. 1. 각 배점을 받을 때마다 최대값을 갱신한다.2. 갱신된 최대값 ~ 0 까지 탐색하며, 만약 이전에 이미 맞았던 점수가 있다면 이 점수에 내가 방금 입력받은 점수를 더해준 값도 체크한다.3. true 로 체크된 값들의 개수를 센다. 12345678910111213141516171819202122232425262728293031.. 공감수 0 댓글수 0 2019. 1. 29.
SWEA 1245. 균형점 :: 돼지개발자 출저 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15MeBKAOgCFAYD&categoryId=AV15MeBKAOgCFAYD&categoryType=CODE"이분 탐색 과 double.. 100~200 번만 돌리자." 이분 탐색을 통해 문제를 풀어야 한다. 근데 제한 없이 돌리다 보니 stackoverflow... 아래와 같은 게시물을 봄... 결론만 말하자면 double형을 가지고 이분 탐색을 할 경우 100~200 번 까지만 돌리도록 한다는 것이다. (https://www.acmicpc.net/blog/view/37) 1234567891011121314151617181920212223242526272.. 공감수 0 댓글수 0 2019. 1. 29.
백준 4920. 테트리스 게임 :: 돼지개발자 출저 : https://www.acmicpc.net/problem/4920 "전체 다해보자. 이상한 문제 trim() 주의." 브루트포스. 전체 다해보자. 삼성 기출의 테트로미노가 훨씬 깔끔한 문제... 이거는 좌표 지정 다 해줘야 한다. 좌표 지정할때는 정말 정신 차리고 해야 한다. 그리고 입력으로 주어지는 데이터에 공백이 많으므로 trim() 하여 공백 처리해줬다. 이런 류의 문제 일일히 좌표 지정해주면 풀릴거 같으면 그냥 좌표 지정하자. 만약 좌표 지정하는데 너무 오래 걸린다... 막 테트리스 도형이 아니라 막 이상하다... 이러면 규칙을 찾아보자. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464.. 공감수 0 댓글수 0 2019. 1. 28.
백준 3019. 테트리스 :: 돼지개발자 출저 : https://www.acmicpc.net/problem/3019 "아구가 맞니?" 해당 문제를 처음에는 모든 조각의 상대 위치를 3?4? 차원 배열로 만들어서 모든 경우에 수에 따라 검색하려고 했다. 하지만 조각의 위치를 정의하는데 너무 복잡하고 더러워서 다른 방법을 찾아봄... 아구가 맞는지를 탐색하는 방법이다. 아래와 같이 돌출된 부분에 값을 준다. 전체 높이가 같은지 확인한다.아래 왼쪽 그림의 경우 높이는 2,1 이고 ㅓ 의 경우 돌출된 칸이 1칸 이므로 0,1 이렇게 한 후 높이와 이 값을 더한다. 왼쪽) 2 + 0 = 1+ 1오른쪽 ) 2+ 0 = 1 + 1 = 2 + 0 123456789101112131415161718192021222324252627282930313233343536.. 공감수 0 댓글수 0 2019. 1. 28.
2018 카카오 1차 코딩테스트 오픈채팅방 :: 돼지개발자 출저 : https://programmers.co.kr/learn/courses/30/lessons/42888 "하라는대로~~~" 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354 static final String str1= "님이 들어왔습니다.";static final String str2= "님이 나갔습니다."; public static String[] solution(String[] record) { HashMap map = new HashMap(); int size = 0; for(int i = 0 ; i 공감수 0 댓글수 0 2019. 1. 23.
프로그래머스 124 나라의 숫자 :: 돼지개발자 출저 : https://programmers.co.kr/learn/courses/30/lessons/12899"자리수와 시작 숫자를 구해서 그 지점에서부터 탐색" 구해야 하는 자리수와 시작 숫자를 알고 나서 그 지점부터 탐색하여 탐색 범위를 확 줄여서 시작한다. startWith= 1 startWith= 2 startWith= 4 length = 1 1 (1) 1 (2) 1 (4) length = 2 3 (11,12,14) 3 (21,22,24) 3 (...) length = 39 (...) 9 (...) 9 (...) 위와 같이 검색하면 내가 탐색해야 할 지점을 알 수 있다. 만약 여러 개의 테스트가 주어진다면 이 값을 배열로 저장하는 것도 좋을 듯 하지만 위 문제에서는 필요없어 매번 for문을 돌아서.. 공감수 0 댓글수 0 2019. 1. 23.
2018 카카오 1차 코딩테스트 프렌즈4블록 :: 돼지개발자 출저 : https://programmers.co.kr/learn/courses/30/lessons/17679?language=java "하라는대로~~~~" 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172static int[] dx = {0,0,1,1};static int[] dy = {0,1,0,1}; public static int solution(int m, int n, String[] board) { int answer = 0; char[][] map = new char[m][n]; boolean[][] .. 공감수 1 댓글수 0 2019. 1. 23.
2018 카카오 1차 코딩테스트 비밀지도 :: 돼지개발자 출저 : https://programmers.co.kr/learn/courses/30/lessons/17681 "하라는대로~~~~" 123456789101112public String[] solution(int n, int[] arr1, int[] arr2) { for (int i = 0; i 공감수 0 댓글수 0 2019. 1. 23.
백준 14499. 주사위 굴리기 :: 돼지개발자 출저 : https://www.acmicpc.net/problem/14499 "구현하자." 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899import java.util.Scanner; class Main { static int N,M; static int x,y; static int K; static int[] dice = {0,0,0,0,0,0}; static int[][] map; static int[] dx = .. 공감수 0 댓글수 0 2019. 1. 21.
백준 14888. 연산자 끼워넣기 :: 돼지개발자 출저 : https://www.acmicpc.net/problem/14888 "브루트포스" 다해보자~12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main { static int N; static int num[]; static int op[] = new int[4]; static int max = Integer.MIN_VALUE; stati.. 공감수 0 댓글수 0 2019. 1. 21.
백준 14890. 경사로 :: 돼지개발자 출저 : https://www.acmicpc.net/problem/14890 "시뮬레이션" 해당 문제는 다리를 놓을 수 있느냐 없느냐 를 판별하는 것이 핵심인 문제로 아래와 같이 경사로는 두 가지로 분류할수 있다. 내려가는 경사로와 올라가는 경사로가 둘다 비슷하지만 조금 다른 부분이 있다. 내려가는 경사로의 경우 경사로가 이전에 방문하지 않았던 칸으로 놓이기 때문에, 경사로 설치 여부 체크를 하지 않아도 된다. 하지만 올라가는 경사로의 경우 이전에 방문했던 칸에 경사로를 놓아야 하기 때문에 이전에 경사로를 놓아 지금 칸에 도착한 것인지 판별해야한다... 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647.. 공감수 0 댓글수 0 2019. 1. 19.
백준 15686. 치킨 배달 :: 돼지개발자 출저 : https://www.acmicpc.net/problem/15686 "Brute force/ 다해보자." 1. 마을의 전체 치킨집 에서 m개의 치킨집을 고른다2. 각 집에서 m개의 치킨 중에 가장 가까운 거리를 구하고 모든 집에서의 치킨 거리를 더한다.3. 치킨 거리의 값 중 최소값을 구한다. 고대로 해줬다. 재귀를 가지고 m개의 치킨 집을 고른 후 거리를 구해줬다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687import java.io.Buffer.. 공감수 0 댓글수 0 2019. 1. 17.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.