kth990303의 코딩 블로그

+) 21.12.22 추가 이 프로젝트는 2022년에 나 혼자서 스프링 + 리액트 풀스택으로 진행해볼 예정이다. 위 말이 거짓말이 되지 않도록 열심히 공부하자! https://kth990303.tistory.com/234 [211222] 스프링과 리액트로 1인분 하기 위해 요즘 하고 있는 공부 예전에 '운동일지 다이어리'를 친구랑 같이 만들다가, 어쩌다가 흐지부지된 프로젝트가 있다. (안좋게 끝난 건 아니다. 서로 각자의 공부를 해야될 것 같다고 결론이 났다.) https://kth990303.tistory.co kth990303.tistory.com 이 프로젝트는 협업 프로젝트이기 때문에 내 일정 뿐만 아니라 친구 일정도 중요한데, 친구가 중간고사 끝나고 재정비를 가진 후 11월부터 프로젝트를 해야할 ..

그룹 연습으로 진행된 Virtual 코딩테스트 연습6 후기를 포스팅하려 한다. 문제셋을 풀면서 어떤 생각을 거쳐 해결했는지 기록해두면 이후에 풀이과정을 떠올리는 필연성을 매끄럽게 떠올릴 수 있을 것 같기 때문이다. https://www.acmicpc.net/group/practice/9928/51 참여자가 나 혼자뿐이다... 참고로 알고리즘 분류는 보지 않았고, 티어는 성공했을 경우 표시로 진행하였다. A - 인터넷 설치 을 처음 접했을 때, A번이니까 쉬울 것이라 예상했는데 생각보다 쉽지 않았다. 1번은 이미 인터넷에 연결돼있었고, N번만 인터넷에 연결시키면 되니까 N에서부터 거꾸로 생각해보았다. 처음 떠올렸던 것은 그리디나 dp이다. 그러나, 아무리 생각해도 관통하는 최적의 방법이 보이지 않아 그리디..

바닐라js로 틱택토를 만들면서 기본기를 다져보자. 틱택토는 오목과 룰이 동일하나, 가로, 세로, 대각선 중 한 방향으로 5개를 자기 것으로 칠해야하는 오목과 달리, 3개만 자기 것으로 칠해도 되는 룰을 가진다. 여기서 사용되는 문법은 다음과 같다. (모르더라도 이번 포스팅을 보면서 알면 될 듯하다.) querySelector, createElement html 태그를 선택해주는 querySelector, 또는 html 태그를 추가해주는 createElement. html 파일을 생성해서 ... 와 같은 html 파일을 만들어도 되나, 여기서는 js로 대체하도록 한다. 만약 html 파일을 생성해서 진행한다면 querySelector로 태그를 선택하면 된다. 콜백함수와 고차함수 개념 고차함수가 말이 거창해..

요즘 백준 풀문제들, 공부할 내용들이 많다보니 알고리즘 공부 우선순위가 상당히 높아져있다. 포스팅도 대부분 백준 관련 포스팅으로 이루어져버렸다. 아무튼 문제는 아래와 같다. https://www.acmicpc.net/problem/13710 13710번: XOR 합 3 첫째 줄에는 배열의 크기 N (1 ≤ N ≤ 100,000), 둘째 줄에는 수열 A에 들어있는 수가 주어진다. 수열 A에 들어있는 수는 109보다 작거나 같은 음이 아닌 정수이다. www.acmicpc.net 의식의 흐름 및 해설 처음엔 좀 쉬운 문제가 아닌가 생각했다. 수열 a1, a2, ... , an이 있을 때, 연속하는 부분수열의 xor합을 구하기 위해선 누적합으로 p[i-1]^a[i]+a[i]를 해주면 되지 않나 싶어서 간단하게 ..

굉장히 유명한 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/11014 11014번: 컨닝 2 최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목은 상당히 까다롭기로 정평이 나있기 때문에, 몇몇 학생들은 시험을 보는 도중에 다른 사람의 답지를 베끼려 한 www.acmicpc.net 1014번 컨닝은 N, M 제한이 80이 아니라 10이라는 점 외엔 11014번과 동일하다. 의식의 흐름 및 해설 사실 이 문제는 너무나도 유명한 문제여서 최대유량, bitmask+dp 로 풀어야한다는 사실 자체는 알고 있었던 문제이다. 그러나 왜 최대유량으로 풀리는지 모르는 상태였기 때문였었고, 마침 우연히 최근에 flow 관련 그래프 이론을 공부중이기 때문에 ..

