#알고리즘 28
codeforce vs leetcode vs 백준
알고리즘을 잘하기 위해선 어떻게 해야할까
운영체제에서는 어떤 알고리즘이 쓰일까?
알고리즘을 공부하면서 생긴 의문점 해소하기
소프티어 7726: 나무 섭지
자율 프로젝트 기간에 준비하는 코딩테스트
백준 2295: 세 수의 합
알고리즘 재활훈련 1주차
백준 1563: 개근상
알고리즘 감각 되살리기 프로젝트 1주차
백준 2922: 즐거운 단어
알고리즘 재활 훈련 2일차
백준 16946 : 벽 부수고 이동하기 4
문제 링크문제의 조건을 보면 간단한 BFS같이 보이지만, 실제로 구현하면 시간초과가 난다.안에서 문제의 조건을 미리 계산하고 중복을 제거하는 자료구조를 사용해야만 시간초과를 해결 할 수 있는 문제였다!BFSO(N^2)해결 로직은 생각했지만, 중복 제거를 구현하는데 H
백준 7579 : 앱
문제 링크 DP로 결과값을 배낭문제처럼 분할해서 접근했다!Memory의 범위가 매우 넓고, 문제 메모리 조건이 128MB로 작기 때문에, cost를 기준으로 잡고 DP 공식을 만들었다!DPO(N)그리디 접근방식에서 틀린걸 깨닫고 DP 방식으로 다시 접근했다없을 것 같다
백준 15681 : 트리와 쿼리
문제 링크인접 리스트를 순회하는 방식만 구현하면 된다고 생각해서, DFS나 BFS로 접근했다DFSO(V+E)처음에는 메모리를 고려하지 않고 BFS를 사용했다가 메모리 초과가 난 이후에 DFS로 바꿨다!DP도 가능할 것 같다!
백준 2239 : 스도쿠
문제 링크처음엔 DFS 재귀 방식으로 접근했는데 계속 값 초기화 부분에서 오류가 났다난이도를 보고 쉬운줄 알고 접근했는데, 시간안에 풀지 못했다...결국 이번 문제는 정답을 참고해서 풀었고, 다음에 다시 한번 풀기로 했다.백트래킹최악 O(9^N^2)추후 다시 풀어볼 예
백준 2473: 세 용액
문제 링크어제 풀었던 투 포인터의 응용 문제로,N의 범위를 보니 포인터를 하나 더 늘리기만 하면 되겠다고 생각했다!투 포인터O(N^2)없다!없을 것 같다!
백준 2467: 용액
문제 링크이미 정렬이 되어있는 용액의 최소 절댓값을 구하는 문제로, 투 포인터를 사용하면 되겠다고 생각했다!투 포인터O(N)처음에 초기값을 MAXVALUE로 안해줘서 틀렸는데 바로 고쳐서 맞았다!없을 것 같다
백준 1799: 비숍
문제 링크처음에는 제한시간이 10초 + 모든 공간을 다 봐야한다고 생각해서 DFS로 접근했다.또한 비숍은 바로 옆의 칸 체스판의 흰색과 검은색칸은 가지 못하므로 2가지 경우로 나누어서DFS를 돌리면 되겠다고 생각했다!깊이 우선 탐색 DFSO(N^2)2가지 경우로 처음에
백준 20040: 사이클 게임
문제 링크사이클 유무를 판단해야하므로 Union Find로 그룹화가 되었는지 확인하면 된다! 유니온 파인드 Union FindO(N+M) V+E한번에 풀었다!없을 것 같다!
백준 2623: 음악프로그램
문제 링크주어진 좌표 가수 연결 정보의 순서를 검사해서 출력하면 되므로 그래프의 순서를 탐색하는 알고리즘인 위상 정렬을 사용했다!위상정렬O(V+E)간만에 한번에 맞아서 좋다!없을 것 같다!
백준 1202: 보석 도둑
문제 링크먼저 가장 많이 가져갈 수 있는 가격을 구해야하고, 조건에 맞추어 가방 무게를 검사해야하는 문제다.따라서 처음에는 가방을 크기순으로 내림차순 정렬, 보석은 무게순으로 내림차순 정렬한 이후들어갈 수 있는 최대한의 가치를 가진 보석을 pq 우선순위큐로 골라서 합산
백준 1647: 도시 분할 계획
문제 링크그룹화를보고 일반적인 MST에 마지막 한단계만 더 생각하면 될 것 같았다!MST 최소신장트리O(NlogN)Union할때 find 되지 않은 값을 합쳐줘서 틀리는 문제가 있었다..바로 수정해서 통과했다!없을 것 같다!
백준 2096: 내려가기
문제 링크처음에는 일반적인 브루트포스인줄 알고 DFS, 또는 BFS를 사용하려 했지만입력 범위와 메모리 조건을 보니 일반적인 완전탐색으로는 안될 것 같았다.따라서 DP로 접근하기로 했다!DP 동적 프로그래밍O(N)없다!어떻게 로직을 잘 자면 메모리를 더 줄일 수 있을거
백준 1043: 거짓말
문제 링크파티의 수와 거짓말을 판단해야하므로, 그룹화 Union Find 알고리즘을 사용하면 되겠다고 생각했다!유니온 파인드 Union FindO(NlogN)처음에 아무생각없이 find값들을 서로 비교하지 않고, 초기값과 find값을 비교해서 틀리는 문제가 있었다.그룹
백준 1753: 최단 경로
문제 링크일반적인 최단 경로 문제이므로 다익스트라를 사용했다!다익스트라 DijkstraO(V+E)pq에 넣을때 최적화된 값을 넣지 않아서 시간초과가 나는 오류가 있었다...고쳐서 바로 해결했다!이미 pq를 사용해서 없을 것 같다!
백준 15311: 약 팔기
문제 링크100만 까지의 수를 특정 숫자의 합으로 나타내는 문제이다.처음에는 범위가 2000까지여서 1부터 2000까지 전부 더해봤는데 100만이 넘었다.그래서 1부터 차례대로 넣고 뽑는 식으로 구현할려 했는데, 연속된 범위가 발목을 잡았다..100만까지의 수를 표현하
백준 5430: AC
문제 링크조건에 맞추어 문자열을 파싱해서 출력한다!구현O(N)처음에는 아무생각없이 일반 구현인 줄 알고 회전 명령이 들어오는대로 처리를 했더니 시간초과가 났다...일괄적으로 명령을 받아 범위만 확정지은 후에 파싱하는 방법으로 해결했다!또한 O(N)의 시간 복잡도를 유지
백준 1884: 고속도로
문제 링크 created : 2024-06-07 문제 떠올린 접근 방식, 과정 시작점이 정해진 최단경로이므로 다익스트라를 사용한다! 하지만 조건이 두개 이상이기 때문에 한가지 기준에 따른 다익스트라를 돌린후, 조건에 맞추어 순회해서 정답을 구한다. 알고리즘과 판
백준 1938: 통나무 옮기기
문제 링크최단경로이므로 BFS에 기본 로직들에 맞춰 조건을 구현했다.BFS최단경로니까!O(N^2)방문처리를 한 조건에 안해줘서 메모리 초과가 났었다.바로 추가해줘서 해결했다!더 깔끔하게 리팩토링은 가능할 것 같다..
백준 26606: 이게 게임이냐?
문제 링크기본 로직은 BFS로 pq에 카드 게임 진행상황과 현재 카드 소비수를 같이 넣어서, 카드 소비수를 내림차순 기준으로 뽑아내고, 카드를 넣을 수 있는 모든 곳의 수를 탐색해서 게임 성공 유무를 판단한다.BFSO(NlogN)처음에 구현할 때는 손패를 고려안해서
백준 1914: 하노이 탑
문제 링크N개의 하노이탑을 옮기려면 N-1개의 탑을 빈 공간에 옮긴후, 제일 큰 탑을 목적지로 이동 후, 다시 빈공간에서 목적지로 N-1개를 옮겨야한다.이는 N 개의 하노이 탑을 옮기기 위해서 N-1개의 하노이 탑을 옮기는걸 총 2번 반복해야된다는 소리고, 이는 재귀로
백준 20926: 얼음 미로
문제 링크최단경로이므로 기본적으로 BFS로 조건에 맞게 탐색한 후, 시간 복잡도 최적화를 위해 check 배열을 사용해 최소값을 갱신한다.다익스트라(Dijkstra)우선순위 큐로 최적화 시켰으므로 O(NlogN)해당 부분을 check 배열로 잘못써서 계속 시간초과가 났
백준 26609: 험난한 등굣길
문제 링크문제의 범위가 3000이고, 해당 조건의 교통체중을 전부다 BFS로 일일히 돌리면 시간초과가 난다. 따라서 교통체중의 경계값만 표시하고 학교를 가는 최소값은 다익스트라를 사용한다.다익스트라구현우선순위큐로 최적화를 시키지 않았기 때문에O(N^2)일반 BFS로 해