알고리즘

[C++] 백준 1074번 Z

1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 www.acmicpc.net 재귀 / 분할 정복 문제. 처음에 풀었던 풀이가 시간초과가 나서 게시판의 도움을 받았다. 게시판의 도움을 받고, 어디가 시간초과가 나는지 알아서 바로 해결해서 제출했더니 맞출 수 있었다. 비효율적이지 않다고 생각했는데도 비효율 적이였다... 시간 줄이는 것은 너무 어려운 일 같다. 문제풀이 문제에서 2^n, 재귀라는 말이 주어졌으므로 분할 정복으로 풀어야 한다. 그렇다면 어떻게 분할해서 풀어야 할까? 처음에는 2 x 2 사이즈가 되기 전까지는 계속해서 분..

[C++] 14891번 톱니바퀴

14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 문제가 길어서 링크로 대체하겠다. 특별한 알고리즘 없이 톱니바퀴 4개가 회전하는 조건을 고려해서 회전을 구현하면 된다. 특별히 어려운 것은 없는 문제이다. 문제풀이 톱니바퀴에 대한 조건들은 다음과 같이 정리할 수 있다. 톱니바퀴는 1번부터 4번까지 총 4개가 있다. 톱니바퀴는 총 8개의 극이 있는데, N극 혹은 S극이다. 하나의 톱니바퀴가 회전할 때, 맞물린 톱니바퀴들과 맞닿은 극이 서로 다른 극이라면 맞물린 톱니바퀴를 회전하고, 서로 같은 극끼리 있다면 맞물..

[C++] 9020번 골드바흐의 추측

골드바흐의 추측은 예전에 학교 정수론 강의에서 들었었다. (사실 기억이 어렴풋이 나는거라 자세히는 기억이 안난다.) 2보다 큰 짝수는 무조건 두 소수의 합으로 표현이 된다는 것이 골드바흐의 추측이다. 그리고 차이가 가장 적게 나는 방법으로 두 소수를 찾으면 된다. 처음에 풀었는데 시간이 1976ms가 나와서 다른 풀이를 찾아봤다. 24ms만 초과했어도 시간초과였다. 잘못된 방법으로 풀었기 때문에 다른 풀이로 풀었는데 0ms가 나왔다. 문제풀이 처음의 내가 푼 방식의 코드부터 보여주겠다. #include #include #include using namespace std; int testCase, num; int ans1, ans2; bool primeCheck[10001]; // true라면 소수아님. ..

[C++] 백준 16236번 아기 상어

구현 / 시뮬레이션 + BFS(너비 우선 탐색) 문제. 테스트 케이스가 상당히 많고 잘 돼 있어서 디버깅을 하다보면 맞출 수 있다. 처음에 4번째 테스트 케이스가 자꾸 다른 값(60이 아니라 56)이 나와서 뭐가 잘못됐는지 모르겠어서 백준 게시판에 봤더니 고려해 주지 못한 부분이 있었다. 아마 테스트 케이스들만 올바른 방향으로 통과한다면 맞출 수 있을 것이다. 문제풀이 아기상어는 다음과 같은 조건을 갖는다. 이동은 상, 하, 좌, 우 방향으로 가능하다. 이동하는데는 1초의 시간이 소요가 된다. 처음 아기상어의 크기는 2이고 자신의 크기만큼 물고기를 먹으면 크기가 증가한다. 자신의 크기보다 큰 물고기가 있는 곳은 지나가지 못하고, 같은 물고기가 있는 곳은 지나가기는 가능하며, 더 작은 물고기가 있는 곳은 ..

[C++] 백준 11048번 이동하기

처음에 그래프 탐색 문제인 줄 알았던 문제. 알고보니 다이나믹 프로그래밍 문제였다. DFS로 구현하려고 하니까 시간 초과가 났다. 생각해 보면 최대 정점의 개수가 1000 x 1000 해서 1,000,000개가 되는데 각 점마다 3번의 메서드를 호출하게 된다. 이렇게 되면 3^1000000이므로 시간초과가 날 수 밖에 없다. DP인 것을 알고나면 쉽게 해결할 수가 있다. 문제풀이 DP의 관점에서, 각 칸의 도달할 수 있는 경우는 다음 세가지이다. y, x의 좌표로 부른다고 할 때, (y - 1, x)에서 (y, x) : 이전 칸이 위에서 아래로 이동한 경우 (r + 1, c) (y, x - 1)에서 (y, x) : 이전 칸이 좌측에서 우측으로 이동한 경우 (r, c + 1) (y - 1, x - 1)에서..

[C++] 백준 14499번 주사위 굴리기

