본문 바로가기

PS831

백준 1068 자바 - 트리 (BOJ 1068 JAVA) 문제 : https://www.acmicpc.net/problem/1068 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01000/BOJ_1068.java 제거된 1개가 루트노드일 경우 무조건 0을 출력하면 된다. 그렇지 않다면, 루트노드부터 탐색할 때 제거된 노드쪽으로는 탐색을 진행하지 않으면서 리프노드들의 갯수를 세주면 된다. 로직은 1. 부모 -> 자식으로 단방향 그래프 간선 정보를 저장해둔다. 2. 루트노드부터 갈 수 있는 모든 곳을 탐색하며. 이 때 제거된 노드로는 진입하지 않는다. 3. 탐색 중 리프노드를 발견하면 카운팅한다. 2021. 11. 9.
백준 13711 자바 - LCS 4 (BOJ 13711 JAVA) 문제 : https://www.acmicpc.net/problem/13711 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/13700/BOJ_13711.java [ 스포 주의 ] 직접 풀어보려면 풀이를 보면 안됩니다. 딱 한마디로 바로 풀이가 끝나는 문제라.. --- LCS 시리즈인척 하는 LIS 문제입니다. LCS ; Longest Common Subsequence LIS ; Longest Increasing Subsequence [오답] 1. 문제제목이 LCS라서 처음엔 LCS 알고리즘으로 풀었습니다. -> 답이야 나오겠지만 당연히 메모리초과 (10만x10만xsizeof(int)) 2. 어차피 N x N 배열이 필요없으므로 배열.. 2021. 11. 9.
백준 16964 자바 - DFS 스페셜 저지 (BOJ 16964 JAVA) 문제 링크 : https://www.acmicpc.net/problem/16964 코드 링크 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/16900/BOJ_16964.java 해결 방식을 떠올리기 다소 어려웠다. 결국 올바른 DFS 방문 순서라 함은 '각 간선을 방문하는 순서는 상관없지만 어쨌든 방문할 간선이 남아 있다면 무조건 방문해야 한다.' 이걸 지키면된다. 예를 들어 아래와 같은 그래프를 보자. 1부터 시작한다. 방문한 곳은 빨간색으로 표시했다. 1에서 2부터 가야할까 3부터 가야할까? 상관없다. 우선 2로 가보겠다. 이 때, 3을 가면 올바른 DFS 순서가 아니게 된다. 2로 일단 갔으면 2에 연결된 간선을 모두 들린 후 3으.. 2021. 11. 9.
[자바] 프로그래머스 - 위장 [코딩테스트 연습 Lv2] [ 문제 링크 ] [ 코드 링크 ] 문제 출처 : 프로그래머스 코딩 테스트 연습 각 의상 종류에 해당하는게 몇 가지씩인지만 알면 된다. 이 때 의상 이름의 경우 '같은 이름을 가진 의상은 존재하지 않습니다.' 에 따라 의미가 없으므로 버려도 된다. 즉, 예제1의 경우 의상 이름은 필요없고 아무튼 headgear 2 eyewear 1 라는 점만 알면 되며, 사실 종류명도 별로 상관없다. 동일한지만 hashing을 통해 확인할 수 있으면 된다. 그럼 계산은 어떻게 해야하냐면, 옷이 2종류라고 치면 2칸을 둬보자. 'ㅇㅇ' 첫번째 칸은 headgear를 입거나 입지 않을것이고, 2번째칸은 eyewear를 입거나 입지 않을 것이다. 그럼 경의의 수는 (2+1) * (1+1) 이 된다. 여기서 +1은 '입지 않는.. 2021. 11. 8.
백준 1036 자바 - 36진수 (BOJ 1036 JAVA) [ 백준 1036 - 36진수 ] [ 코드 보기 (깃헙 링크) ] 23046(큰 수 뒤집기)를 얼마전에 푼 이후로 당분간 큰 수 연산 관련된건 안보려 했으나, 그냥 그리디에 36진수 자리수 올림 (carry) 정도만 필요한것같아 시도했다가 로직 자체가 틀리면서 물렸다.. 그 뒤로 맞는 것 같은 로직을 세웠는데, 결국 더 많은 큰 수 연산이 필요했다 ㅠㅠ 그래도 이번엔 BigInteger로도 입력 숫자 자체가 적다보니 문제없어서 다행이었다.. 로직 자체는 그리디인데, 로직보다도 구현 자체가 빡쌨던 문제이다. [ 틀린 로직 ] 가끔씩 틀린 로직도 적는데, 누구 보라고 적는건 아니고 나중에 내가 다시 봤을 때 이렇게 틀렸었지! 하기 위해서이다. 그러니 아래쪽의 'AC 코드 해설'로 바로 넘어가도 상관없음. 처.. 2021. 11. 7.
백준 2786 자바 - 상근이의 레스토랑 (BOJ 2786 JAVA) [ 백준 2786 - 상근이의 레스토랑 ] [ 코드 보기 (깃헙 링크) ] 쉬운 것 같으면서도 은근 생각할게 좀 있었다. 일단 생각 과정을 적어본다. 1. 첫 음식이 A가격이 아니고 B가격만 있었다면 어떻게 계산할까? -> 음식을 입력받은 순서와 관계없이 B가격만 영향을 끼치므로, 그리디하게 B 가격 순서대로 구매한다고 생각하면 된다. 따라서 B를 기준으로 정렬한 후 prefix sum(누적 합) 배열 하나 만들어두면 쉽게 출력 가능하다. 결국 첫 음식은 A가격을 지불해야 하는 부분만 잘 처리하면 되는 문제이다. 2. 음식을 1개 시킬 때 최소 가격 : [전체 중 최소 A 값] 3. 음식을 n개(전부) 시킬 때 최소 가격 : [모든 B를 더한 값] + [(A-B)의 최소값] -> 2,3번을 합쳐서 그럼 .. 2021. 11. 6.
백준 17469 자바 - 트리의 색깔과 쿼리 (BOJ 17469 JAVA) [ 백준 17469 ] [ 코드 (깃헙) ] 트리의 부모를 알려주고, 주어진 쿼리를 해결해야 한다. 쿼리는 '1 a'와 같이 들어오면 간선 제거, '2 a'와 같이 들어오면 a에서 갈 수 있는 정점들에 포함된 색깔 종류의 개수를 출력해야 한다. 당연히 매번 쿼리를 진행하고 bfs나 dfs로 갈 수 있는 경로를 찾고 또 해당 노드들에 존재하는 색깔 종류를 셀 순 없다(시간초과). 그럼 일단 각 부분들을 뭘 이용해 구할 수 있을지 확인해보자. 1. 갈 수 있는 정점들 확인 : union-find를 사용한 그룹짓기 2. 각 그룹에 포함된 색깔 종류의 개수 : HashSet을 사용하면 애초에 동일한 색깔이 중복해서 안들어가니, 해당 set의 size()만 확인하면 해당 그룹에 포함된 색깔 종류의 개수를 알 수 .. 2021. 11. 4.
백준 13306 자바 - 트리 (BOJ 13306 JAVA) [ 백준 13306 ] [ 코드 (깃헙) ] 트리의 부모를 알려주고, 주어진 쿼리를 해결하는 문제이다. 쿼리는 '0 b'와 같이 들어오면 b번째 edge 제거하는 쿼리와, '1 c d'와 같이 들어오면 c와 d 사이에 연결경로가 있는지 묻는 쿼리가 있다. 일단 거리 자체를 묻지 않고, 연결 경로가 있는지만 파악하면 된다. 그럼 이거엔 union-find 알고리즘을 쓰면 될 것임을 알 수 있다. 다만 해당 알고리즘의 경우 그룹간의 관계를 맺는것은 쉽지만, 연결을 끊는건 힘들다. 그럼 쿼리를 반대순서로 보면 어떻게 될까? 원래 순서대로라면 '간선들이 존재하는 그래프에서 edge를 제거하면서 중간중간 특정 노드간에 연결경로가 있는지 묻는 쿼리' 이지만, 반대로 미리 쿼리상에 존재하는 모든 간선을 제거한 후 역.. 2021. 11. 4.
백준 1138 자바 - 한 줄로 서기 (BOJ 1138 JAVA) [ 문제보기 ] [ 코드보기(깃헙) ] N이 최대 10이다. 따라서 모든 경우를 보려면 10! 번을 봐야한다. 이 경우 362880번으로, 사실 모든 경우를 봐도 가능하긴 하다! 다해봐야 O(N! * N) 정도이다. 사실 시간복잡도, 메모리복잡도 면에서 모두 이득인 방법이 더 있다. 어차피 입력이 키가 1인 사람부터 차례대로 들어오기 때문에, 키가 큰 사람부터 순서대로 입력을 만족하는 위치에 넣어버리면 된다. (따라서 그리디 알고리즘 분류다.) 4 2 1 1 0 의 입력을 확인해보자. 이 경우 키가 1인 사람은 좌측에 2명, 2인 사람은 좌측에 1명, 3인 사람은 좌측에 1명, 4인 사람은 좌측에 아무도 없다는 입력이다. 키가 작은 사람부터 보자면 어려운 문제가 확실하지만, 키가 큰 사람부터 보면 엄청 .. 2021. 11. 3.
백준 1485 자바 - 정사각형 (BOJ 1485 JAVA) [ 문제 보기 ] [ 코드 보기(깃헙) ] [ 틀린 경우 ] 처음엔 아래와 같이 축에 평핸한 정사각형을 찾는줄 알았다. 그래서 예를들어 입력이 1 1 1 1 2 2 1 2 2 와 같다면, 사실 좌측이 x축인지 우측이 x축인지는 안알려줬지만 상관없이 좌측이 2종류고, 우측이 2종류이며 각각 2번씩 나왔고, 좌측의 2종류의 차이와 우측의 2종류의 차이가 동일하다면 정사각형으로 판단하도록 했다. 이 코드는 틀렸다. [ 해설 ] 그렇다면 아래와 같이 정사각형이 기울어 있는 경우까지 찾을 수 있어야 한다. 1. 그래도 딱히 어려울건 없는데, 그냥 4개의 점을 입력받고 나올 수 있는 모든 경우의 길이를 구해본다. 4개에서 2개를 순서없이 골라야하니, 4C2 = 4P2 / 2! = 4*3/2 = 6가지만 구해보면 된.. 2021. 11. 3.

티스토리툴바