본문 바로가기

분류 전체보기1053

백준 12931 자바 - 두 배 더하기 (BOJ 12931 JAVA) https://www.acmicpc.net/problem/12931 우선 처음으로 생각할 부분이, 만약 시작지점인 0,0,0,... 에서 시작해서 제시된 B 배열을 찾아가려면 결국 모든 경우를 봐야한다. 매번 B 배열과 비교하며 최소 연산 횟수를 찾게 짜는건 사실상 무리라고 본다. 그럼 반대로 B 배열에서 0,0,0,...을 찾아가는걸 생각해보자. 제시된 연산은 각각에대해 1을 더하는 것과 전체에 대해 2를 곱하는 것이므로, 반대로 B배열에서 0,0,0,... 을 찾아가기 위해서는 각 배열에 대해 1을 빼는 연산과, 전체에 대해 2로 나누는 과정을 거쳐야 한다. 그럼 N=1일 때 조차도 무조건 2로 나누는 것이 이득인 것을 쉽게 알 수 있다. (더 적은 연산으로 차이를 더 많이 낼 수 있음) 최종적으로 .. 2021. 10. 5.
백준 15989 자바 - 1, 2, 3 더하기 4 (BOJ 15989 JAVA) https://www.acmicpc.net/problem/15989 처음엔 무지성 DP 돌리면 될줄 알았는데, 수의 순서가 다른 것은 하나로 처리해야 한다. 무작정 dp 진행하며 모든 쌍을 확인하고, 그 중 겹치는 것을 확인하기엔 메모리가 부족해보인다. 풀이1. 2차원 DP https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/15900/BOJ_15989_2D-DP.java 우선 서로 겹치는 쌍이 생기지 않도록 하려면 어떻게 해야할까? 각 n에서 더해지는 숫자에 제한을 두면 된다. 예를 들어 서로 겹쳐도 된다고 생각하고 n = 1~4 일 때 1,2,3의 덧셈으로 표현 가능한 경우를 보자. 1 : 1 2 : 2, 1+1 3 : 3, 1+1+1, 1+.. 2021. 10. 4.
백트래킹 알고리즘 (Back Tracking) 다음과 같은 그래프가 있다. 여기서 1부터 시작해서 숫자 순서대로 얼마나 멀리 갈 수 있는지 찾고싶다. 즉 1->2->3->4->5->... 이런식의 루트를 찾으려 한다. 우선 생각해볼 수 있는 방법은, 그냥 모든 루트에 대해 DFS 등을 사용해 전부 탐색해 보는 것이다. 이 방식이 이전에 작성한 Brute Force 방식이다. 그냥 컴퓨터의 빠른 연산력에 기대어 모든 경우를 확인하는 것이다. 위는 모든 경우를 살펴보는 DFS 과정의 순서를 표시한 것이다. 모든 경우를 확인해보니 결국 1->2->3->4를 찾긴했다. 그런데 우린 직관적으로, 중간과정에서 이미 순서가 안맞다면 해당 루트로는 아예 안가봐도 될 것임을 알 수 있다. 그럼 다음 이미지를 보자. 위와 같이 답이 될 가능성이 없는 경로라면 더이상 .. 2021. 10. 3.
백준 21772 자바 - 가희의 고구마 먹방 (BOJ 21772 JAVA) https://www.acmicpc.net/problem/21772 BFS로 착각할 여지가 있는 문제이다. 하지만 한번 지나간 곳을 다시 올 수 있다는 점과, 지나간 경로상에 있는 고구마의 갯수를 세야 하는 문제이므로 방문체크를 할 수 없다. 따라서 모든 경로를 보는 Brute Force 문제이다. 정확히 따지자면 내 로직의 경우 사실 모든 경우를 보진 않았고, 답이 될 수 없는 경로인 경우 취소시켰으므로 Back Tracking이라 봐도 되는데, 어차피 모든경로 다 봐도 시간초과가 나진 않으므로 큰 의미는 없다. t가 최대 10이고 한 장소에서 상하좌우 4개의 방향으로 이동 가능하므로 최대 O(4^10) 짜리 BF라고 보면 된다. 그냥 DFS 돌리면서 모든 경우를 확인하면 된다. 주의점은 '가희가 고구.. 2021. 10. 3.
백준 11048 자바 - 이동하기 (BOJ 11048 JAVA) https://www.acmicpc.net/problem/11048 만약 이동이 상하좌우로 가능했었다면, 혹은 [우측, 아래, 우측아래, 좌측]과 같이 좌측으로도 이동이 가능했다던지 하면 BFS 등의 방법으로 전체 경우를 보면서 풀어야 한다. 하지만 이처럼 방향이 우측, 아래, 우측아래 대각선 처럼 한쪽 '사분면'으로 고정되어 있다면 Dynamic Programming(DP; 동적계획법)으로 더 간단하게 풀 수 있다. 일단 다음의 그림을 보자. 위 그림은 이 문제에서 (1,1)에서 (N,M)으로 갈 때 각 위치에서 이동할 수 있는 방향을 나타낸 것이다. 그럼 위 그림에서 예를들어 정중앙의 '5'로 올 수 있는 화살표만 남겨보겠다. 다음으로 중앙 우측의 '6'으로 오는 화살표이다. 그럼 벽에 붙어있는 '2.. 2021. 10. 2.
백준 2825 자바 - 수업시간에 교수님 몰래 교실을 나간 상근이 (BOJ 2825 JAVA) https://www.acmicpc.net/problem/2825 알고리즘 분류랑 솔브닥 티어 표시 끄고, 문제 검색 옵션에서 실~플로 랜덤으로 나오게 하고 문제푸니 쫄깃하게 재밌다. 이건 처음엔 실버상위~골드하위 정도일줄 알았는데, 생각할수록 최소 골드 중간쯤은 될꺼란 생각이 들었다.. 처음엔 단순하게 1이 포함된 숫자 리스트, 2가 포함된 숫자 리스트, ... 이렇게 분류해서 union-find나 각 쌍을 hashset에 넣으면서 nCr로 계산하면 될 것 같았다. 하지만 아무리 생각해봐도 시간복잡도를 O(N^2)에서 줄일수가 없었다. 이쯤에서 실~골하위는 아닐꺼라 일단 생각이 들었다 ㅋㅋ N이 100만개이므로 O(N^2) 풀이는 아예 불가하고, 못해도 O(NlogN) 정도 수준으로 생각해내야 한다. .. 2021. 10. 2.
자료구조 리스트 (List) - Linked List, Array List, Vector 차이점 포함 리스트? (Linked List - 연결 리스트) 일반적으로 '리스트'는 연결 리스트(Linked List)를 뜻한다. 이후 Array List와 Vector를 추가로 설명하기 전까지 모든 설명은 연결 리스트(Linked List)에 대해 다룬다. 리스트는 배열처럼 데이터를 순서대로 표현하는 자료구조 중 하나인데, 구현 방법에 큰 차이가 있다. 배열은 메모리 상에 연속된 공간을 '미리 할당받고' 메모리상에 데이터를 순서대로 넣어 만든 자료구조이다. 리스트는 메모리 상에 데이터가 어디에 있던 신경쓰지 않는다. 'data = [12. 3. 11. -2]'를 배열과 리스트로 표현해보겠다. 위의 정갈하게 메모리상에 순서대로 들어가 있는 것이 배열, 아래쪽에 메모리상에 흩뿌려져 있는 것이 리스트이다. 이 때 배열.. 2021. 9. 30.
백준 2617 자바 - 구슬 찾기 (BOJ 2617 JAVA) https://www.acmicpc.net/problem/2617 홀수인 N개의 구슬 중 '중간이 될 수 없으려면' 자신보다 무게가 작은게 (N/2+1)개 존재하거나, 무게가 큰게 (N/2+1)개 존재하면 된다. 예를들어 N이 7일 때 자신보다 큰게 4개라면 무조건 중간엔 가고싶어도 갈 수 없다. 이 문제는 다소 이해하기 난해할수도 있으나, 결국 '자신보다 큰게 (N/2+1)개 이상 있거나, 자신보다 작은게 (N/2+1)개 이상 있는 구슬의 갯수를 구하면 된다.' 그럼 어떻게 구할까? M개의 쌍에 대해 어느쪽이 무거운지 알려줬는데 이걸 단방향 그래프(=directed graph =유향 그래프 =방향 그래프)의 edge라 생각하면 쉽다! 문제에서 제시된 예시를 단방향 그래프로 그려보겠다. 우선은 '무게가 .. 2021. 9. 30.
[자바] 프로그래머스 - 지형 이동 [코딩테스트 연습 Lv4] - 문제 : https://programmers.co.kr/learn/courses/30/lessons/62050 - 코드 : https://github.com/NaHwaSa/Programmers_OnlineJudge/blob/main/Level%204/%EC%A7%80%ED%98%95%20%EC%9D%B4%EB%8F%99.java 1. 모든 칸을 방문한다고 했지, 한 칸에 여러번 가면 안된다는 말은 없었다. 따라서 높이차이가 height 이하인 곳은 가중치 0으로, 아무런 제약 없이 돌아다닐 수 있다. -> 다시 말해, 상하좌우로 높이차이가 height 이하인 곳은 서로 그룹으로 생각해도 됨. -> 예를들어 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, .. 2021. 9. 29.
백준 6549 자바 - 히스토그램에서 가장 큰 직사각형 (BOJ 6549 JAVA) https://www.acmicpc.net/problem/6549 코드가 긴 문제는 아니었지만, 공책에 그려보며 생각한걸 구현하기가 좀 어려웠다. 많이틀렸다 ㅋㅋ (맞았습니다가 여러개인 이유는 시간을 좀 더 줄여보려 했으나 유의미하게 시간차이를 못냈다.) 풀고보니 사람들이 참 다양한 방법으로 푼 문제인것같다. 스택, 분할정복, 세그먼트 트리, 분리집합+우선순위 큐 크게는 이렇게 4가지 방식으로 푼 듯 하다. 저의 경우엔 스택으로 풀었다. 높이(h)가 너비(n)에 비해 수치가 많이 크다. 처음 들었던 생각은 어차피 높이가 많다해도, n이 최대 10만이므로 h의 종류는 아무리 많아봐야 10만 가지이다. 따라서 좌표압축처럼 높이를 1~10만까지로 압축할 수 있다. (예를들어 높이가 3,5,2 처럼 들어왔다면 .. 2021. 9. 29.

티스토리툴바