투투

스택 스택은 후입선출(Last In First Out)의 구조를 갖고있다. 따라서 가장 늦게 들어온 데이터가 가장 먼저 반출된다. 이는 상자를 아래에서 위로 하나씩 쌓아올리는 것으로 생각할 수 있다. 상자를 쌓아올린 뒤에 상자를 다른 곳에 옮길 때 중간이나 처음이 아닌 가장 위에있는 상자를 먼저 들어서 옮기는 것이 효율적이다. 큐 큐는 선입선출(First In First Out)의 구조를 갖고있다. 따라서 가장 먼저 들어온 데이터가 가장 먼저 반출된다. 이것은 식당에 손님들이 줄을 서는 것을 생각해보면 알 수 있다. 손님들이 식당 앞에 줄을 선 후에 입장할 때는 가장 먼저 온 손님 즉, 가장 앞에 있는 손님들이 먼저 식당에 입장한다. 스택과 큐는 어려운 개념이 아니다. 하지만 이러한 성질을 이해했을 때 ..

https://programmers.co.kr/learn/courses/30/lessons/68936 코딩테스트 연습 - 쿼드압축 후 개수 세기 [[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]] [4,9] [[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]] [10,15] programmers.co.kr 접근 쿼드 트리를 구현해보았다. 만약 행과 열의 개수가 같은 2차원 리스트에서 행의 개수가 4라고 가정해보자. (0, 0)부터 시작해서 4x4를 모두 탐색했을 때 같은 숫자로..

우리는 PC를 이용해 웹 서핑을 하고 동시에 음악을 들으며 친구한테 메시지를 보낸다. 우리는 이러한 일들이 동시에 일어나고 있다고 느낀다. 하지만 실제로 굉장히 빠른 시간에 프로세스들이 교체되어 실행되는 것이다. 이때 운영체제가 현재 실행되고 있는 프로세스들을 관리하여 실행을 유지할 수 있는 정보들이 저장된 자료구조를 PCB(Process Control Block)이라고 한다. PCB의 구성요소 프로세스를 할당하거나 프로세스가 교체되었을 때 지금까지 수행된 내용을 기록하기 위해서는 PCB 내의 여러가지 요소들이 사용된다. PCB의 구성요소를 파악한다면 하나의 CPU에서 어떻게 여러 개의 프로세스가 실행될 수 있는지 파악할 수 있을 것이다. 프로세스 상태 : CPU를 할당해도 되는지 결정하기 위해 필요하며..

https://programmers.co.kr/learn/courses/30/lessons/17687 코딩테스트 연습 - [3차] n진수 게임 N진수 게임 튜브가 활동하는 코딩 동아리에서는 전통적으로 해오는 게임이 있다. 이 게임은 여러 사람이 둥글게 앉아서 숫자를 하나씩 차례대로 말하는 게임인데, 규칙은 다음과 같다. 숫자를 0 programmers.co.kr 접근 먼저 10진수로 진행했을 때 가장 마지막에 말해야하는 숫자까지 n진수로 변환하여 특정 문자열에 저장한다. 이후 n진수로 게임을 진행했을 때 말해야하는 범위까지 입력된 사용자의 차례의 수를 최종해에 대입한다. 구현 - 아래의 함수는 10진수를 n진수로 변환하는 함수이다. - s에 아래와 같이 초기화를 시킨 후에 number를 n으로 나눈 나머..