구현 / 시뮬레이션 문제. 처음에 어떻게 방향들을 나눌 수 있을까 고민을 많이해본 것 같다. 주사위의 주변칸들이 어떻게 구성되는지 알 수 있다면 쉽게 풀 수 있다. 그리고 이 문제를 2번 틀렸는데, 문제에서 좌표가 (x, y)로 구성돼있다. 입력도 x y순서로 입력받는데 사실 이는 y좌표와 x좌표를 순서대로 입력받는 것과 마찬가지이다. 이 부분을 고려하지 못해서 틀렸다. 문제풀이 조건에 윗 면이 1이고, 동쪽을 바라보는 방향이 3인 상태로 놓여져 있다고 되어있다. 그런데 어차피 윗면이 1이든 6이든, 모든 주사위의 칸은 처음에 0이므로 아랫면을 1로 설정하고 풀어도 상관없다. 1이든 6이든 동쪽을 바라보는 방향이 3인 것만 유지시켜주면 된다. 그리고 예제 입력 1을 예로들면 좌표는 다음과 같은 형태이다...

[C++] 백준 2580번 스도쿠

2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 백트래킹 문제. 골드 4문제였는데 생각보다 너무 쉽게 풀렸다. 백트래킹 알고리즘을 사용해서 그런건가? 백준의 티어는 정말 알 수가 없다. 어떤 문제는 실버문제여도 오래 붙들고 있어도 안풀리는데, 이런 문제는 금방금방 쉽게 풀린다. 근데 또 정답률은 낮다...흠... 나도 사실 정사각형 3x3 고려를 하지 못해서 틀렸었다. 아마 나도 운이 좋아서 시간초과에 안걸려서 맞춘 것일 수도 있을 것 같다. 문제풀이 스도쿠게임을 완성시키돼, 백트래킹 알고리즘을 사용해서 구현..

[C++] 2294번 동전 2

다이나믹 프로그래밍 문제. 분명 동전 1을 풀었었는데, 풀이가 잘 생각이 나지 않아서 예전에 블로그에 썼던 글을 살짝 보고 풀었다. 문제가 비슷하긴 한데 동전 1은 경우의 수의 개수를 묻는 문제라면 이 문제는 어떤 경우의수가 나오는지를 묻는 문제였다. 물론 동전 1의 풀이를 안다면 쉽게 풀 수 있었을 것 같다. 처음에 동전의 가치가 100,000보다 작거나 같은 자연수 라는 조건을 읽지 못해서 틀렸었다. 이 말의 뜻은, 동전의 가치가 원하는 값보다 클 수 있다는 것을 의미한다. 문제풀이 n가지 동전이 있을때, 각 동전을 몇 가지를 사용하는지를 나누어서 계산하면 된다. 테스트 케이스를 예시로 들자면, 1만 사용했을 때 1 2 3 4 5 6 7 ... 1개 2개 3개 4개 5개 6개 7개 1, 5를 사용했을..

[C++] 백준 1699번 제곱수의 합

수학적 사고를 묻는 다이나믹 프로그래밍 문제. 결국 풀지못하고 구글링해서 답을 보고 나서야 이해를 했다. 수학에 많이 약한 것 같다. 특별히 어려운 것은 없어보인다. 근데 이렇게 생각해 내는 과정이 너무 어려운 것 같다. i번째의 수에서 제곱수들을 빼 주어서 제곱수는 한 개이므로 하나를 더해주고 원래값과 대소비교를 해 주는 방식이다. 뭔가 계속 고민했어도 생각 못했을 것 같다. 정수론 / 수학의 문제이므로 문제를 풀이한다기보다는, 따로 정리를 하고 싶어서 올렸다.

[C++] 백준 9465번 스티커

다이나믹 프로그래밍 문제. 엄청 오래전에 풀었던 기억이 있는데, 사실 그 땐 못 풀어서 블로그에 검색해서 이해도 못하고 그냥 코드 제출해서 맞았었다. 지금은 새로 풀었는데 초기화 안해서 한 번 틀리고 맞췄다. 문제풀이 어려운 문제는 아니였다. Bottom Up 방식을 사용해서 각 칸에 도달했을 때, 어떤 경우가 최대가 될 수 있을지를 생각해보면 된다. ... 2 1 O ... ... ... 2 1 O ... O에 갈 수 있는 경우의 수를 봐보자. 여기를 가로기준 i번째라고 한다면 각 칸에서 최대값을 기록하는 배열을 dp배열이라고 하고 각 칸의 값을 기록하는 배열을 sticker 배열이라 하고 max(A, B)를 A, B중 더 큰값을 반환한다고 하자. dp[1][i] = max(dp[2][i - 1], d..