flow 이론에 있어서 나름 구현은 쉽지만 중요한 문제이다. 문제는 아래와 같다. https://www.acmicpc.net/problem/1867 1867번: 돌멩이 제거 첫째 줄에 n과 k가 주어진다. (1 ≤ n ≤ 500, 1 ≤ k ≤ 10,000) 이후 k개의 줄에는 돌멩이의 위치가 한 줄에 하나씩 주어진다. 줄마다 첫 번째 숫자는 행 번호, 두 번째 숫자는 열 번호를 나타낸다. www.acmicpc.net 의식의 흐름 및 해설 특정 행, 열을 최소한으로 선택하여 모든 돌멩이를 제거하는 문제이다. 행을 선택하면 그 행에 포함된 돌멩이의 열들이 영향을 받는다. 단, 다른 행들은 영향을 받지 않는다. 따라서 행과 열로 이분그래프를 나눠볼 수 있다. 여기서 돌멩이는 행-열을 연결하는 간선을 의미한다..

학교 채점현황을 둘러보다가 발견한 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/1990 1990번: 소수인팰린드롬 151은 소수이면서 동시에 팰린드롬이기 때문에 소수인 팰린드롬이다. 팰린드롬이란 앞으로 읽어나 뒤로 읽으나 같은 수를 말한다. 예를 들어 1234는 앞으로 읽으면 1234지만, 뒤로 읽으면 4321이 되 www.acmicpc.net 의식의 흐름 및 해설 소수 문제인데 팰린드롬이어야 하는 문제이다. 범위가 1억까지이기 때문에 애매하게 시간초과가 될까말까한 문제처럼 보였는데, 생각해보니 팰린드롬인지 체크해주는 과정 때문에 O(1억 * s.length())이므로 시간초과가 나오기 충분한 시간복잡도였다. 특히, 수가 클수록 수가 많으므로 (ex.10 ~100..

클래스 문제에 있길래 풀어보았다. 문제는 아래와 같다. https://www.acmicpc.net/problem/17401 17401번: 일하는 세포 출력은 N개의 줄로 구성되며, i 번째 줄에는 N개의 정수 xi1, xi2, ..., xiN를 공백으로 구분하여 출력해야 한다. xij는 0초 때 거점 i 에서 출발하여 정확히 D초 때 거점 j에 위치하게 되는 경로의 수를 1 www.acmicpc.net 의식의 흐름 및 해설 우선 D가 굉장히 크다. 어지간한 그래프 탐색 (dfs, bfs, floyd)로는 시간복잡도 내에 절대 불가능해보인다. 그런데, 이렇게 이동 경우의 수를 구하는 문제, 어디서 많이 보지 않았나? 바로 본대산책2에서 본 듯하다. https://www.acmicpc.net/problem/..

KOI 2차대회 중등부 문제이다. 예상보다 꽤나 고전했던 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/22345 22345번: 누적 거리 KOI 나라는 수직선 위에 놓인 N개의 마을로 구성되어 있다. 이 중 i (1 ≤ i ≤ N)번째 마을은 xi 위치에 놓여 있으며 ai명이 거주 중이다. 또한 서로 다른 두 마을이 같은 위치에 놓인 경우는 없다. KOI www.acmicpc.net 의식의 흐름 및 해설 범위가 상당히 크기 때문에 좌표 범위대로 스위핑은 불가능하다. 대신, N개의 좌표를 순서대로 스위핑은 가능하며, 주어진 q가 어느 마을 사이에 있는지 이분탐색으로 구해줄 수 있겠다. 이렇게 대충 O(QlgN) 시간복잡도를 떠올릴 수 있는데, 문제는 누적거리가 어떻..

정말 오랜만에 소박한그룹 java 프로젝트를 진행한다. 댓글 기능을 오늘 이어서 하려다가, 지난번에 회원이 작성한 게시글 목록 기능 구현을 우선적으로 하고 있었다는 사실을 깨닫고 회원작성 게시글 목록 view단을 만드는 작업을 진행했다. 그러던 와중, 아래 uri 주소에서 에러가 발생했다. http://localhost:8090/delete/1 test code에서 롤백되지 않고 남은 test, test2, test3을 회원탈퇴 시키려할 때 아래 에러가 발생했다. test code를 잘 작성해도 아직 이런 에러를 겪는 걸 보니 한참 멀었다. 연관관계가 많아질수록 버그도 많아지는... 에러는 위와 같이 떴는데, 아마 post-member table이 원래 단방향이었는데, 양방향으로 바꾸면서 에러가 발생한 ..