https://www.acmicpc.net/problem/3190 머리말 아, 뱀 게임 로직 짜는 거구나,, 재밌겠다,, 처음에는 뱀의 위치 정보를 어떻게 구현해야 할지 고민을 하다가 큐가 문득 떠올랐다. 자료구조 때 배운 것을 바로 적용할 수 있는 능력을 키우자! 접근 방법 차근차근 해결하면 된다. 맵 정보를 저장하는 graph 리스트에 사과 위치를 2로 저장하였다. dx, dy 방향 전환을 동, 북, 서, 남 형식으로 저장하여 방향에 맞게 circle로 돌 수 있도록 하였다. cnt는 게임의 시간 정보를 나타내는 변수로, 이것을 logs 배열에 존재하는지 확인 후 방향 전환을 고려하였다. 뱀의 위치 정보를 저장하는 snake 리스트를 큐(deque)를 사용하여 이동할 때 머리는 push, 꼬리는 po..
백준
https://www.acmicpc.net/problem/1865 머리말 문제를 보고, 아 negative cycle 찾는 문제이구나 싶었다. 그래프에서 최단 경로를 탐색하는 방법 중 다익스트라와 벨만 포드가 있는데, 다익스트라는 Greedy 알고리즘이기 때문에 반드시 간선들이 non-negative weights을 만족해야 한다. 한편, 벨만 포드는 Dynamic Programming 알고리즘으로 negative weights를 가져도 정상적으로 동작한다! 접근 방법 edge relaxation을 N-1번 수행한다. 그때 만들어진 distance 배열은 최단 경로이다. edge relaxation을 N번째 수행했을 때, 더 짧은 경로를 발견한다면 negative weight cycle이 존재한다는 결론..
https://www.acmicpc.net/problem/16500 머리말 완전 탐색인 줄 알고 왜 시간 초과가 나지 쩔쩔 맺던.. (테스트케이스 완전 불친절하다 😇) 이 문제는 dp 문제이다. 가만 생각해보면 중복 연산이 많으니 메모이제이션을 당연히 해야 한다. 처음 참고한 블로그도 좋은 풀이법이지만, 다른 분(cozyyg)의 풀이가 더 직관적이어서 그 풀이로 다시 공부하였다. 접근 방법 dp 배열에는 해당 인덱스까지 A에 포함된 문자열로 표현할 수 있는지 여부를 0, 1로 저장한다. 초기값 dp[0]은 1(True)로 두고, 우리의 목표는 dp[len(s)]값이 무엇인지 찾는 것이다. 계산 편의를 위해 +1 위치에 결괏값을 저장한다. 추가 테스트 케이스 1 [input] aaaaaaaaaa 2 aaa..
https://acmicpc.net/problem/12865 머리말 0/1 Knapsack 문제 DP로 유명한 문제이자 NP-hard 문제로 유명한 문제.. 작년 알고리즘 수업시간 때 배웠던 부분이 기억이 잘 나지 않아 첨부하였다. 수업 노트 코드 n, k = map(int, input().split()) weights = [-1] values = [-1] for i in range(n): w, v = map(int, input().split()) weights.append(w) values.append(v) dp = [[0] * (k + 1) for _ in range(n + 1)] for i in range(1, n + 1): for w in range(1, k + 1): if weights[i]
https://www.acmicpc.net/problem/2357 머리말 solved 통계를 보니 자료구조 관련 데이터가 별로 없길레 관련 문제 중에 랜덤으로 하나를 골랐다. 문제 자체는 굉장히 평이해보였지만 n, m 범위가 1 이상 10만 이하 라는 점에서 아,, 이거 뭔가 트리 써야할 것 같은데? 라는 생각이 들었다. 어떤 트리 써야할 지 몰라 알고리즘 분류를 보니 세그먼트 트리 문제라고 한다. 세그먼트 트리 백준 블로그에 상세한 설명이 적혀있다. 세그먼트 트리는 어떠한 구간 내의 로직을 처리할 때 굉장히 효율적인 알고리즘이다. 트리의 노드에 범위라는 개념이 들어가고, 저장할 데이터는 로직에 따라 다르겠지만 이 문제에서는 해당 구간의 최솟값, 최댓값을 저장한다. 리프 노드(idx)라면 idx ~ id..
https://www.acmicpc.net/problem/1162 머리말 오랜만에 9시에 일어나서 백준 문제를 풀어봤다. 일찍 일어난거 맞지..? 어떤 문제를 풀지 고민하다가 최근 수업시간에 다루었던 다익스트라 문제를 골랐다. 1시간 30분 고민해서 풀었다가 6%에서 바로 틀렸다. 허허 아직 부족하다. 나의 접근 방법 다익스트라 문제라는 것만 생각하고 어떻게 문제에 다익스트라를 녹여낼까 고민했던 것 같다. 모든 가중치를 priority queue에 넣고 크기가 큰 순으로 weight를 0으로 집어 넣고 다익스트라를 적용시켰다. 하지만, 조금만 생각해보면 당연히 잘못된 풀이법이다. weight가 큰 것을 포장 도로로 만들 필요가 없기 때문이다. 또한 'k번 이하'라는 조건에 주의를 기울여야 했을 것이다. ..
문제 링크 1. 종만북 어려워서 힐링차 오랜만에 solved 들어가서 풀어본 문제 아이디어는 떠오르는데 코드 써 내려가는 게 귀찮았다. 조금 더 깔끔하게 풀 수 있을 것 같은데, 현재 코드는 조금 난잡한 느낌이 없지 않아 있다. 2. 입출력을 어떻게 처리할지 많이 고민했다. input[]은 n개의 수로 이루어진 수열이다. op_num[]은 덧셈, 뺄셈, 곱셈, 나눗셈의 개수를 나타낸다. op_num[]의 index 번호를 각각의 연산자로 간주하였다. 즉, 0은 덧셈, 1은 뺄셈 이런 식으로 말이다. opArr[]에 연산자를 숫자로 표현하여 집어넣었다. 예를 들면, op_num[0]=2, op_num[1]=1, op_num[2]=1, op_num[3]=2 이라면 opArr = {0, 0, 1, 2, 3, ..
문제 링크 1. 기본적인 그래프 문제였지만 요즘 문제 풀기가 너무 싫어서 뭉그적거리면서 풀었던 문제 2. BFS를 이용하여 문제를 해결하였다. 나이트가 이동할 수 있는 8가지 방향을 배열로 만들어준다. int[] dx = { 1, 2, 2, 1, -1, -2, -2, -1 }; int[] dy = { -2, -1, 1, 2, 2, 1, -1, -2 }; 조건에 맞으면 queue에 넣는데, 중요한 점은 cnt 2차원 배열을 만들어 해당 위치까지 몇 번을 이동했는지를 저장한다. 3. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static int n; static Pos now..
