Algorithm37 1644 : 소수의 연속합 https://www.acmicpc.net/submit/1644/95941199오늘 푼 따끈따끈한 문제다.특히 한 번에 풀게 되어 기분이 매우 좋다. 앞으로도 계속 한번에 풀 수 있도록 조금 더 노력해야지. 이 문제는 소수의 연속합이라면서 소수를 알려주지 않는다.따라서 문제를 풀 때 소수를 필히 구해야 한다. 이때, 4백만이라는 완전 탐색에 다소 괴랄한 수가 있어 조금 걱정을 했으나, 아래와 같이 소수를 구할 경우 2중 for문에도 불구하고 O(nlogn)으로 결과를 뽑아낼 수 있을 거라고 생각했다.먼저 multiple로 증감자를 만든 후, 변화되는 수를 idx로 두게 되면idx의 시작점이 2인 경우, 2를 제외하고 4,6,8,10 등이 사라지게 된다.기본적인 원리는 에라토스테네스의 체다. 그렇게 소수를.. 2025. 7. 4. 백준 1766 : 문제집 https://www.acmicpc.net/problem/1766이번 문제는 문제집이란 것으로 시작점을 파약해야한다는 점문제를 푸는 순서가 존재한다는 점으로 미루어보아 위상 정렬로 문제를 접근했다. 그러나 초기 접근은 DFS로 접근을 했는데, 기초적인 위상정렬의 형태로는 문제가 풀리지 않았기 때문이다.이유는 진입 차수가 0인 것을 모두 Queue에 넣어 순서를 지키며 위상정렬을 하는 것이 기본적인 형태였다면, 여기서는 숫자가 작다면 더 빨리 풀 수 있는 조건이 있었기 때문이다.이 과정 때문에 PriorityQueue를 사용해서 순서를 지키며 문제를 풀었다. 구해야 할 것문제를 푸는 순서문제 풀이 순서1. 입력을 받으면서 a->b로 입력 시 b를 인덱스로 하는 진입 차수 배열 inOrder[b]를 증가한다.. 2025. 7. 2. 백준 2630 : 색종이 만들기 https://www.acmicpc.net/problem/2630 이번 문제는 백준 2630 색종이 만들기 문제이다.카테고리는 분할 정복으로 되어 있지만, 결국 접근해야할 문제 방법은 재귀다.재귀를 이용해서 색종이의 색이 일치하는지 안하는지를 확인해나가며 체크한다면 정답을 얻을 수 있다. 시간 체크를 안하기도 했지만, 단번에 풀어 큰 문제가 없다고 판단했다.^^ 구해야할 것흰 색종이와 푸른 색종이의 갯수방법1. 좌측 상단의 색종이 좌표와 우측 하단의 좌표를 구해 해당 색종이가 같은 색인지 확인한다.2. 만약 색종이의 색이 같다면 좌측 상단의 색을 구하고 해당 색을 더해준다,3. 색종이의 색이 같지 않다면 좌측 상단의 좌표와 우측 하단의 좌표를 이용해 색종이를 4개로 쪼갠다.이때 좌표는 좌측상단 좌표와 우.. 2025. 6. 25. 프로그래머스 : 숫자 게임 https://school.programmers.co.kr/learn/courses/30/lessons/12987 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr이번엔 숫자게임이다.조금 짧게 걸리긴 했으나, Hint를 보게 돼서 아쉬웠다. Hint를 참고하게 된 이유는 17번 T/C 때문이었는데, 해당 T/C는 두 수가 서로 같을 떄의 조건을 제대로 해결하지 않아서였다. 내 생각내가 생각했을 때는 등호 역시 승점을 얻지 않기에 이길 수 있는 가장 좋은 방법일 수는 있었다. 그러나 문제에서 원하는 것은 최대 승점으로 이 경우에도 가장 작은 숫자를 버리는 방법으로 접근해야혹시라도 그 다음 수보다 현재의 숫자가 클 때.. 2025. 6. 23. 프로그래머스 : 단어변환 https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr이번 문제는 프로그래머스 : 단어변환이다.최근 코딩테스트 전반으로 나오는 모든 문제를 다 풀어야 통과가 가능하므로 문제당 걸리는 시간을 줄여보고자 스탑워치를 사용하고 있다. 구해야할 것단어 변환에 걸리는 가장 짧은 Count 문제의 조건1. 하나의 알파벳씩만 바꿀 것2. 배열 내의 단어로만 바꿀 수 있다. 푸는 순서0.단어라는 특수성이 있는 만큼 Map을 활용1.배열 내의 target 단어가 없다면 0 반환2.Map에 넣는 함수를 써서 인접 맵을 채운다... 2025. 6. 23. 프로그래머스 : 등굣길 https://school.programmers.co.kr/learn/challenges?order=acceptance_desc&levels=3%2C4%2C5&languages=java 코딩테스트 연습 | 프로그래머스 스쿨개발자 취업의 필수 관문 코딩테스트를 철저하게 연습하고 대비할 수 있는 문제를 총망라! 프로그래머스에서 선발한 문제로 유형을 파악하고 실력을 업그레이드해 보세요!school.programmers.co.kr구해야할 것등굣길의 가짓수 -> 문제 훑고 최단거리라고 착각하지 말자. 그렇다면 DFS를 쓸 이유도, DP를 사용할 이유도 없다. 접근 방법얼핏 보면 DFS/BFS문제 같다.이 문제는 경로의 가짓수이므로 BFS를 제외한다. BFS를 제외한다면, 분명하게 DFS이다. 그렇지만 여기서 나.. 2025. 6. 8. 이전 1 2 3 4 ··· 7 다음 반응형