알고리즘 22

[백준 알고리즘] 2933번 - 미네랄 (구현, BFS)

1. 개요2시간 녹인 문제... 늘 내 블로그에 적는 말이지만 구현은 초반 설계가 잘못된다면 정말 힘든 문제인 것 같다. 여러 예외도 생각해야하고... 이래서 난이도 높은 문제들은 구현인가...? 싶기도 하다. 문제를 나누고 나올 수 있는 예외를 전부 처리해야 성공하는 문제이기에 시간도 많이 들고 힘도 많이 들었다... 출처: https://www.acmicpc.net/problem/2933 2. 본문내가 생각한 구현 문제의핵심은 다음과 같다. 물론 말 그대로 타고난 능력이 좋은 사람들은 저런 방법이 필요 없겠지만 말이다.. ㅋㅋㅋ1. 문제를 단계별로 나눈다.2. 예외사항을 처리한다.3. 구현- 문제 나누기 문제를 나누면 다음과 같다.1. 방향에 맞는 미네랄 제거.2. 떨어지는 미네랄 조사.3. 떨어질 ..

[programmers] 340211번 - 충돌위험 찾기 (구현, [PCCP 기출문제] 3번)

1. 문제 및 예제 문제를 제대로 읽지 않아 두바퀴 정도 뺑뺑 돌다가 해결한 문제다. 아까운 내 한 시간이 날아갔다. 이렇게 장문의 문제를 푸는 요령이라도 터득해야할 것 같다. 집중력 문제인 것 같기도해서 최근에는 시간을 정해두고 문제를 풀고있다. 이런 구현 문제는 지금 회사에서도 비슷한 일을 하는데 이렇게 시간이 오래 걸리다니... 충격적이긴 하다 ㅋㅋhttps://school.programmers.co.kr/learn/courses/30/lessons/340211 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr2. 본론 이런 복잡한 문제들은 문제를 나누고 ..

[programmers] 250136번 - PCCP 기출문제 2번(BFS, PCCP 기출문제)

1. 문제 및 예제 Level 2 문제들을 쭉 풀어가던 도중 PCCP 기출문제 두 문제가 공개되어 바로 풀어보았다. BFS 알고리즘이 핵심이지만, 더 빠른 알고리즘을 위해 범위를 저장하는 부분이 필요하였다. https://school.programmers.co.kr/learn/courses/30/lessons/250136 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이과정 시간 복잡도 때문에 BFS로는 풀 수 없다. O(N^3)이기 때문에 다른 방법을 생각해야 했다. 내가 생각한 방법은 다음과 같다. 아래와 같은 입력이 주어졌다고 가정하자. 이렇..

[프로그래머스] 17679번 - 프렌즈4블록 (구현, 2018 KAKAO BLIND RECRUITMENT)

1. 문제 및 예제 엄청난 구현 문제. 설계를 잘 하면 그렇게 어렵지 않게 해결할 수 있다. 중요한 점은 한 배열에서 사라질 모든 블럭을 찾아낸다는 것 같다. 블럭이 포함되어 있다는게 조금 까다로웠다. https://school.programmers.co.kr/learn/courses/30/lessons/17679 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이과정 문제를 나눠보았다. 1. 블록을 터트리고 터진 블록의 갯수를 반환한다. 2. 터진 블록을 아래로 내린다. 다음은 전체 코드이다. #include #include #include #in..

[프로그래머스] 17686번 - 파일명 정렬 (구현, 2018 KAKAO BLIND RECRUITMENT)

1. 문제 및 예제 간단하게 문자열을 다루는 문제였다. 문자열을 입력에 맞게 나누는 것은 어렵지 않았지만, 안정 정렬에 관한 지식이 있었어야 했다. C++같은 경우는 관련 정렬 함수를 지원해주었지만 미리 알지 않았으면 큰일날뻔 했다... https://school.programmers.co.kr/learn/courses/30/lessons/17686 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이과정 안정 정렬을 알고있으면, compare함수를 커스텀하여 풀 수 있는 문제이다. 문제를 다음처럼 쪼개보았다. 1. 문자열을 전부 소문자로 변경한다. ..

[프로그래머스] 72411번 - 메뉴 리뉴얼 (구현, 2021 KAKAO BLIND RECRUITMENT)

1. 문제 및 예제 programmers에서 단계별로 문제를 풀다가 만난 문제다. 처음 문제를 보고 이게 대체... DP인가... 백트레킹인가... 싶었는데 입력 크기를 보고 무조건 브루트포스구나 싶었다. O(N^2)의 조합 문제로 해결하였다. 중간에 set container가 말을 안 들어서 vector로 전환하는 과정에서 시간이 좀 걸렸다. 30분에서 40분 정도? 걸린 것 같다. https://school.programmers.co.kr/learn/courses/30/lessons/72411 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이과..

[프로그래머스] 68645번 - 삼각 달팽이 (재귀함수)

1. 문제 및 예제 이게 무슨 유형의 문제인가... 구현인가 싶었는데 재귀가 정답이었다. 배열에 그리는 문제를 전에 만나봐서 예외 처리 빼고는 어렵지 않게 설계할 수 있었다. 재귀함수 잘 쓰고 싶다.. 지금은 그냥 써야될 때 쓰는 수준? 책에서 본 알고리즘 풀이들은 재귀함수를 마치 무기처럼 자유자재로 쓰던데 그 경지에 도달할 때 까지 연습하고 싶다. https://school.programmers.co.kr/learn/courses/30/lessons/68645 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이과정 문제를 나누는게 참 중요하다는걸 ..

[백준 알고리즘] 1197번 - 최소 스패닝 트리 (크루스칼 알고리즘)

1. 문제 및 예시 실행 결과 solved.ac의 CLASS가 올라갈수록 모르는 알고리즘이 많다. 어제 토스 코테 한번 찍먹하고 많이 반성하게 됐다. 모르는 것을 공부하는게 맞는 것 같다. Union-find를 활용한 크루스칼 알고리즘을 공부하고 적용해보았다. 한큐에 초록 글자가 떠서 너무 좋았다. 출처: https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 2. 풀이과정 문제를 잘게 나눠봤다. 1. 문..

[백준 알고리즘] 2467번 - 용액 (투 포인터)

1. 문제 및 예시 실행 결과 투 포인터를 활용하는 문제... 나름 재밌었다. 보통 이런 경우는 이분탐색 처럼 구현을 하게 되는데 그 과정은 어렵지 않지만 어떤 문제로 접근해야하는지 찾는 과정이 이분탐색 혹은 투 포인터 문제의 핵심이라는 생각이 든다. 출처: https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 2. 풀이과정 문제를 잘게 나눠봤다. 1. 입력 2. 이분탐색 진행 왼쪽과 오른쪽으로 부터 시작하여 두 값의 합이 0보다 크면 음수쪽이..

[백준 알고리즘] 11779번 - 최소비용 구하기 2 (Dijkstra에서 경로를 출력하는 방)

1. 문제 및 예시 실행 결과 간단한 다익스트라 문제이지만, 경로를 출력해야한다. 처음에는 문자열을 옮기는 방식으로 풀었는데, 원인을 알 수 없는 이유로 틀렸다는 문자만 계속 떴다. 그래서 경로를 배열에 저장하는 방식을 사용했다... 문자열도 같은 원리인데 대체 왜 그러는지 참... 출처: https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 2. 풀이과정 문제를 잘게 나눠봤다. 1. 입력 2. 다익스트라 진행 3. ..