본문 바로가기

전체 글1065

백준 13717 자바 - 포켓몬 GO (BOJ 13717 JAVA) 문제 : https://www.acmicpc.net/problem/13717 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/13700/BOJ_13717.java 문제에 제시된 '힌트'에서는 하나씩 확인하고 있다. 물론 그렇게 해도 워낙 입력값이 적어서 충분히 가능하지만, 약간만 수식을 넣으면 더 효율좋게 풀 수 있다. Weedle 12 42 위 입력에 대해 보자. k와 m을 입력 받고 m을 k로 나눈 몫으로 현재 몇개 살 수 있는지 알 수 있다. cnt = m/k = 42/12 = 3 (몫) 그리고 m은 m%k (나머지)로 변경한다. 그럼 m = m%k = 6이 된다. 그리고 살 수 있을 때 마다 2개를 되돌려받으므로, 몫*2를 m.. 2021. 11. 10.
백준 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.
읽은 책 소감 - 비전공자를 위한 이해할 수 있는 IT 지식 최근 친한 동생이 개발쪽으로 전향하고싶어해서 국비지원 교육을 듣는다고 한다. 개발적인 부분이야 따로 묶어두고 강제로(?) 알려주면 되니, 당장 배경 지식을 쌓아줄겸 추천해줄만한 책을 살펴보다가 발견한 책이다. 난 전공자긴 하지만 일단 목차가 너무 재밌을 것 같기도 하고, 200페이지 좀 넘는 얇은 책이라 부담없이 볼 수 있을 것 같아 나도 하나 샀다. 확실히 재밌어서 한 2일만에 다 읽었다. 책의 목표는 기획자나 디자이너 등 개발자와 같이 일하는 사람에게 배경지식을 쌓아줘서 개발자와 얘기가 통하게 하는걸 목표로 한 책으로 보인다. 사실 개발자라면 대강 다 알고있는 내용들이긴 할테지만, 막 개발자를 시작한 사람들에게도 강력하게 추천할만하다. 솔직히 이정도면 신입 개발자 필독서는 물론이고 영업팀, 기획팀 등.. 2021. 11. 6.
읽은 책 소감 - 수학귀신 알고리즘 풀 때, 알고리즘 해설을 블로그에 작성할 때 증명적인 면이 너무 부족한 것 같다. 특히 수학 관련 알고리즘 문제를 푸는데 어려움이 있다. 뭐 기업 코테같은 것에선 큰 수학적 지식을 요구하진 않으니 현재의 수준으로도 딱히 상관없는 부분이지만, 애초에 알고리즘은 취미로 하고있었고 앞으로도 꾸준히 할테니 수학적 지식이 필요하다(개인만족을 위해!). 물론 코드를 외워서 따라하는건 할 수 있다. 하지만 난 암기보단 이해를 하고싶다. 예를들어 이런거다. 에라토스테네스의 체를 구현할 때 최적화를 위해 입력 숫자(n)의 제곱근(sqrt(n)) 까지만 확인한다. 이걸 이해해서 사용하기 전까지는 암기해서 사용하게 된, 어쩌다가 발견한 시간복잡도를 줄일 수 있는 정보였다. 하지만 중간에 한번 증명과정을 이해했고, .. 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.

티스토리툴바