알고리즘/Baekjoon

[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..

[C++] 백준 2206번 벽 부수고 이동하기

그래프 탐색 문제. 최단 거리를 탐색하는 문제로, BFS를 응용해서 풀면된다. 조건을 따지지 못해서 검색을 했는데, 코드를 약간 수정해서 맞출 수 있었다. 처음에 이 문제를 접근했을 때 N x M의 맵이고, 벽은 1이고 땅은 0이다. 그리고 상, 하, 좌, 우를 이동할 수 있다. 1로 된 곳 중 하나를 부숴서 갈 수 있다. 나는 다음과같은 조건들을 고려했다. BFS로 점들을 이동하며, 내가 이 점에 왔을 때 벽을 부수고 온 것인지 아닌지를 고려했다. 만일 이전에 벽을 부수고 왔다면, 이번 정점에서는 벽을 가지 못하도록 했다. 이전에 벽을 부순적이 없다면, 벽을 부쉈다는 것을 기록하고 해당 벽을 방문한다. visit 2차원 배열을 만들어서 해당 지점을 방문한 것을 저장했다. 빨간색으로 칠한 이유는 저 부분..

[C++] 백준 2447번 별 찍기 - 10

분할 정복 / 재귀 문제. 알고리즘 분류를 보고나서, 이 문제를 어떻게 분할 정복 / 재귀로 풀 수 있을까 하는 생각을 많이 했던 것 같다. 규칙을 찾으면 쉽게 풀 수 있던 문제였다. 문제풀이 그동안 백준에서 풀어왔던 분할 정복 / 재귀문제는 색종이 자르기와 같이 자기 자신과 같거나 다르면 나누는 문제였다. 그래서 이 문제를 보았을 때 처음에 어떻게 분할해서 나눌수 있을까 생각을 많이했다. 위처럼 그림을 다 그려보고(9x9 그려서 복붙했다.)나서 어떻게 일반화할 수 있을지 생각해보았다. 그리고 어떤 조건에서 '*'이 그려져야 하고, 어떤 조건에서 ' '이 그려져야 하는지 생각해보았다. 아무리 생각해도 조건이 그려지지 않았다. 그래서 다르게 생각해 보았다. 어떤 경우에 공백이 그려져야 하는가? 공백이 나오..