https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net d[i][j] = 구간 [i,j]가 팰린드롬인지 여부 팰린드롬의 성질을 이용해서 구간을 확장시켜가면서 a[i]와 a[j]가 같을 때, d[i+1][j-1]이 참인지 확인하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include int i,j,k,n,m,p,q,a[2001]; bool d[2001][2001]; int main() { scanf("%d",&n); for(i=1;i
https://www.acmicpc.net/problem/1890 1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include typedef..
https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으 www.acmicpc.net d[i][j] = (1,1)에서 (i,j)까지 이동했을 때 얻을 수 있는 사탕의 개수의 최대값 d[i][j] = a[i][j]+max..
https://www.acmicpc.net/problem/9536 9536번: 여우는 어떻게 울지? 문제 고대 미스테리로 전해지는 여우의 울음소리를 밝혀내기 위해 한신이는 고성능 녹음기로 무장하고 숲으로 들어갔다. 하지만 숲에는 동물들이 가득해, 녹음된 음성에는 다른 동물들의 울음소리가 섞여 있다. 그러나 한신이는 철저한 준비를 해 왔기 때문에 다른 동물들이 어떤 울음소리를 내는지 정확히 알고 있다. 그러므로 그 소리를 모두 걸러내면 남은 잡음은 분명히 여우의 울음소리일 것이다. 입력 첫 번째 줄에는 테스트케이스의 개수 T가 입력된다. 각 테스트케이스는 www.acmicpc.net 123456789101112131415161718192021222324252627282930313233343536373839..
https://leetcode.com/problems/two-sum/ 일반적으로는 for문 2번 도는 O(N^2) 방법을 생각한다. 이때 해시를 이용해서 a+b=c이라고 할때 a를 해시에 넣기 전에 먼저 b(c-a)가 있는지 확인한다. 이 방법으로 O(N)으로 해결가능하다. 12345678910111213141516171819class Solution {public: vector twoSum(vector& nums, int target) { map hash; vector ret(2); int len=nums.size(); for(int i=0;isecond; return ret; } hash.insert({nums[i],i}); } }};Colored by Color Scriptercs
https://www.acmicpc.net/problem/1620 숫자 -> 포켓몬 이름: 미리 저장해둔 문자열 순서로 찾는다.포켓몬 이름 -> 숫자: 해시 테이블을 이용한다. 체이닝 방식을 사용했다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112#include #define MAX_DATA 25#define MAX_TABLE 100007#defi..
https://www.acmicpc.net/problem/1707 DFS로 노드를 탐색해가면서 마킹표시를 해준다. 이전 노드와 색이 같으면 이분그래프가 아니라고 판정한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include #define V 20050#define E 200050 struct NODE{ int node; struct NODE *next;}; NODE HEAD[V],POOL[E*2];int t,n,m,u,v,cnt,ans,visit[V]; void init(int n){ cnt=0; ans=1; f..
https://www.acmicpc.net/problem/2606 메모리풀로 그래프를 만들고 1번에 연결된 컴퓨터의 개수를 세준다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include #define N 100 struct NODE{ int node; struct NODE *next;}; NODE HEAD[N+1],POOL[N*N];int n,m,u,v,cnt,ans,visit[N+1]; void make(int u,int v){ NODE *node=&POOL[cnt++]; node->node=v; node->next=HEAD[u].next; HEAD[u].next=node..
https://www.acmicpc.net/problem/14003 LIS 배열을 구할 때 길이는 구할 수 있지만 실제 LIS의 순서를 보장하지는 않는다. 하지만 마지막 값이 정답의 마지막값임은 보장한다. 이 정보를 p 배열에 따로 담은 후 LIS 배열을 구한 후에 마지막 값의 인덱스를 이용해서 역추적하면 실제 LIS를 구할 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include #include #include #include using namespace std;typedef pair pii; int n,a[1000000],p[1000000];vector l; bool..
https://www.acmicpc.net/problem/12015 lower_bound를 이용해서 O(nlogn)만에 LIS를 만들 수 있다. 직접 예제들을 만들어서 동작 과정을 살펴보면 이해가 쉽다. 1234567891011121314151617181920#include #include #include using namespace std; int main(){ int n,m; scanf("%d",&n); vector l; l.push_back(-1); while(n--) { scanf("%d",&m); if(l.back()