접근 최대 높이를 찾고 2차원 맵을 탐색해서 최대 높이의 위치에서 DFS를 진행한다. 현재 위치에서 상하좌우 탐색을 진행하고 현재 위치보다 높이가 작은 위치로 이동한다. 만약 같거나 클 때는 K만큼 공사할 수 있는지 판단하여 이동한다. 구현 - 최대 높이를 찾아서 max_value에 저장한다. - 2차원 리스트인 board를 탐색해서 max_value가 나올 때마다 dfs를 진행한다. - dfs에는 현재 위치, 방문 여부, 길이, 공사의 여부를 전달한다. N, K = map(int, input().split()) board = [list(map(int, input().split())) for _ in range(N)] max_value = 0 for y in range(N): for x in range(..

접근 리스트를 원소로 갖는 2차원 리스트를 생성하여 미생물들의 개수와 방향을 넣었다. 이후에 미생물이 이동할 때 새로운 2차원 리스트에 이동한 미생물들을 대입하였다. 그리고 2개 이상의 미생물들이 모였을 때 합을 구하고 제일 많은 개수를 갖는 미생물의 방향을 구하여 업데이트하였다. 구현 - 다음은 미생물들이 이동하는 것을 구현한 함수이다. - 먼저 기존의 미생물들이 들어있는 board를 탐색하여 해당 미생물을 이동시킨다. - 이동시켰을 때 약품이 칠해져있는 곳일 때는 개수를 반으로 나누고 방향을 반대로 설정한다. - 미생물의 개수가 1 이상일 때 새로운 위치에 대입한다. - 모든 미생물들의 이동이 끝난 후에 2개 이상이 모여있는 곳은 미생물들을 하나씩 꺼내어 총합을 구한다. - 이때 개수가 가장 많은 미..

https://programmers.co.kr/learn/courses/30/lessons/12987 코딩테스트 연습 - 숫자 게임 xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다. 먼저 모든 사원이 무작위로 programmers.co.kr 접근 A와 B를 모두 오름차순으로 정렬한다. 그리고 A를 탐색하면서 해당 숫자보다 큰 것을 B에서 찾는다. 이때 idx를 사용하여 B를 탐색할 때 사용한다. 만약 A의 첫 번째 숫자보다 큰 것을 찾았다면 B를 처음부터 탐색하는 것이 아니라 큰 것을 찾은 다음 숫자부터 탐색하여 시간을 줄인다. 구현 - A와 B를 오름차순으로 정렬한다. - A의 숫자..

접근 약품을 투입할 수 있는 모든 조합을 확인했을 때 완전탐색으로 풀이가 가능하다고 생각하였다. 따라서 K가 2 이상일 때 약품을 투입하는 조합을 생성하여 해당 셀을 모두 0 또는 1로 바꾸어주었다. 그리고 모두 성능검사에 통과하는지 판단하는 함수로 전달하여 판단하였다. 이 문제는 계속 49개만 맞았다고 나왔는데 문제점을 파악하기 어려웠다. 계속 시도를 해보다가 뒤늦게 깨달았는데 나의 풀이에 문제가 있었다. 만약 3개의 막에 약품을 주입한다했을 때 해당 막의 셀들을 모두 0 또는 1로 바꾸어주었다. 하지만 이렇게하면 3개의 막 중에 2곳은 0 1곳은 1을 주입할 수도 있는 경우의 수를 놓치고 있었다. 따라서 이 부분을 해결한 후에 PASS를 받을 수 있었다. 구현 - 성능 검사에 통과할 수 있는지 판단하..

먼저 프로세스에 대해서 공부를 했었다. 프로그램은 파일이 메모리에 올라가 있지 않고 디스크에 저장되어 있는 상태이며 프로그램을 실행시켰을 때 메모리에 올라가서 프로세스가 생성이 된다. 그렇다면 스레드는 무엇이고 어떻게 동작을 하는 것일까? 스레드가 생겨난 이유 스레드라는 개념이 생기기 전에는 프로그램이 시작되고 끝나기 전까지 하나의 프로세스를 사용하였다. 하지만 점점 프로세스가 복잡해졌고 하나의 프로세스로 프로그램을 실행시킬 수 없었다. 그렇다고 프로세스를 여러 개 사용할 수도 없다. 왜냐하면 운영체제는 안정적인 운영을 위해 프로세스에게 할당한 메모리 내에서만 활동할 수 있도록 하였기 때문이다. 즉 하나의 프로그램에 여러 개의 프로세스를 사용하더라도 프로세스끼리 정보가 공유되지 않기 때문에 오류가 발생한..

https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 접근 dfs를 통해 현재 단어에서 1개의 글자만 다를 때 해당 단어로 다음 탐색을 진행한다. 진행하다가 target 단어가 되었을 때 지금까지의 depth가 답이된다. 구현 - 먼저 answer에는 words의 길이에 + 1로 하여 찾지 못했을 때 0을 출력하도록 한다. - picked에 지금까지 선택한 단어들을 추가한..