끄적끄적

[문제] https://www.acmicpc.net/problem/12100 [처음 생각] 삼성전자 작년 하반기 오전반 시험문제라고 알고있는데 아닐수도 있음! 블럭을 옮기는게 애매하다고 생각했다. 위쪽 방향으로 옮긴다면, 맨 위에서부터 생각해야하는데 옮기면서 그 다음 블럭을 앞으로 당겨줘야하는게 구현하려니 너무 복잡해졌다. 결국 소스 참고함... [풀이] 사진은 잘 보이지 않지만 내가 보기위해 정리용으로 올림! 전체 함수 구조를 봤을 때, main함수에서 moving함수를 호출하고 그 안에서 재귀호출하는 형태로 짰다. number라는 매개변수를 넣어서 5번까지만 돌아가는 것을 제한해두고 매번 5번까지 돌때마다 max_local을 구해서 결국 전체 max를 구하도록 한다. 방향은 네가지로 나눈다. 위/아래..

[문제] https://www.acmicpc.net/problem/13460 [처음 생각] 처음에는 맵을 보고 BFS로 풀어야겠다고 생각했는데, 빨간 구슬과 파란 구슬 모두를 움직여야 하므로 Queue가 2개여야 하나?? 라는 생각이 들었다. 그래서 그럼 BFS로 풀지 않고 단순하게 시뮬레이션으로 구현하고 예외처리해주는식으로 문제를 풀려고 했다. 근데 그 안에서 벽/앞에 구슬이 막고 있을 때/구멍을 만났을 때로 나눠서 생각하려니 너무 복잡하고 알고리즘이 짜이지 않아서 애먹었다... [풀이] 결국 째로탈출2 문제가 아닌 원래 째로탈출 문제의 코드를 참고해서 풀었다. BFS로 풀었고 나는 처음에 빨간 구슬과 파란 구슬을 한꺼번에 움직이기 위해서 while(true)문을 하나에 다 몰아서 쓰려고 했다. 근데 ..

[문제] https://www.acmicpc.net/problem/10809 [풀이] 알파벳 a의 아스키코드값은 97알파벳 A의 아스키코드값은 65 애초에 -1로 alpha배열을 초기화한다.입력받은 단어의 각 알파벳의 아스키코드값에서 97을 빼주면 알파벳의 위치가 나오므로 거기에 현재 위치값을 넣는다. 단 같은 알파벳이 나와도 맨 처음 위치가 저장되야 하므로 alpha배열값이 -1일때만 위치를 저장한다. [Code] https://github.com/dbwls94/gomulsang/blob/youjin/BOJ/src/boj_10809/FindAlpha.java

[문제] https://www.acmicpc.net/problem/7569 [처음 생각] 처음에는 단순히 2차원 토마토처럼 6방향으로 돌면서 체크하면 되겠다고 생각했다. 그래서 그렇게 풀었는데 틀렸다... [풀이] 지난번 2차원 토마토 문제와 같은 방식으로 푸려다가 틀리긴했지만 같은 방식으로 다시 풀면 맞을 것 같다...! 대신 이번엔 visited 배열로 익은 날짜를 세는게 아니라 따로 토마토 위치를 저장하는 Uni 클래스 자체에 날짜를 세는 변수 cnt를 넣어서 변화시켰다. 그리고 계속해서 객체의 cnt값을 결과값에 갱신하며 모두 익었을 때의 날 수를 출력하도록 했다. 큐를 확인하는 while문에서 익지 않은 토마토를 만나면 애초에 세어 놓은 익지 않은 토마토 개수에서 1개씩 빼주고 그 토마토를 익히..

