유쾌하게 긍정적으로 유쾌하게 긍정적으로

해결 과정 두 배열이 주어지면 각 배열마다 부 배열의 합이 있을 것이고, 특정 부 배열의 합들을 더해서 T를 만족하는 경우의 수를 구하는 문제다. 문제에서 주어졌듯이 부 배열은 각 배열에서 매우 많다. (단, 입력의 조건에 의해 최대 배열의 길이는 1000이므로 배열 당 최대 1000000개까지 나올 것이다) 부 배열은 연속된 배열이라는 특징이 있다. 가장 먼저 눈에 띄는 것은 T의 범위인데 범위가 매우 커서 int로 담을 수 없다는 것을 바로 알 수 있다. 따라서 문제 해결 과정에서 필요한 곳에 long 타입을 사용해야한다. 또한 단순히 모든 부 배열의 쌍을 구한다면 1000000 * 1000000 번의 연산이 필요하기 때문에 시간초과가 발생할 것이다. 따라서 다른 방법으로 접근해야한다. 이 문제는 경..

해결 과정 회의실 배정을 적절히 해서 가장 많은 스케줄을 할당하게 하는 문제다. 처음에는 솔루션이 떠오르지 않아, 모든 케이스에 대해서 다음에 올 가장 적절한 스케줄을 찾아나가는 식의 Brute Force를 생각해봤으나, 회의의 수가 최대 100000개이기 때문에 모든 케이스에 대해서 접근하면 O(n^2), 즉, 100000^2의 연산이 필요하다. 따라서, 시간초과가 발생할 여지가 충분했다. 따라서 적어도 O(n*lgN)이나 O(n)의 시간복잡도를 가지는 알고리즘이 필요했는데, 시작 시간이나 종료 시간을 기준으로 해당 타임에 가장 적합한 스케줄을 앞에서부터 찾아나가면 되겠다고 접근했다. 문제를 자세히 보면, 종료 시간이 가장 짧은 스케줄들을 차례대로 이어나가다보면 회의의 최대 개수를 구할 수 있음을 알 ..

해결 과정 주어진 그래프가 이분 그래프인지를 판별하는 문제다. 문제의 설명에서 이분 그래프에 대한 간단한 설명이 주어지는데, 사실 이것만 읽고 이분 그래프를 이해하기가 힘들었다. 그래서 가장 먼저 이분 그래프에 대해 조사를 했다. 먼저 위키 백과에서 조사를 했는데, 대충 꼭짓점을 색칠한다는 걸로 나와있으나, 이분 그래프에 대한 개념이 없던 나로서는 이해하기 매우 힘든 설명이었다. 그래서 다른 블로그를 조사했고, 이분 그래프에 대해 명확한 설명이 나와있는 블로그 게시글을 봤다. https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html [알고리즘] 이분 그래프(Bipartite Graph)란 - Heee's Development Blog ..

해결과정 전형적인 브루트 포스 형태의 문제이다. 문제는 수빈이와 동생의 위치가 일치되는 지점을 찾고 거기까지 걸리는 최소 시간을 찾는 문제이다. 재밌는 것은 위치는 선형적으로 계산하면 되고, 순간이동이라는 선택지가 있다는 것이다. 따라서, 각 이동시점마다 선택할 수 있는 선택지는 3개이다. 이러한 선택지와 과정들을 탐색하면서 가장 빠른 시간에 일치되는 시점을 찾는 것이다. 처음에는 DFS로 접근을 했는데, 이렇게 됐을 경우 StackOverFlow가 발생했다. 왜냐하면, 재귀적으로 호출하기 때문에 운이 좋으면 바로 찾아낼 수 있지만, 잘못된 과정으로 진입한다면 100000이 넘어서는 지점까지 계속해서 재귀호출을 하기 때문이다. 예를 들어, X+1 호출이 맨 처음 선택지로 주어진다면 재귀 호출은 10000..

https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 구현 문제입니다. 2차원 배열에서 지나갈 수 있는 길이 몇개인지를 판별하는 문제인데, 지나갈 수 있는 길에 대한 조건을 잘 코딩하는 것이 중요했습니다. 지나갈 수 있는 길은 한 열, 또는 한 행만을 판단합니다. 따라서, 전체 배열은 2차원 배열이지만, 체크하는 함수를 따로 분리해서, 1차원 배열을 받아 체크하면 될 것이라고 생각했습니다. 문제의 조건에 나와있듯이, 길의 높이가 모두 같으면 그 길은 통과 가능합니다. 만약..

문제 링크 : www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 풀이 각각 톱니가 8개가 있는 톱니바퀴 4개가 주어진다. 이를 회전시킬 때, 톱니가 어떻게 변하는지 계산하는 문제. 톱니를 회전하면 어떻게 데이터를 변경시킬지 고민해야하고, 한 톱니 바퀴를 회전시켰을 때, 맞닿는 톱니와 이에 대한 결과를 생각해야한다. 특히, 맞닿는 조건과 연쇄적으로 회전하는 부분에 대한 구현이 중요했다. 각각의 톱니가 회전하는 것은 동일하고, 톱니에 대한 데이터를 저장해야하..

오늘은 백준의 1260번 문제인 DFS와 BFS문제를 풀어봤는데요, DFS와 BFS의 개념과 구현, 그리고 인접 행렬과 인접 리스트에 대한 내용을 공부할 수 있는 아주 좋은 문제 같았습니다. 학부 수업에서 자료구조를 들으면서 DFS와 BFS, 그래프에 대해서 짧게 배운적이 있습니다만 구현을 해보고 응용하기엔 너무 얕게 배워서 오늘 이 문제를 풀면서 다시 공부하게 됐었네요. 그래프와 인접 행렬, 인접 리스트 DFS, BFS를 들어가기 전에 그래프의 개념에 대해서 알아볼 필요가 있는데요 그래프는 노드와 그 노드를 연결하는 간선을 하나로 모아놓은 자료구조입니다. 여기서 노드는 경우에 따라서 Vertex로 부르기도 합니다. 그래프는 상당히 큰 개념인데요, 트리라고 불리는 자료구조도 그래프의 일종입니다. 그래프의..

시간 복잡도를 항상 고려해야한다 오늘 알고리즘 문제로 프로그래머스의 '탑'문제를 풀었는데요. 검색과 비교의 문제라고 판단하고 자료구조를 배열로 해서 접근했습니다. 출력은 정확히 나오지만, 시간초과가 발생해 정답으로 인정되지 않았습니다. 이 문제는 분류가 스택/큐 입니다. 역시 출제자의 의도를 잘 파악하는 것이 중요한 것 같네요. 자료구조를 어떤 것으로 쓰냐에 따라 속도의 차이가 많이 발생하는 것 같습니다. 일단 저는 스택으로 풀지 못했지만 문제를 푼 다른 사람들의 코드를 참고해서 스택으로 수정해봤습니다. 배열로 접근한 코드 public class Solution { public int[] solution(int[] heights) { int[] answer = {}; int size = heights.l..