코딩스토리

www.acmicpc.net/problem/16120 16120번: PPAP 첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다. www.acmicpc.net 그리디 알고리즘이라길래 풀었다가 크게 당한 문제다.. 그리디 문제를 여러 번 풀수록 내 멍청함에 한 번 감탄하고 내가 풀이법을 떠올리는 것에 또 한 번 감탄한다. 참 신기한 알고리즘이야.. 이거 풀려고 연습장에 PPAP를 몇 번을 썼는지 모르겠다ㅋㅋ 처음에 접근을 완전히 이상하게 해서 너무 많은 시간을 버리고 결국 코드를 처음부터 다시 짰다. 먼저 정답을 받은 방법부터 설명하자면 아래와 같다. 1. 문자열의 마지막부터 시작하여 하나의 문자씩 확인한다 (딱 봐도 ..

www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 코드포스 만년 초록 따리를 벗어나기 위해 그리디 문제를 많이 풀어봐야겠다고 마음먹었다. 이 문제의 풀이는 다음과 같다. 1. 모든 단어에서 각 문자가 얼마만큼의 계수를 갖는지를 구하기 ex) AB이면 10A + B, 즉 A = 10, B = 1을 저장 2. 계수가 큰 알파벳 순으로 정렬 (어차피 전체 단어의 합이기 때문에 계수가 크면 큰 수를 할당해야 한다.) 3. 정렬된 알파벳에 9부터 순서대로 할당하여..

www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 연구소 문제는 매우 유명한? 문제이기 때문에 한번 풀어보았다. 문제를 읽어보면 알겠지만 연구소 1과 비슷하게 백트래킹과 bfs를 사용하여 해결하면 될 것 같았다. 가장 걱정되었던 것은 시간제한이 0.25초인 거였지만 아무리 봐도 다른 풀이가 떠오르지 않아서 생각한 대로 구현해보았다. 풀이과정은 다음과 같았다. 1) 바이러스를 놓을 수 있는 모든 위치를 찾아놓음(최대 10개) 2) 모든 경우를 계산함 3) 이때 각 위치에..

www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 난이도 자체는 어렵지 않았으나 구현이 너무 복잡했다.. 처음에 map으로 접근해보려다가 2시간 넘게 날리고 다시 그냥 배열로 접근했다.. (처음부터 배열로 접근할걸 괜히 까불다가) 이 문제의 핵심 포인트는 아무래도 매 연산마다 바뀌는 숫자들의 개수를 파악해놓는 것 아닐까 싶다. 그리고 이런 문제를 풀때마다 실수하는 점은 i와 j를 헷갈리거나 +=인데 -=으로 쓰는 등 이런 점들을 조심해야 한다 (내..

www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 다익스트라 알고리즘을 사용한 문제이다. 최단거리를 찾아야 하나 가중치가 존재한다. 즉 전형적인 다익스트라 알고리즘 문제이다. 문제는 지금까지 인접 리스트를 활용해서 풀어보다 보니 이렇게 그래프로 모델링해서 풀어본 적이 없었다. 구현 자체는 문제가 없었는데 고민했던 부분은 우선순위 큐에서 우선순위를 어떻게 주어야 하는지였다. 내가 사용하고 싶은 것은 dis, x좌표, y좌표 이 3가지였기 때문에..