알고리즘
[백준 - 1010번] 다리 놓기 - 자바(JAVA) 정리 및 해설 & 1일 1DP - 1일차
[백준 - 1010번] 다리 놓기 - 자바(JAVA) 정리 및 해설 & 1일 1DP - 1일차
2020.02.18안녕하세요. 오늘 풀어볼문제는 백준 다리 놓기입니다. 이 문제는 다이나믹 프로그래밍 혹은 조합으로 문제를 푸는 문제입니다. https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 일단 이문제에서 결국 포인트로 잡아야하는 부분은 얼만큼 최대한 많은 여러가지의 경우의 수를 체크할 수 있냐라는 포인트입니다. 예시를 들어서 설명해보겠습니다. 한점에서 3점으로 만들 수 있는 경우의 수는 3가지입니다. 근데 저희가 문제가 되는 것은 N개의 점일때 M개의 점을 따..
1일 1DP를 시작해보겠습니다.
1일 1DP를 시작해보겠습니다.
2020.02.18최근들어서 알고리즘 공부를 좀 멀리한 경향도 있고, 다시 어느정도의 감을 잡기위해서는 DP 문제의 사고력이 필요하다고 느꼈습니다. 실제로 여러 코딩테스트를 준비하기에는 DP문제의 난이도가 적당하다고 생각했습니다. DP문제들을 빠르게 풀어가면서, 하루에 하나씩 DP문제를 풀어 보는 시간을 가지도록 하겠습니다. 물론 완벽하게 1일 1DP를 지킬 수 있을지는 조금의 의문이 드는 건 사실이지만 최대한 노력해서 많은 문제를 풀어보고 싶네요.
[백준 - 12790번] Mini Fantasy War - 자바(JAVA) 정리 및 해설
[백준 - 12790번] Mini Fantasy War - 자바(JAVA) 정리 및 해설
2019.09.27안녕하세요. 이번 문제는 구현 문제인 Mini Fantasy War를 풀어보겠습니다. 이문제는 구현 문제인데, 개인적인 생각을 정리하기 위해서 적습니다. 구현 문제에서는 코드를 얼마나 줄일수있냐가 문제를 빠르게 풀 수 있는 지를 가르는 척도라고 생각합니다. 즉, 체력, 마력, 공격력, 방어력을 함수처리를 해버리는 걸로 문제 해결을 편하게 할 수 있습니다. Main문에 여러가지 코드를 넣는 것보단 외부에 함수를 만들어서 한번에 처리하는 것이 나중에 코드를 고치거나 오류점을 찾아내기가 편할 겁니다. /** 2019. 9. 23. */ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; impor..
[백준 - 5585번] 거스름돈 - JAVA 정리 및 해설
[백준 - 5585번] 거스름돈 - JAVA 정리 및 해설
2019.09.27안녕하세요. 오늘 풀어볼 문제는 거스름돈입니다. 이 문제는 그리디 방식의 문제입니다. https://www.acmicpc.net/problem/5585 5585번: 거스름돈 문제 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오. 예를 들어 입력된 예1의 경우에는 아래 그림에서 처럼 4개를 출력해야 한다. 입력 입력은 한줄로 이루어져있고, 타로가 지불할 www.acmicpc.net 거스름돈의 경우는 구현 문제라고 해서 문제를 풀었습..
2019 Kakao Blind CodeTest - 2. 실패율 자바(JAVA) 해설 및 정리
2019 Kakao Blind CodeTest - 2. 실패율 자바(JAVA) 해설 및 정리
2019.09.08안녕하세요 .이번의 풀어볼 문제는 실패율입니다. 실패율은 객체 정렬을 통해서 문제를 해결합니다. 문제 2. 실패율 정답률: 55.57% 문제 풀러 가기 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다. 이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았다. 오렐리를 위해 실패율을 구하는 코드를 완성하라. 실패율은 다음과 같이 정의한다. 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테..
2019 Kakao Blind CodeTest - 1. 오픈 채팅방 자바(JAVA) 해설 및 정리
2019 Kakao Blind CodeTest - 1. 오픈 채팅방 자바(JAVA) 해설 및 정리
2019.09.08안녕하세요. 차후 있을 카카오 코딩테스트들을 준비하면서 카카오 블라인드 코딩테스트 1차 시험에서 나왔었던 문제들을 풀어 보았습니다. 풀어본 문제를 어떤 식으로 풀었고, 어떤식으로 해결 했는지에 대해서 이야기를 해보려고 합니다. 문제 1. 오픈채팅방 정답률: 59.91% 문제 풀러 가기 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오픈 채팅방을 개설한 사람을 위해, 다양한 사람들이 들어오고, 나가는 것을 지켜볼 수 있는 관리자창을 만들기로 했다. 채팅방에 누군가 들어오면 다음 메시지가 출력된다. “[닉네임]님이 들어왔습니다.” 채팅방에서 누군가 나가면 다음 메시지가 출력된다. “[닉..
[백준 - 16235번] 나무 제테크- JAVA 정리 및 해설(삼성 SW 역량테스트)
[백준 - 16235번] 나무 제테크- JAVA 정리 및 해설(삼성 SW 역량테스트)
2019.07.24안녕하세요. 이번에 풀어볼 문제는 나무 제테크입니다. 나무제테크는 시뮬레이션을 이용한 문제입니다. 문제 자체는 엄청 간단하므로, 구현하라는 대로 구현을 해주면 그렇게 어려울게 없는 문제입니다만, 구현대로 하면 약간의 오류가 발생하는데요. 바로 시간초과에 걸리게됩니다. 처음에 문제를 풀때는 ArrayList를 이용해서 문제를 풀었는데 이 경우는 시간 초과가 발생하게 됩니다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayList; i..
[백준 - 1912번] 연속합- JAVA 정리 및 해설
[백준 - 1912번] 연속합- JAVA 정리 및 해설
2019.07.13안녕하세요. 오늘 풀어 볼 문제는 연속합입니다. 연속합은 Dynamic Programming을 이용한 문제입니다. 연속합은 연속된 수중에서 가장 큰 합을 구하는 문제이기 때문에 수열마다 연속적으로 수를 더해가면서 그합이 가장 큰 경우를 찾으면 된다고 생각해서 문제를 이런식으로 풀 수도 있습니다. 수열에서 n번째 수부터 마지막까지 연속적으로 더해가면서 가장 큰 수를 cache[n]에 저장하고 그 cache배열에서 가장 큰수를 더해가는 방식으로 문제를 풀었습니다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io..
[백준 - 14499번] 주사위굴리기 - JAVA 정리 및 해설(삼성 SW 역량테스트 문제)
[백준 - 14499번] 주사위굴리기 - JAVA 정리 및 해설(삼성 SW 역량테스트 문제)
2019.07.12이번 문제는 삼성 SW역량테스트 기출문제인 주사위 굴리기입니다. 시뮬레이션 문제 방식으로 문제를 풀면 됩니다. 저도 처음에는 이 시뮬레이션 문제를 어떤식으로 풀어야할지 감을 잘 못잡았는데요. 푸는 방식은 간단하게 케이스를 나눠서 생각해보고, 순차적으로 문제를 어떤식으로 진행할지를 생각해보고, 문제를 접근하는 편이 좋습니다. 여기서 시뮬레이션에서 가장 큰 골격은 3가지의 루틴으로 진행됩니다. 1. 지도상에서 주사위를 이동시켜봅니다. 1-1. 지도상에서 주사위가 밖으로 이동한 경우. 무시합니다. 2. 지도상에서 주사위가 밖으로 이동하지 않은 경우 이동 방향에 따라서 이동합니다. 3. 주사위의 아래쪽은 Map의 경우에 따라 그값을 복사하거나 복사해줍니다. 그 이후에 주사위 상단의 값을 출력합니다. 이 루틴을 ..
[백준 - 2579번] 계단오르기 - 자바(JAVA) 정리 및 해설
[백준 - 2579번] 계단오르기 - 자바(JAVA) 정리 및 해설
2019.03.13오늘은 대표적 DP(Dynamic Programming)문제인 계단오르기를 보겠습니다. Dynamic Programming 초반에 가장 많이 연습하게 되는 문제인 계단오르기는 처음에 접할때는 조금 어렵습니다.. 일단 저는 DP에 대해서 짚고 넘어가야된다고 생각합니다. 우리는 왜 DP를 사용하는 것에 대해서 정확한 인지가 필요하고 이걸 바탕으로 문제를 풀어보도록하겠습니다. DP는 기본적으로 중복으로 여러번 계산하는 것을 막기위해서 고안된 방법입니다. 개념이 길긴하지만, 간단하게 쉬운 사례를 들면. 파스칼의 삼각형을 생각해보면 쉬운데 파스칼의 삼각형은 이항계수의 앞의 계수를 구할때 사용하는 방법인데, 이게 삼각형의 모양을 띄고 있다보니, 중복되는 경우가 발생합니다. 그래서 이경우 재귀적(재귀인지 혹은 For..
[백준 - 2292번] 벌집 - 자바(JAVA) 정리 및 해설
[백준 - 2292번] 벌집 - 자바(JAVA) 정리 및 해설
2019.03.06안녕하세요. 오늘 풀어볼 문제는 벌집입니다. 벌집은 단순히 수학적 공식으로도 풀수 있는 문제이지만, (결국 그게 수학적인 규칙성을 찾아서 공식화 시킨거긴 하지만.) 그 공식 과정을 직접 일일히 대조하는 방식으로 진행했습니다.저는 일단 인접한 방들을 기점삼아서 즉 2~7까지 인접해 있는 수들의 규칙성을 확인해보는 식으로 수를 만들어 갔습니다.첫번째 1을 거쳐서 방을 지나가기때문에 다음 방은 2일것이니N =2 2, 3, 4, 5, 6, 7 N=3 9, 11, 13, 15, 17, 19N=4 22, 25, 28, 31, 34, 37..... 계속 이런식으로 진행하게 될것입니다. 그 그림들로 보시면 N은 각 방을 지나서 갈수 있는 곳이고, 그 수에 있는 수들이 색깔별로 늘어나가는 숫자라고 생각하면 됩니다. 근데..
[백준 - 3055번] 탈출 - 자바(JAVA) 정리 및 해설
[백준 - 3055번] 탈출 - 자바(JAVA) 정리 및 해설
2019.02.17이번 문제 탈출은 두 개포인트에서 시작하는 BFS를 다루는 문제입니다. 동시간에 두가지 곳에서 동시에 퍼져나가는 경우에는 BFS를 사용합니다. 이렇게 풀지 않으면 안풀리는 경우가 많은데요. 어차피 같은 시간에 같은 공간에서 같은 회차로 움직여야하기때문에, 그런것을 감안을 해서 문제를 풀어야합니다.그럼 문제를 풀어가는 논리적인 구성을 생각해봅시다. 1. 일단 이문제는 BFS를 풀어야한다는 사실을 알았고, 미로찾기와 같은 x,y를 동시에 queue안에 넣어야합니다. 물론, 두 queue를 이용해서 사용할 수 있지만, 저는 혹시 모를 상황을 대비(그렇게 된 경우는 적으나, 두 큐에 넣었을때 같은 순서로 되지 않을 경우가 있을 수도? 있을 것같아서 저는 적어도 두 인수를 가진 상황이면 그냥 묶어서 집어넣습니다...