실수가 너무 잦았던 문제.헷갈렸던 개념range(0, n)은 0 부터 n-1 까지 이다.풀이조건을 위해 전체 합을 투 포인터로 빼준다.
문제 풀이 투포인터
매우 쉽게 풀었으나 범위 설정 문제가 있었음.풀이 최대에 집중. 서로 다른 n 개의 합이 10이라고 할 때, 최대 n 구하는 것을 생각해보자.1,91,2,71,2,3,42,8...즉 최대 n은 가장 작은 수 부터 차례로 더한 것이다.ps 로 낮아진 자존감은 ps로 풀어
이진 탐색 기초 문제전역 변수 지역 변수에 대해 미숙해 구현에 애먹었다.
이진 탐색 기초 문제https://www.acmicpc.net/problem/2805 와 매우 유사하다.문제에서 주어진 '단, 항상 N ≤ K 이다.' 가 중요한 힌트. 핵심을 하나씩 체크하자.조금씩 내 알고리즘 실력이 느는 느낌이다.
문제를 어떻게 완탐을 할 수 있을 지 고민하는 게 중요.뭔가 사람이 푸는 것 처럼 풀려고 하면 꼬인다.
이차원 배열일 때 구간합을 어떻게 구할 지 고민하게 해준 문제이다. 문제의 핵심은 다음과 같이 나뉜다. 입력 받은 값들을 누적합으로 만들기누적합으로 만든 배열 이용해 (x2,y2),(y1,x1) 까지의 합 구하기입력 받은 값을 누적합으로 만들려면 리스트 패딩을 이용하면
imos를 사용 하여 풀었다. 메모리 부분은 dic으로 해결 하였다. 1차원 배열에서 imos는 출입때 +1
배열의 누적합을 구하고 그 누적합의 나머지를 저장한다.나머지가 같은 구간을 처리하는 것이 문제 핵심서로 다른 두 구간을 선택 nC2 이다.
쉬운 정수론 문제https://www.acmicpc.net/problem/2824math.gcd로 간단히 풀었다.다만, 이러면 정수론 연습이 안되서 유클리드 호제법을 두 가지 형태로 구현하는 법을 연습 했다.다만, 재귀로 구현한 gcd를 이용해 이 문제를 풀려
0~9 숫자를 정해진 부등호에 맞추어 나열하는 문제순열인것을 파악하는 것이 중요하다.재귀를 통해 문제 조건에 맞는 값을 도출하였다.
순열 구현하여 문제를 풀었다.https://www.acmicpc.net/problem/10819모듈도 이용해 봤다.
문제 접근 모든 경우의 수를 보는 방식을 사용했다. 1 2 3 4 5 6 7 8 9 o o oo o xo x oo x xx o ox o xx x ox x x이런 식으로 풀고자 했으며 모든 경우의 수를 보는 코드를 먼저 작성해 봤다.경우의 수가 5의 10승이기 때문이다.
숫자 1개수 0개수0 0 11 1 02 1 13 2 14 3 2...나열해보니 n의 0의 개수는 n-1과 n-2의 0의 개수와 같고n의 1의 개수 역시 그러하다는 걸 알게 되었다.이를 이용해서 먼저 모든 수들의(문제에
케이스를 깔끔하게 나누어 봐야함을 알려준 문제. 100 과 비교했을 때 큰거 작은것, 안눌리는 버튼의 개수가 0일때 아닐때이렇게 나누어 보면 쉽게 풀 수 있다.
CS 스터디에서 union-find를 학습한 김에 풀어보았다.해당 알고리즘의 원리를 다시 되새기면서 구현 연습을 계속 해봐야겠다.
이제는 bfs를 공부할 때가 온거 같아 큐를 공부해보았다.https://www.acmicpc.net/problem/2164카드 2큐, 큐2https://www.acmicpc.net/problem/10845https://www.acmicpc.n
https://www.acmicpc.net/problem/25330 백트래킹을 활용해 풀었다. 재귀의 최대깊이를 어떻게 설정하는 것이 좋을 까? 재귀 가지치기를 어떻게 할까 고민을 하였다. 재귀의 최대깊이를 어떻게 설정하는 것이 좋을 까? 이 생각을 하면서 단순
https://www.acmicpc.net/submit/3184/49276284우리 안의 양과 늑대를 세는 문제우리가 어떻게 나뉘는 가를 생각한 후 DFS/BFS를 쓰면 해결된다.
문제 링크https://www.acmicpc.net/problem/2606DFS와 BFS 문제와 같이DFS/BFS 연습하기 좋은 문제. DFS 풀이BFS 풀이
기억하기이차원 visited 만들기get((), 1) 사용
✍배운것list 배열 만들고 해당 위치의 인덱스 값을 출력👍잘한점일단 구현 시도 해본 것. 항상 구현이 좀 귀찮을 것 같으면 그냥 넘어 갔다.딕셔너리를 활용한 visited 구현😅어려웠던점set을 활용해 중복인 답을 제거 할려 했으나 set이 순서를 보장 못해주는
발상이 재밌었던 문제💡idea물이 차오르는 것을 1, 2, 3, ... 으로 표시하고BFS로 최단 거리 탐색때 비버가 이동한 거리보다 물 차오르는 게 작으면 return
문제 링크: 숫자 고르기 개념 정리DFS의 의미는 연결요소!우리는 DFS를 이용해서 연결요소의 크기/개수를 구할 수 있고, 연결 요소의 정보에 대해 알 수 있다.배운 것DFS를 이용해 싸이클 확인 법.문제 해설 첫째 줄 수를 뽑았을 때 집합이 뽑힌 수들의 밑에 있는
모든 장소를 방문해서 최단 거리를 갱신.
문제 태그벽부수고 이동하기1: 링크벽부수고 이동하기2: 링크벽을 부순 상태를 배열에 추가 해주었습니다. 기존 이차원배열에서 벽을 부순 상태를 추가 해주었습니다.즉 벽을 하나 부술수 있는 경우 \[] 이고벽을 두개 부술수 있는 경우 입니다. 이를 고려 하여 코드를 짜면
📖접근 최단 거리 문제 -> BFS칼을 먹고 나서는 어떻게 할 것인가? 칼을 먹고 나서 기존에 칼이 없을 때 방문 한 곳을 또 방문해도 된다. 이를 고려 안하면 틀립니다. 그래서 칼이 있는 위치에서 BFS를 다시 돌리면 문제를 풀 수 있다.다만, 문제 관찰을 더 하면
\- 트리의 부모 찾기 👨💻문제 관찰 트리의 루트를 1이라고 할때 각 노드의 부모를 구하는 문제🔑문제 해설 첫째 줄에는 노드의 개수가 주어지고 둘째 줄 부터 N-1개의 줄에 트리의 상에서 연결된 두 정점이 주어 진다.
최단 경로👨💻문제 관찰 간선과 가중치를 가지는 그래프 문제 -> 다익스트라🔑문제 해설 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 임으로 nlogn 시간 복잡도를 가지는 다익스트라를 구현해야함. 이를
문제를 잘 관찰하자.조합 문제인데 왜 ... 순열로 풀었니... 그러니 맞왜틀 외치지..관찰 정말 중요하다.
문제 제목: 일곱 난쟁이링크: https://www.acmicpc.net/problem/2309관찰: 9명 중 난쟁이가 아닌 2명 찾기, 일곱난쟁이 키의 합은 100 , 일곱난쟁이를 출력문제 접근:일곱난쟁이 키의 합은 100인것을 활용예제를 보면 9명의 키의
문제링크: https://www.acmicpc.net/problem/2981문제 관찰: n개의 숫자가 주어짐. n개의 숫자를 m으로 나누었을 때 나머지가 모두 같게 되는 m찾기. 단 m은 1 보다 커야함.문제 분석: 완전탐색 접근 n개의 숫자 중 가장 작
최소 공배수, 최대 공약수에 대해 생각 하게 해준 문제.
도토리 숨기기!🐿️
문제 링크: 사이클 게임 문제 해설 싸이클을 이루게 하는 지점을 찾는 문제 Union Find로 싸이클을 이루는 지 계속 체크
매우 재밌었는 문제
문제에 있어서 관찰은 중요하다.
유니온파인드
DFS에 대한 이해와 DP에 대한 이해가 필요했던 문제.
백트래킹과 DFS