본문 바로가기

전체 목록!291

[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.
시간복잡도 & 공간복잡도 Time complexity & Space complexity블로그에 알고리즘 배울 때 가장 먼저 배우는 빅-오 표기법과 시간 복잡도, 공간 복잡도를 안 적어놨길래 지금이라도 정리해서 올립니다. 자세한 정보는 웬만하면 위키피디아을 찾아보시는 걸 추천드려요.시간 복잡도알고리즘 수행 시간을 측정한 계산 복잡도(시간) 공간 복잡도메모리 차지하는 양(메모리) 빅-오 표기법(Big-O notation)빅-오 표기법은 주로 시간 복잡도를 나타내는데 이 알고리즘이 '어느 정도 걸리겠다'는 것을 알 수 있습니다.빅-오 표기법은 O(내용)으로 표기합니다. 알고리즘의 복잡도에서는 주로(항상이 아닙니다) 반복문이 좌지우지하기 때문에 반복문이 몇 번 도는지 확인해서 표기할 수도 있습니다. 복잡도가 N + 12여도 상수를 제외.. 2018. 2. 17.
[BOJ]1920번: 수 찾기 문제 풀러 가기 링크 1920번: 수 찾기이분 탐색을 이용하면 된다. 나는 속도가 60ms가 나왔는데 적게 나오신 분들의 코드를 보니 입력 받는 부분이 특이하던데 어떻게 하는지는 모르겠다.이분탐색에서 int mid = (left + right) / 2하는 부분에서 / 2 부분을 쉬프트 연산자를 써서 >> 1로 바꿔주니 나의 경우에는 64ms -> 60ms로 바뀌었다. 코드 2018. 2. 5.
손코딩뇌컴파일눈디버깅 어제 저녁부터 해서 지금 새벽까지 '나는 프로그래머다'라는 팟캐스트를 다시 보고 있었다. 그 중에서 알고리즘을 주제로 해서 '구종만'님과 '하광성'님께서 출연하셨는데 이야기를 나누시면서 하광성님이 하셨던(지금은 안 하신단다) '손코딩뇌컴파일눈디버깅'이라는 스터디를 하셨다고 했는데 손코딩뇌컴파일눈디버깅 스터디 설명 링크 "와.. 정말 좋은 것 같다"라는 생각이 들었다. 디버깅이 실제 개발 시간보다 길듯이 테스트 케이스를 고민해보고 실제 내 머리를 굴리면서 생각하는 것이 오히려 문제 하나를 풀더라도 더 효과적이라고 생각한다. 그래서 앞으로 학교에서 친구들이랑 PS 스터디를 만들어 볼까 생각 중인데 이 신박하면서도 좋을 것 같은 컨셉을 갖고 스터디를 구성하면 좋을 것 같다. 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.
2017년의 연말이네요 안녕하세요. 파크입니다. 최근 2개월간 블로그에 글을 올리지 않았는데 그 이유는 제가 학교 공부를 하느라 딱히 올릴 글이 없었습니다 XD 오늘 날짜로 2017년 12월 22일. 2017년의 끝도 드디어 보이는데요. 이번 년은 참 빨리 지나간 것 같습니다.학교를 다니면서 블로그를 시작하고 제가 써온 글들, 힘들었던 수행 평가, 프로젝트들, 읽은 책들을 쭉~ 보면서 언제 이렇게 많이 했지?라는 생각을 했습니다.저도 한 해를 마무리하는 작업을 계속해서 하고 있고 여러분들께서도 바쁘게 보내실 것 같네요. 저에게는 특히 다사다난 했던 1년, 어찌해서 잘 마무리 지은 것 같고 내년에는 더 열심히 하도록 하겠습니다. 2017. 12. 22.
Sir, Ma'am을 올바르게 사용하자 영어를 배웠거나 스타크래프트를 해봤다면 "Yes, sir!"을 한 번씩 들어봤을 거다. 내 친구들도 그렇고 어린 친구들도 알겠다는 말을 영어로 하겠다고 'Yes' 뒤에 (거의 자동적으로) 'sir'을 붙인다. 그러면 "Yes, sir"이라는 것인데 "남성"에게 이렇게 말하면 문제가 되지 않는다. 하지만 문제는 이 말을 여성에게 할 때다. Sir은 우리나라 말로는 '경(卿)'에 해당하는 단어인데 남자에 대한 경칭으로 쓰는 단어이다. * Sir의 사전적 정의 그래서 여성에 대한 경칭으로 쓰는 단어는 '부인'에 해당하는 단어인 "Ma'am" [mæm]을 사용해야 한다. * Ma'am의 사전적 정의 사람들이 실수하는 것을 정말 많이 봤기 때문에 적어도 이 글을 본 사람은 잘 분간해서 썼으면 좋겠다. 정리 남자에.. 2017. 12. 22.
[BOJ] 1002번 : 터렛 링크 : https://www.acmicpc.net/problem/1002 터렛문제... 방금전에 올린 '두 원의 위치관계'를 올린 이유가 여기 있다.굉장히! 유익한 문제~ 중학교 과정에서 약했던 부분을 다시 보강한 기분이다. 암튼 여기서 해설을 원한다면 전에 있는 글을 보길 바란다. 그 다음에 다시 오길 바란다.아, 참고로 이 문제에서 고민해야하는 부분은 -1을 출력하는 부분인데, 그냥 x1 == x2 && y1 == y2 && r1 == r2 일 때 -1을 출력하면 된다. (잘 생각해 보면 될 것이다.) 그리고 나머지 부분은 내 전 글에 있으므로 그냥 여기에는 코드만 올리겠다.12345678910111213141516171819202122232425262728293031#include #include.. 2017. 11. 16.

티스토리툴바