[문제] https://www.acmicpc.net/problem/7576 [처음 생각] 이전 BFS 문제와 마찬가지로 토마토 상자를 기준으로 상.하.좌.우 방향의 토마토들을 확인하면서 익지 않았고 방문하지 않았다면 그 토마토를 익히고 큐에 넣어주는 과정을 반복하면서 visited 배열의 익히는 날짜를 하루씩 늘려간다. [풀이] 풀었을 때, BFS 알고리즘 자체는 맞았다. 다만 문제에서 원하는 애초에 모두 익은 경우, 결과적으로 모두 익을 수 없는 경우, 모두 익었을 때의 걸린 날의 수를 출력하는 경우에서 틀렸다. 처음에 visited 배열의 초기값을 0으로 했었는데, 0이 아닌 -1로 두고 시작한다. 0으로 하지 않는 이유는 초기값을 0으로 두어도 어짜피 나중에 결과 count에서 1을 빼주기 때문에 ..

[문제] https://www.acmicpc.net/problem/1157 [처음 생각] 단순히 각 알파벳에 대해 마주치면서 1씩 증가하면 시간복잡도가 많이 클 것 같다. 아니면 유니코드 값으로 바꿔서 int형으로 계산할까했다. 일단 대문자를 모두 소문자로 바꾸는 절차가 필요할듯? [풀이] 1. 소문자 -> 대문자 변환(나중에 대문자 출력이니까)2. int형으로 바꿔서 각 자리 배열에 ++ 해서 저장3. max값 찾고 그 인덱스도 찾음4. 다시 int배열을 돌면서 그 인덱스값이 아니면서 max값과 같은 알파벳이 있다면 ? 출력 [참고] https://www.acmicpc.net/board/view/12135 [Code] https://github.com/dbwls94/gomulsang/blob/youji..

[문제] https://www.acmicpc.net/problem/1037 [처음 생각] 일단 약수가 어떤 순서로 입력되는지가 안주어져서 마구잡이로 주어진다는 가정을 하고 시작했다. [풀이] 약수 개수가 1개일 때와 2이상인 짝수일때로 나눠지므로, 1개일때는 그 약수를 제곱해주면 되고, 짝수일때는 약수 중에서 가장 큰 수와 가장 작은 수를 곱해주면 된다. [Code] https://github.com/dbwls94/gomulsang/blob/youjin/BOJ/src/boj_1037/Measure.java

[문제] https://www.acmicpc.net/problem/1010 [처음 생각] 겹치지 않게 n을 기준으로 했을 때, m중에서 선택하려니 조합이나 순열로 풀리지 않았다. 그래서 반대로 m을 기준으로 했을 때, n중에서 순서없이 선택한다고 생각하니 겹치지 않게 선택할 수 있었다. m개 중에서 n개를 순서없이 선택한다면 선택된 점들은 n개의 점과 차례대로 그냥 이어지면 되기 때문! [풀이] 조합 알고리즘으로 mCn으로 풀었다. 함수 재귀 호출로 점화식을 사용해서 풀었다. [참고] http://bumbums.tistory.com/2 [Code] https://github.com/dbwls94/gomulsang/blob/youjin/BOJ/src/boj_1010/MakeBridge.java

[문제] https://www.acmicpc.net/problem/1005 [처음 생각] 힌트가 위상정렬인걸 보고 일단 위상정렬을 찾아봤다... 찾아보니 위상정렬 알고리즘은 여러 일들에 순서가 정해져있을 때 순서에 맞게 나열할 때 사용하는 알고리즘이어서 이 문제처럼 건설 순서가 정해져있고 순환이 없는 그래프이므로 사용하기 적절한 듯 하다. 위상정렬 알고리즘을 그대로 사용하되 중간에 max 값 갱신해주는 부분만 넣어주면 되지 않을까?! [풀이] 위의 방법처럼 하려고 했는데 위상정렬을 짜려니 길어져서 혹여나 다른 방법으로 할 수 있을까 찾아보니 DP 재귀로 한 사람이 있었다. 위상정렬을 하면 나중에 의존관계를 고려해야 하는데 DP로 풀면 의존관계를 고려하지 않고 거꾸로 지어야 할 마지막 건물번호를 기준으로 ..