Naver Blog
백준 3190번 - 뱀
문제 링크 https://www.acmicpc.net/problem/3190 우선 전체 코드는 아래와 같습니다 enum class를 사용해...
키자드에 등록된 총 133개의 포스트를 확인하실 수 있습니다.
문제 링크 https://www.acmicpc.net/problem/3190 우선 전체 코드는 아래와 같습니다 enum class를 사용해...
https://www.acmicpc.net/problem/14499 전체 코드는 아래와 같습니다. 설명은 코드 아래에 있습니다. 이 ...
https://www.acmicpc.net/problem/1699 설명은 아래에 있습니다. 수학적 사고능력이 정말 중요한 문제입니...
[1] 라이브러리 라이브러리는 누군가 이미 만들어 놓은 '도구'를 쓰는 것입니다. 이 도구라는 단...
Git은 내부적으로 크게 3가지 종류의 작업 영역을 두고 동작합니다. 각 적업 영역의 이름은 1. working di...
Git으로 관리되는 파일은 일종의 '상태'라는 걸 가집니다. 크게는 Untracked 상태와 Tracked ...
GitHub는 '원격 저장소'입니다. 즉, 내 컴퓨터에서 작업하던 작업물을 저장하는 공간입니다. ...
로컬 레포지터리 내용을 리모트 레포지터리에도 반영하려면 git push를 해줘야한다고 했습니다. 그런데 모...
https://www.acmicpc.net/problem/1260 설명은 아래에 있습니다. 음.. 사실 설명할게 별로 없습니다. DF...
https://www.acmicpc.net/problem/2178 설명은 코드 아래에 있습니다. 저는 dfs로 문제를 풀었습니다. 이 ...
https://www.acmicpc.net/problem/2606 bfs를 쓰면 굉장히 쉽게 풀리는 문제였습니다. 추가적인 설명은 하...
커밋은 연결 리스트 형식으로 저장되어 있습니다. git log로 커밋 이력들을 살펴보면 가장 최신 커밋에 &#x...
branch A, B에서 서로 다른 작업을 하고 있습니다. 그런데 A에 있는 기능이 B에도 필요하게 되었습니다...
remote repository의 마스터 브랜치를 보려면 깃허브에 들어가서 보면 되겠죠? 하지만 제 컴퓨터에서도 확...
사실 HEAD와 branch는 포인터입니다. 포인터는 무엇을 가리키는 것을 말합니다. 이전에 HEAD를 설...
결론부터 말하자면 reset은 브랜치의 이동이고 checkout은 해드의 이동입니다. [1] reset reset은 브랜치의...
제목이 조금 이상하게 느껴지셨을 수도 있습니다. 커밋을 취소하려면 리셋을 쓰면 되지 않을까요? 반은 맞...
마스터 브랜치에서 작업을 하다가 아직 커밋을 하지 않았는데 급하게 다른 브랜치로 가야할 일이 생길 수 ...
$ git init : 현재 디렉터리를 워킹디렉터리로 지정, 레포지터리 생성 $ git config user.name '이름&...
https://www.acmicpc.net/problem/2667 메인 함수에서 map[0][0]부터 차례대로 탐색하면서 아직 방문하지 ...
https://www.acmicpc.net/problem/7569 사실 난이도는 그렇게 높지 않지만 실수할 수 있는 부분이 굉장히 ...
https://www.acmicpc.net/problem/14719 각 인덱스에서 채워지는 빗물의 양을 구해야합니다. 그런데 첫 번...
https://www.acmicpc.net/problem/1463 문제에서 가능한 연산은 세 가지입니다. 1.N이 3으로 나누어 떨어...
https://www.acmicpc.net/problem/1697 많이 나오는 유형인데 정답률이 되게 낮아서 당황한 문제였습니다. ...
https://www.acmicpc.net/problem/5639 전위 순회 순서대로 이진 트리에 삽입시켜주면 트리가 완성됩니다. ...
https://www.acmicpc.net/problem/1107 푸는데 오래 걸렸습니다ㅠㅠ 처음에는 무슨 규칙이 있을줄 알았는데...
매번 C++로만 코딩을 해서 제가 까먹은 부분들을 다뤄보려고 합니다. [1] 문자열 포멧팅 %d => ...
1. List [1] 인덱싱과 슬라이싱 list[a:b] 인덱스 a부터 인덱스 b-1까지의 원소 읽는다 list[a:] 인덱스 a...
C++ 을 배울때 call by value와 call by reference를 이해하느라 고생했던 기억이 나네요. 처음 이 개념을...
1. min, max 함수 2. sum함수 리스트, 튜플, 사전의 모든 요소의 합을 반환해준다. 사전 같은 경우 key의 ...
https://www.acmicpc.net/problem/2579 우선 두 개의 배열을 생성합니다. dp배열에는 누적 점수를 저장하고...
https://www.advancedwebranking.com/html/ 위 사이트에 들어가면 아래와 같이 자주 사용하는 html tag를 ...
css 스타일을 적용하는 세 가지 방법을 소개하겠다. 어느 방법을 써도 상관없겠지만 일반적으로 세 번째 방...
html/css 간단한 실습. 코드잇을 참고했고 문제가 되면 바로 지우겠다. 하지만 어차피 나 말고 볼 사람이 ...
p, div, span 태그 모두 박스 모델이다. 박스 모델은 padding, border, margin을 갖는데 그림으로 보면 아...
Display는 HTML 요소의 레이아웃을 결정하는 속성 중 하나다. 모든 요소는 딱 하나의 display 값을 가...
합집합 찾기는 그래프의 연결 유무를 판별할 때 쓰이는 알고리즘이다. 세 가지 함수만 구현하면 된다. 1. g...
최소비용신장트리는 순환하지 않는 최소 비용의 경로를 의미한다. kruskal 알고리즘은 그리디 알고리즘이며...
문제 설명 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 beg...
문제 설명 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다...
파이썬과 많은 부분 비슷하다. 파이썬이라 생각하고 써도 무방하다. === vs =...
id로 태그 선택하기 document.getElementById('idName'); class로 태그 선택하기 document.g...
이벤트 헨들링 1) 첫 번째 방법 const btn = document.querySelector('#myBtn'); btn.on...
AND와 OR의 연산 방식 console.log('a' && 'b'); 왼쪽값이 true면 오른...
기본 형태 function sayHelloWorld(){ console.log('Hello World!'); } 변수에 할당해서 사...
1. 콜백함수 fetch 함수는 콜백함수로 서버에 request를 보내고 response를 받는 함수다. 그렇다면… 콜백 ...
1. 공식 문서에 따르면 exports는 module.exports의 shortcut일 뿐이며 항상 module.exports를 참조하고 있...
https://www.acmicpc.net/problem/1197 문제 제목에서 친절하게 어떤 문제인지 알려주고 있다. 나는 크루스...
1. 다익스트라의 구성 최소 거리를 구할때 사용하는 대표적인 알고리즘 '다익스트라'에 대해 알아보자. 다익스트라 알고리즘은 시작점으로부터 모든 노드까지의 최소거리를 구해준다. 다익스트라를 구현하기 위해서는 비용 배열, 방문 노드 배열, 시작점~각 노드까지의 비용 배열이 필요하다. 다익스트라에서 노드간의 연결은 wiehgt의 값으로 판단한다. 특정 값이 있으면 연결되어 있다는 뜻이고, 무한값(INF)이면 연결되지 않았다는 뜻이다. 실제로 무한 값은 아니고 자료형의 최대값으로 보는 게 적절하다. 노드 간의 방향성도 표현할 수 있다. 단방향, 양방향을 아래와 같이 표현할 수 있다. 2. 다익스트라 알고리즘 직접 해보기 이.......
https://www.acmicpc.net/problem/1700 문제를 읽고 'DFS로 풀면 되겠구나'라고 생각해서 무지성 코딩을 했는데 시간 초과가 났다. 반례들은 다 통과하기 때문에 정답을 도출하는 것에는 문제가 없는 코드라고 생각한다. 다만 모든 경우의 수를 따지기 때문에 비효율적일 뿐... 우선 버리기는 아까우니깐 DFS 코드를 살펴보자. 알고리즘은 아래와 같다. (정답 코드는 아래쪽에 있음) 이제 정답 코드를 살펴보자. 알고리즘은 정말 간단하지만 생각하기가 꽤나 까다로운 문제였던 거 같다. 방법이 떠오르면 풀만한 문제지만 그렇지 않으면 오래 걸리는 문제.. 아래의 규칙만 따르면 된다.
https://www.acmicpc.net/problem/1806 이 문제를 읽자마자 '그냥 이중 for문을 돌리면 되겠구나'라고 생각했다. 그러나 제한 시간 0.5초를 보고 시간 초과가 날 것이라 생각했다. 아니나 다를까, 이중 for문으로 짜니깐 시간 초과가 났다. O(n)의 시간 복잡도로 해결해야 하는 문제다. 투 포인터를 아는지 모르는지에 대한 문제라고 생각한다. 이 문제의 핵심은 '연속'에 있다. 연속합을 구하는 것이기 때문에 중복되는 부분이 존재한다. 말로 하면 헷갈리니깐 그림으로 보자. 위 그림에서 빨간색과 파란색의 연속된 부분합에서 형광색 부분이 중복됨을 알 수 있다. 이 사실을 잘 기억하자. 이제 투 포인터의 알고리즘을 살.......
https://www.acmicpc.net/problem/1916 모든 비용이 0 이상이고, 최소비용을 구하기 때문에 다익스트라로 해결할 수 있다. 알면 쉽고, 모르면 어려운 문제라고 생각한다. 다익스트라의 구현 방법은 세 가지가 있는데, 나는 가장 비효율적인 방법으로 풀었다. 시간복잡도는 O(N^2)다. 가장 비효율적인 방법으로 푼 이유는 다른 두 방법을 몰랐기 때문이다. 다익스트라에 대한 설명은 알고리즘 파트에서 볼 수 있다. 시간 복잡도가 O(nlogn)인 방법도 정리해놨다.
https://www.acmicpc.net/problem/2581 소수 판별 함수 isprime()을 만들어주고 소수면 최소값 초기화, sum에 값을 더해준다. 최소값이 10000으로 변화 없으면 소수가 없다는 뜻이므로 -1을 반환해주고 그 외에는 sum, min을 차례대로 출력해준다.
프로세스는 간단하게 '실행 중인 프로그램'으로 정의할 수 있다. '실행중'이라는 것은 해당 프로그램이 메모리 위에 있다는 것을 뜻한다. 프로그램은 컴퓨터 상에 설치된 'exe' 파일이라고 생각하자. exe파일은 실행파일이라고 하는데 이는 단순히 코드일 뿐이다. exe파일을 클릭하면 필요한 메모리 공간을 할당받는데, 이를 프로세스라고 한다. 하나의 프로그램이 여러개 실행되면 프로세스 또한 여러개가 되는 것이다. 그림으로 나타내면 아래와 같다. OS가 프로세스에게 할당하는 메모리는 구역마다 이름이 정해져 있다. 각 구역의 이름은 Text, Data, Stack, Heap이고, 저장되는 데이터 종류는 아래와 같다. -.......
메인 메모리는 커널 영역과 사용자 영역으로 구분된다. 이 둘은 같은 공간을 공유하고 있으므로 자칫하면 사용자 영역이 커널 영역을 침범할 수 있다. 이러한 침범 문제를 방지하기 위해 하드웨어의 도움이 필요하다. CPU에는 Mode bit라는 것이 존재한다. Mode bit 값에 따라 커널 모드와 사용자 모드로 구분되는데, 커널 모드는 모든 메모리에 접근 가능하지만 사용자 모드는 오직 사용자 영역에만 접근 불가능하다. 하드웨어적으로 아예 분리를 시켜놨기 때문에 사용자 영역이 커널 영역을 침범하는 일은 없다. 한편, 사용자 모드에서는 실행 가능한 명령이 매우 한정적이다. 컴퓨터를 할때 대부분이 커널 모드로 동작한다고 봐도 무방하다. 그.......
https://www.acmicpc.net/problem/14888 내 풀이가 좋은 풀이는 아닌 것 같다. 그래도 우선 풀어야 하기 때문에... 생각나는대로 풀었다. 가능한 연산자 조합을 구하는 문제이므로 next_permutation을 썼다. 연산자 종류를 operators라는 벡터에 삽입한 후에, 연산자의 모든 조합으로 계산을 해주고 각각의 경우에 최대값과 최소값을 초기화해줬다. 다른 방법으로 DFS로 푸는 방법이 있다. 원리는 완전하게 동일한데 재귀 함수를 쓰기 때문에 코드가 짧아진다는 점... DFS 방법은 아래쪽에 있다
1. Next Permutation 알고리즘 문제를 풀다 보면 <algorithm> 라이브러리의 next_permutation 함수를 쓸 일이 많다. 문득 이 함수의 원리가 궁금해서 이 글에 정리해보려고 한다. Next permutation의 기본 원리는 오름차순을 내림차순으로 변경하는 것이다. 변경하는 과정에서 모든 가능한 조합이 나오게 된다. 단, 수열은 사전에 오름차순 정렬되어 있어야 한다. Next_permutation의 과정을 살펴보면 아래와 같다. Next Permutation 과정 1. find max(k), a[k] < a[k+1] 2. find max(m), a[k] < a[m] && k < m 3. swap(a[k], a[m]) 4. reverse(a[k+1:]) [1, 2, 3, 4, 5]를 수동으로 한 예시다. 이런식으로 계속 반복하면.......
https://www.acmicpc.net/problem/1935 후위 표기식의 계산법을 알기만 하면 간단하게 풀 수 있는 문제다. 하지만 나는 원리를 잘 몰랐기 때문에 꽤나 고민했다. 정답을 보고 푼 것은 아니지만 알고리즘에 대한 선행 학습을 하고난 뒤에 풀어서 정답을 보고 푼 것 같은 느낌이다. 후위 표기식을 계산하기 위해서는 스택이 필요하다. 그리고 아래 두 가지 규칙만 지켜주면 된다. 1. 피연산자면 스택에 push 2. 연산자면 스택에서 두 개 pop해서 연산 후 결과값 push 아주 간단하다. 123*+45/-를 계산하는 예시를 살펴보자. 단, 스택에서 꺼낼 때 계산 순서가 (아래쪽) + (위쪽) 임을 주의하자. 위 두 가지 규칙 그대로 코드로 구현하면 아래와 같.......
https://www.acmicpc.net/problem/14719 아이디어만 떠오르면 굉장히 쉬운 문제다. 다행히도 문제를 읽고 생각나는대로 알고리즘을 짜봤는데 잘 맞아서 빨리 풀 수 있었다. 아이디어는 아래와 같다. 모든 칸에 대해 '흰색'이면 그 칸을 기준으로 같은 행에 좌우로 검은색 칸이 있으면 그 칸은 빗물이 고이는 칸이다. 사실 이게 끝이다. 더 설명할게 없다. 나는 아래와 같은 순서로 코드를 구현했다. 1. 2차원 배열을 0으로 초기화. 즉 0이 흰칸. 2. 검은칸을 1로 초기화. 즉 1이 검은칸. 3. 모든 칸에 대해 흰칸이면 좌우에 검은칸이 있는지 검사하고 있으면 정답에 1 더해준다. 4. 정답 출력
코딩 테스트를 준비하면서 느낀건데 최종 보스는 DFS와 dp인 것 같다. 생각하기는 어려운데 굉장히 직관적이랄까.. 백준 문제를 풀다가 조합이 꼭 필요한 문제가 있었는데 조합을 구현할 줄 몰라서 이 글을 쓰게 됐다. 조합을 먼저 구현한 뒤에 순열을 구현해 보겠다. 둘 다 재귀를 이용한 DFS로 구현한다. 1. 조합 그냥 직관적으로 생각해보자. 크기가 5인 배열 {4, 2, 1, 3, 5}에서 3개를 뽑는 5_C_3의 경우를 예로 들어보자. 첫번째 숫자부터 차례대로 뽑았다가 3개를 다 뽑으면 다시 되돌아오고 다음 숫자를 뽑을 것이다. 말로 하면 헷갈리니 그림으로 보자. 5가지 경우의 수까지를 살펴보면 아래와 같다. 우선 조합에서는 각 경우의 수 마다.......
https://www.acmicpc.net/problem/1062 조합을 구현할 수 있는지 없는지에 대한 문제였다. 조합을 구현할 줄 알면 나름 수월하게 풀 수 있다. 하지만 나는 조합을 구현할 줄 몰랐기 때문에 조합을 구현하는 것부터 배웠다. '알고리즘' 파트에 조합, 중복조합, 순열, 중복순열에 대한 글을 정리해놨다. 문제를 읽고 이해하기까지 5분 정도 걸린 것 같다. 이 문제에서 주의할 점은 모든 단어가 'anta'로 시작하고 'tica'로 끝난다는 점이다. 따라서 a, n, t, i, c 다섯 글자가 K 안에 항상 포함된다. 즉, K가 5보다 작으면 정답은 항상 0을 출력, K가 26이면 모든 글자를 배운 경우이므로 N을 출력하면 된다. 원리는.......
https://www.acmicpc.net/problem/1918 후위 표기식에 대한 설명은 '알고리즘' 파트에서 '중위 표기식을 후위 표기식으로 변환 후 계산'글에 정리해놨다.
중위 표기식은 연산자가 중간에 위치하는 표기식으로 우리가 늘 쓰는 표기식이다. 후위 표기식은 연산자가 뒤에 있는 표기식으로 컴퓨터의 연산 방식이다. 컴퓨터는 사람이 입력한 중위 표기식을 후위 표기식으로 변환해서 연산을 진행한다고 한다. 중위 표기식 : A * (B + C) 후위 표기식: ABC+* 이번 글에서는 중위 표기식을 후위 표기식으로 변환하는 알고리즘과 후위 표기식을 계산하는 알고리즘을 다룬다. 두 가지 경우 모두 stack 자료구조가 필요하다. 1. 중위 표기식을 후위 표기식으로 변환 알고리즘은 아래와 같다. 이를 그대로 코드로 구현하면 된다. 코드를 보기 전에 먼저 수동으로 직접 해보자. 아래의 식을 위 알고리즘에 따라 후.......
https://www.acmicpc.net/problem/2504 개인적으로 너무 어려운 문제였다. 이틀을 꼬박 고민하다가 그냥 다른 사람의 풀이를 봤다. 알고리즘은 아래와 같다. 입력값의 인덱스 0번째 문자부터 순차적으로 진행된다.