본문 바로가기

온라인저지144

[BOJ] 11726번: 2xn 타일링(feat. DP) 11726: 2xn 타일링풀이Dynamic Programming으로 풀 수 있는 문제다. dp[i] = dp[i - 1] + dp[i - 2]코드123456789#include int main(){ int n, i, dp[1001] = { 1, 1 }; scanf("%d", &n); for (i = 2; i 2018. 3. 25.
[BOJ] 1316번: 그룹 단어 체커 문제 링크풀이분기점이 총 3개가 나온다. i와 i-1번째가 다르고 처음 보는 단어인 경우i와 i-1번째가 같고 처음 보는 단어는 아닌 것(같은 문자가 연속된 것)i와 i-1번째가 다른데 이미 확인 된 것(서로 떨어져 있는 경우) - 예) aabba --> 이때가 그룹 단어가 아닌 경우을 바로 확인 가능하다. 즉, i + 1번째 단어들은 볼 필요가 없다.필요한 변수 : bool형 alpha배열(처음 보는 단어인지 아닌지 확인한다), char형 prev 변수(i번째 기준으로 i -1번째 문자를 기억하는 용도) 나는 함수를 사용해서 구현 할 것이므로 3번째 경우일 때 바로 return false를 해주면 되고 나머지 경우일 경우일 때는 alpha배열과 prev변수를 업데이트만 해주면 되는 상황이 나온다. 코드 2018. 3. 10.
[BOJ]1005: ACM Craft 문제 링크 DFS + DP 방식으로 풀었다. 위상 정렬이라는 것으로 풀 수도 있는 것 같은데 다음 시간에 다시 풀어보도록 하고... 나는 처음에 1번부터 시작해서 N까지 다 시간을 구한 후에 dp[w]을 출력해줄려고 했는데 각각의 dp[i]값을 지정해줄 방법을 생각하지 못하다가 결국 다른 분들을 보니 w부터 시작해서 (그래프라면) 위로 연결된 자신의 부모를 탐색하신 것을 봤다. 그래서 만약 7번 노드가 5번 6번과 연결되어 있다면 dp[7] = max(dp[5], dp[6]) + 7번의 시간(d[7]) 이런 형식이였다. 그래서 이 부분은 재귀함수를 돌려서 1번 노드까지 찍고 내려오면 되는 것이였다;;잡소리를 좀 하자면 결국 답은 인접 행렬로 풀었는데 원래 인접 리스트(vector)로 풀려다가 겁나 뻘짓해.. 2018. 3. 9.
[BOJ]1004번: 어린 왕자 1004: 어린 왕자문제 풀기 원 안에 점이 있는지 없는지 확인하는 걸 짜는 문제였다. 다만 조심해야 하는 것은 거리가 int 범위로는 커버할 수 없기 때문에 long long 같은 걸 써줘야 한다. 2018. 2. 19.
[BOJ]1920번: 수 찾기 문제 풀러 가기 링크 1920번: 수 찾기이분 탐색을 이용하면 된다. 나는 속도가 60ms가 나왔는데 적게 나오신 분들의 코드를 보니 입력 받는 부분이 특이하던데 어떻게 하는지는 모르겠다.이분탐색에서 int mid = (left + right) / 2하는 부분에서 / 2 부분을 쉬프트 연산자를 써서 >> 1로 바꿔주니 나의 경우에는 64ms -> 60ms로 바뀌었다. 코드 2018. 2. 5.
[BOJ]2606번: 바이러스 문제 풀러가기 링크 2606번: 바이러스문제 분류가 플로이드 와샬 알고리즘으로 되어 있는데 나는 DFS로 풀었다. 플로이드 와샬을 짜본적이 아직 없고 사실 BFS 연습 문제 추천에서 나온 문제라 풀려고 한 건데 BFS보단 DFS가 더 쉬울 것 같았기 때문이다 ㅋㅋ 문제 자체는 간단한데 1번 컴퓨터에서 바이러스가 시작되서 연결이 되어 있는 모든 컴퓨터까지 감염이 되는데 그 감염되는 컴퓨터의 개수를 세라는 것이다. --> 탐색 DFS와 BFS라는 문제를 풀어 봤다면 엄청 쉽게 풀 수 있다. 사실 컨셉만 다른 거지 문제는 똑같다고 보면 된다. 코드 2018. 2. 5.
[BOJ] 1932번: 숫자삼각형 1932번 문제 풀기! 1932번: 숫자삼각형정말 고민을 많이 했는데 생각보다 간단했었따... 이게 왜 DP인지 궁금하신 분들을 위해 설명을 하자면 문제 자체가 위층에서 다음을 위해 적절한 녀석을 골라서 현재 층에서 가장 적절한 녀석을 골라 더해주는 것이다. 좀 깔끔하게 설명하지 못해서 그렇긴 한데 재귀적인 성격이 나오는 문제이다. 문제를 보면 ↘, ↙으로 갈 수 있다고 했다. 이건 위에서 아래로 내려갈 때 가정(1)이고, 아래에서 위로 간다고 가정하면 ↖, ↗으로 갈 수 있다.(2) 개인적으로 이런 문제들은 바텀-업 방식을 사용하는 것을 선호하기 때문에 (2)의 가정이 점화식을 세우기에 좋았다. [1] [2] [3] [4] [5] [1] 7 [2] 3 8 [3] 8 1 0 [4] 2 7 4 4 [5] .. 2018. 2. 3.
[BOJ]1978번: 소수 찾기 문제 풀러 가기1978번: 소수 찾기소수는 1과 자기 자신으로만 나눠지는 수이다. 예를 들어 2, 3, 5, 7 등이 있다.여기서는 안 쓰이는 방법 같은데 N(자연수)까지의 소수의 개수를 구하는 많은 양을 작업할 때는 에라토스테네스의 체라는 것을 사용한다고 한다.하지만 여기서 사용하진 않았다.참고: 위키피디아코드 2018. 2. 2.
[BOJ]2193번: 이친수 문제 풀러 가기 2193번: 이친수 처음에는 문제를 잘못 보고 n이 주어졌을 때 n을 이진수로 바꿔서 이친수인지 확인하는 문제인줄 알았다. 이래서 문제를 잘 읽어야 한다;; 어쨋거나 이 문제는 DP문제인데 처음에는 왜 DP인가 했지만 주어진 조건들을 보고 손으로 하다보니 DP라는 사실을 알게 되었다. 맨 끝자리가 0으로 끝나면 파생될 수 있는 숫자가 '0'과 '1'로 두 개이고 1로 끝나면 '0'으로 파생된다. 규칙은 찾았고 분명히 개수에도 규칙이 있을 것 같아 몇 개 적은 것을 보니깐 피보나치 수열이라는 사실을 알았다. 아! 그리고 참고로 처음에 제출했을 때 틀려서 질문 올라온 것을 보니깐 90자리까지 나올 수 있는데 그러면 long long이 필요할 것 같아서 고쳤더니 맞았다. + 추가: 2020/0.. 2018. 2. 1.
[BOJ]2669번: 직사각형 네개의 합집합의 면적 구하기 [BOJ]2669번: 직사각형 네개의 합집합의 면적 구하기접근처음에 접근을 무작정 빼고 더하고... 하려고 했으나 감히 그 행동을 하지 못하겠어서 질문 검색을 해봤습니다 ㅠㅠ 풀이메모리를 포기하고 정신을 챙겨간다! 100x100의 배열을 만들고 그 칸들을 채워나가는 방식으로 문제를 풀어봤습니다. 코드 2018. 1. 25.
[BOJ]2667번: 단지번호붙이기 2667번: 단지번호붙이기전체 탐색을 돌아서 해결하는 문제다. 나는 내 코드가 bfs인지 dfs인지는 모르겠다. 아시는 분은 댓글 달아주시면 감사드리겠습니다. 앞으로 문제를 열심히 풀어서 탐색 문제 같은 기본적이고 필수적인 문제들은 마스터를 하도록 노력해야 겠다는 생각을 했다. 2018. 1. 25.
[BOJ] 1002번 : 터렛 링크 : https://www.acmicpc.net/problem/1002 터렛문제... 방금전에 올린 '두 원의 위치관계'를 올린 이유가 여기 있다.굉장히! 유익한 문제~ 중학교 과정에서 약했던 부분을 다시 보강한 기분이다. 암튼 여기서 해설을 원한다면 전에 있는 글을 보길 바란다. 그 다음에 다시 오길 바란다.아, 참고로 이 문제에서 고민해야하는 부분은 -1을 출력하는 부분인데, 그냥 x1 == x2 && y1 == y2 && r1 == r2 일 때 -1을 출력하면 된다. (잘 생각해 보면 될 것이다.) 그리고 나머지 부분은 내 전 글에 있으므로 그냥 여기에는 코드만 올리겠다.12345678910111213141516171819202122232425262728293031#include #include.. 2017. 11. 16.
[BOJ] 1260번: DFS와 BFS 문제 풀러 가기 링크! 1260번: DFS와 BFSDFS와 BFS를 실제로 구현해 볼 수 있는 아주 좋은 문제이다.DFS는 깊이 우선 탐색이여서 최대한 한 정점에서 최대한 깊게 갔다가 다시 돌아오는 작업을 반복해서 모든 정점을 탐색하는 것이고BFS는 너비 우선 탐색이여서 층 별로 있는 모든 정점을 다 돌면서 내려간다고 보면 된다.아직 내가 직접 쓴 글이 없어서 개인적으로 정말 좋다고 생각하는 블로그의 글의 링크를 걸어 놓을테니 이 쪽에 가서 자세히 공부하면 된다.DFS 설명, BFS 설명 개인적으로 DFS는 재귀함수를 이용하는 것을 좋아해서 원래는 스택을 쓰지만 나는 재귀함수로 구현했고 BFS는 스택을 이용해서 구현했다. BFS는 분리하지 않고 main함수에 적어서 가독성이 떨어질텐데... 그 점은 양해.. 2017. 11. 4.
[BOJ] 10942번: 팰린드롬? https://www.acmicpc.net/problem/10942 오랜만입니다... 오늘은 팰린드롬에 대한 문제를 풀어 보려고 합니다.팰린드롬이란, 위키백과 : 숫자, 단어, 구 같은 시퀀스들이 앞과 뒤가 같아서 반으로 접으면 일치하게 되는 녀석들을 칭합니다. 이 문제는 DP로 푼다고 하는데, 저는 사실 DP를 잘 못하기도 하고 굳이 DP로 풀 필요가 없는 것 같았습니다.12345678910111213141516171819202122232425262728293031#include int palin(int start, int finish, int *arr) { int mid = (start + finish) / 2; for(int i = start, j = finish; i = mid; i++, j--).. 2017. 10. 21.
[BOJ]14726번: 신용카드 판별 14726: 신용카드 판별 숫자로 해도 되고 문자열로 해도 되는데 나는 문자열로 구성했다. 구현~ 12345678910111213141516171819202122232425262728293031323334353637383940#include int N;char num[10001][1001]; bool f(char a[]){ int sum = 0; for (int i = 15; i >= 0; i--) { if ((i + 1) % 2 != 0) { if ((a[i] - '0') * 2 >= 10) { a[i] = ((((a[i] - '0') * 2) / 10) + ((a[i] - '0') * 2) % 10) + '0'; } else a[i] = (a[i] - '0') * 2 + '0'; } } for (in.. 2017. 9. 24.

티스토리툴바