문제 https://www.acmicpc.net/problem/16927 16927번: 배열 돌리기 2 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net 문제 풀이 정말 싫어하는 문제의 부류이다.. 배열 회전, 뒤집기 같이 수학과 같이 사용해야 하는 문제는 정말 까다로운 것 같다. 해당 문제의 특이점은 배열 전체를 회전시키는것이회전시키는 것이 아닌 각 인덱스의 원소들을 회전시키는 것이다. 통째로 회전하는 것과 소용돌이처럼 회전시키는 것은 아예 다른 ..
문제 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 문제 풀이 접근 방법에 대해서 많은 고민을 했다. 우선 지역구를 나누는 방법에 대해서 고민을 했는데, 조합을 써서 A와 B 지역구를 나누기 브루트포스로 나누기 두 방법 모두 하나의 지역을 정하면 나머지 구역의 지역을 결정 지을 수 있다. 브루트포스보단 코드적으로 깔끔한 조합을 사용해서 구역을 나눴다. 구역을 나눴다면 이젠 나눈 구역의 지역들이 연결되어 있는지를 확인해야한다. 여러 방법이 있지만 나는 BFS를 이용..
문제 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 문제 풀이 처음에 N개의 행성을 받아서 Prim 알고리즘을 사용해서 구현했었다. 그렇게 하다보니 메모리초과가 발생했다. 도저히 이유를 알지 못해서 질문게시판을 참고했다. 정점의 개수가 N개고, 최대 입력개수가 100,000개인데 모든 행성간의 간선 정보를 포문으로 계산할 시 메모리 초과가 발생하는것이었고, 메모리초과를 해결하기 위해서 간선을 최적화해서 수를 줄..
문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 풀이 전형적인 그래프 탐색 문제이고, 그래프 내에서 구역을 그룹핑하는 문제이다. 문제에서 요구하는 바는 하나의 그래프를 두 가지 방식으로 그룹핑하는것이다. RGB 각각의 컬러를 구별할 수 있는 영역(적록색약 X) RGB 중 R과 G를 하나의 영역으로 처리하는 영역(적록색약 O) 여러 가지 방식이 있겠지만, 두 번의 탐색을 통해서 각 영역을 구별했다. public static bo..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/92335# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 N에 대한 k진수를 구하고 소수 판별에 대한 최적화만 할 수 있다면 쉽게 풀 수 있는 문제이다. 1번 테케에서 틀렸던 사람들은 자료형을 바꾼다면 아마 통과할것이다. 기본적인 k진수 구하기 알고리즘은 k로 나눈 나머지를 저장해서 거꾸로 바꾼다면 아마 그것이 N에 대한 k진수일것이다. 문제에서 요구사항은 N으로 끊어서 그 수가 소수인지 아닌지만 판단하면 된다. 추가적으로 N에 0이 ..
문제 https://www.acmicpc.net/problem/20181 20181번: 꿈틀꿈틀 호석 애벌레 - 효율성 꿈틀꿈틀 호석 애벌레는 N 개의 먹이가 일렬로 나열된 나뭇가지를 오른쪽으로 기어가려고 한다. 시작하는 순간의 호석 애벌레가 0의 위치에 있고 i 번째 먹이는 오른쪽으로 i 초 기어가야 도달할 www.acmicpc.net 문제 풀이 문제를 읽어보니 누적합의 최댓값을 구하는 문제라고 생각을 했다. DP 문제인줄 알았지만, 탐색하는 과정에서 시간이 오래 걸려서 투 포인터 알고리즘을 사용하기로 했다. 투 포인터 알고리즘을 사용했기 때문에 start와 end를 움직이면서 탐색을 진행한다. 기존의 투 포인터 문제들은 누적합을 넘어선 순간 start를 증가시키고, 누적합을 넘지 못한다면 end를 증..
문제 https://www.acmicpc.net/problem/20366 20366번: 같이 눈사람 만들래? 높이가 (2, 5), (3, 5)로 구성된 눈사람 둘을 만드는 것이 최적의 경우 중 하나이다. |7-8| = 1 다른 경우로는 (2, 9), (5, 5)로 두 눈사람을 만드는 경우가 있다. |11-10| = 1 www.acmicpc.net 문제 풀이 4가지 경우의 수를 모두 구한다면 아마 시간 초과를 피할 수 없을 것이다. 해당 문제도 투 포인터 알고리즘을 사용해야 한다. 눈사람을 4개 골라야 하는데 투 포인터 알고리즘으로 어떻게 하냐~~ 할 수 있는데 세 용액 문제와 동일하게 탐색 숫자를 줄여주면 된다. 4개를 골라야 한다면 이미 2개를 고르고 나서 나머지 2개에 대해서 투 포인터 알고리즘을 사..
문제 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 문제 풀이 투 포인터 알고리즘의 대표적인 예시 문제라고 할 수 있습니다. https://jja2han.tistory.com/284 투 포인터 알고리즘(Two Pointer) 알고리즘 스터디를 하다가 새로운 알고리즘을 발견해서 호다닥 공부해서 정리하는 "아주 주관적인" 글입니다. 🔎투 포인터 알고리즘을 쓰는 이유 완전 탐색을 할 경우 시간초과를 피하기 위해 jja2han...
문제 https://school.programmers.co.kr/learn/courses/30/lessons/150367# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 문제를 읽어도 전혀 이해가 가지 않았다. 주어진 이진트리가 뭐지? 무슨 규칙이 있는 건가? 싶어서 무작정 문제에 대한 예시를 그려보았다. 우선 문제에 대한 예시로 나온 숫자들을 2진수로 바꾸면 다음과 같다. 그리고 문제에서 포화 이진트리로 생성해야 했기에, 0을 채워줬다. 포화 이진트리는 깊이가 n일때 노드의 개수는 2ⁿ -1으로 맞춰줘야 한다. 따라서 42와 63 모두 깊이가..
