IT recording...

https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net [문제 풀이] - 역시 삼성의 구현 문제 답게 별 알고리즘은 필요없고 문제 꼼꼼히 읽고 구현하는 문제 - 정말 별로다 너무 디버깅이 힘들다 ㅜㅜ - 나는 톱니가 1,4번이면 각각 2번,3번만 체크하면 되고 2,3번이면 각각 1,3번, 2,4번을 체크해야 하는 것을 보고 재귀 짤바에야 톱니 4개밖에 없으니까 그냥 if문으로 각각 경우 다 해주는게 나을것같다고 생각했다. - 근데 주의할점, 이렇..

https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net [문제 풀이] - 조건이 매우 까다로운 구현 문제였다. 처음 문제 읽고 난독증와서 완전히 이해 못함 - 경사는 무조건 '낮은칸'에만 설치한다. - 경사가 높아지는지, 낮아지는지의 경우의 수를 나누어 풀이한다. - 경사를 설치한 곳에 또 설치를 할 수 없기 때문에 visited 배열을 활용한다. * 높이 차 > 2 -> fail * 높이 차 ==0 -> 그냥 한 칸 증가 * 높이 차 ==1 * 경사가 높아지는 경우 : 이..

[원문링크] https://adorable-aspen-d23.notion.site/PG-6b703aa604e64d19a8b75904ba71d2fc [PG] 정수삼각형 코드 adorable-aspen-d23.notion.site 코딩테스트 연습 - 정수 삼각형 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr [풀이] 처음에 dfs로 했는데 시간초과났다! (dp카테고리에 잇는 거라서 무조건 날 줄 알긴했는데, dfs로 풀고 그거를 top-down으로 바꾸려고 그냥 풀어봄) 근데 바꾸려니까 완전 헷갈리기.. top-down으로 바꿀 때 제대로 이해 못하고 결국 구글링해서 살짜쿵 참고해서 풀..

[원문 링크] https://adorable-aspen-d23.notion.site/PG-c556306cdc3440e58031178200b40e55 [PG] 전화번호목록 코드 adorable-aspen-d23.notion.site 코딩테스트 연습 - 전화번호 목록 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr [풀이] hash라고 되어 있지만 문제 보자마자 트라이 사용하는 것 같아서 트라이 사용해봤다. 근데 런타임에러 자꾸 나ㅡㅡ 메모리 초과인가 싶어서 처음에 TrieNode에서 child 배열로 사용하..

[원문링크] https://adorable-aspen-d23.notion.site/BOJ-2573-fd58e2125704471dbe1e295133cc8926 [BOJ] 2573 빙산 코드 adorable-aspen-d23.notion.site 2573번: 빙산 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net [풀이] 처음에는 union-find로 부모를 관리해야 하는 건 줄 알았는데 하다보니 점점 미궁속으로 빨려들어갔다. 이에 답을 참고하기로 결정 ㅠㅠ 답을 보고 dfs를 활용한 단절점 문제와 비슷한 방..

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net [원문링크] https://adorable-aspen-d23.notion.site/BOJ-7569-6da8db8f25b64ecc86dde5dc4192d83e [BOJ] 7569 토마토 코드 adorable-aspen-d23.notion.site 풀이 최소 시간을 관리하는 문제로 , 토마토가 퍼져 나가는 방식이다. 토마토가 처음 있는 기본 상태에서 점점 퍼져나가며 맵이 변화하..

[원문링크] https://adorable-aspen-d23.notion.site/BOJ-2517-3bfb4962163f45d190eb99a4fc962f72 [BOJ] 2517 코드 adorable-aspen-d23.notion.site [풀이] 조건 : 나보다 index가 작은 애들 중에 나보다 실력이 안좋은 애들 수 인덱스 트리 담는 순서 : 실력이 안좋은 애들 순으로 넣기 index : 애들 index 그대로 value : 나보다 index가 작으면서 실력이 안좋은 애들 수 실력이 안좋은 애들부터 담으니까 그 앞에 몇개가 존재하는지를 찾으면 정답을 알 수 있다. [코드] import java.io.BufferedReader; import java.io.FileInputStream; import ja..

[원본링크] https://adorable-aspen-d23.notion.site/BOJ-2014-f2f38c50eb9b490284b602995b8a7472 [BOJ] 2014 코드 adorable-aspen-d23.notion.site [풀이] 주어진 소수를 이용하여 곱으로 만들 수 있는 수들 중 N번째 수를 구하는 문제이다. 배열을 계속해서 정렬 시켜주면 시간초과가 날 것이므로 priority queue를 사용하는 문제임을 떠올렸다. 처음에 중복 제거를 위해 pq.contains 함수를 사용했는데, 시간초과가 났다. O(N)의 시간복잡도를 가지기 때문인 것 같다. → 중복 제거를 위해 modulo 연산을 사용했다. [코드] import java.io.*; import java.util.*; publi..

[원본 링크] https://adorable-aspen-d23.notion.site/BOJ-2904-bd671fa7811442e38f73bf58f483a75f [BOJ] 2904 코드 adorable-aspen-d23.notion.site 2904번: 수학은 너무 쉬워 2904번: 수학은 너무 쉬워 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100) 둘째 줄에는 종이에 적혀있는 수 N개가 주어진다. 수는 모두 1,000,000보다 작거나 같은 양의 정수이다. www.acmicpc.net [풀이] 처음에는 수가 1,000,000 (백만)이라 소인수분해가 아니라 다른 방법으로 풀어야 할 것이라고 생각했지만 마땅한 방법이 떠오르지 않았다. 근데 백만정도면 소인수분해 해도 되는 수인가보다(민망) 모든 자연수는 ..

Segment Tree(세그먼트 트리) 부분합을 선형 계산을 통해 구하려면 O(N)의 시간이 걸린다. 그 후 특정 부분합을 구하려면 O(1) But, 노드의 값이 빈번히 update된다면 어떨까? → 원소의 개수가 N개인 배열이 있을 때 첫번째 값이 M번 변경된다면 O(MN) 번의 시간복잡도가 필요하다. ⇒ Segment Tree를 이용하면 O(logN)의 시간 복잡도 내에 부분합을 구할 수 있다. : 이진 트리를 바탕으로 트리를 구성하며, update를 해야 할 부분만 업데이트 할 수 있다. leaf 노드는 배열이 가지는 값을 가지게 된다. 이외의 노드들은 부분합 등 특정 조건을 만족하는 조건으로 이루어진다. 트리의 최대 노드 개수 def segmentation_size(node): height = i..